On mapping processes to processors in distributed systems

This paper is concerned with the implementation of parallel programs on networks of processors. In particular, we study the use of the network augmenting approach as an implementation tool. According to this approach, the capabilities of a given network of processors can be increased by adding some auxiliary links among the processors. We prove that the minimum set of edges needed to augment a line-like network so that it can accommodate a parallel program is determined by an optimal path cover of the graph representation of the program. Anoptimal path cover of a simple graphG is a set of vertex-disjoint paths that cover all the vertices ofG and has the maximum possible number of edges. We present a linear time optimal path covering algorithm for a class of sparse graphs. This algorithm is of special interest since the optimal path covering problem is NP-complete for general graphs. Our results suggest that a cover and augment scheme can be used for optimal implementation of parallel programs in line-like networks.A preliminary version of this paper was presented at the 6th IEEE Conference on Computer Communications (INFOCOM '87).This reseach is supported in part by National Semiconductor (Israel), Ltd.     

Graph-Based Dimensionality Reduction for Hyperspectral Imagery: A Review

Hyperspectral image(HSI) contains a wealth of spectral information, which makes fine classification of ground objects possible. In the meanwhile, overly redundant information in HSI brings many challenges. Specifically, the lack of training samples and the high computational cost are the inevitable obstacles in the design of classifier. In order to solve these problems, dimensionality reduction is usually adopted. Recently, graph-based dimensionality reduction has become a hot topic. In this paper, the graph-based methods for HSI dimensionality reduction are summarized from the following aspects. 1) The traditional graph-based methods employ Euclidean distance to explore the local information of samples in spectral feature space. 2) The dimensionality-reduction methods based on sparse or collaborative representation regard the sparse or collaborative coefficients as graph weights to effectively reduce reconstruction errors and represent most important information of HSI in the dictionary. 3) Improved methods based on sparse or collaborative graph have made great progress by considering global low-rank information, local intra-class information and spatial information. In order to compare typical techniques, three real HSI datasets were used to carry out relevant experiments, and then the experimental results were analysed and discussed.Finally, the future development of this research field is prospected.     

一种面向目标的情感极性分析方法

面向目标的情感分析是细粒度情感分析的重要任务之一,旨在预测句子中给定目标实体的情感极性.当前大多数研究方法忽略了句法结构信息,在情感判别时往往会关注无关词汇,从而使分类性能下降.为此,设计了一种新的引入句法结构的模型,该模型利用双向预训练编码器和作用于依存句法树的图卷积网络分别捕获文本的上下文信息和句法结构信息,并使用多头注意力机制进行信息聚合得到目标的情感分类表征.此外,还将该模型与现有的领域自适应方法相结合,同时向模型中引入领域知识和句法结构知识,进一步提升了模型效果.在几个常用的标准数据集上的实验结果表明了上述模型的有效性.     

基于图的语义网络构造算法研究

在自然语言处理的基础上,将中医领域本体与图的基本性质相结合,提出了构造中医诊疗知识语义网络算法。给出了图的基本性质、语义网络的图定义,并为知识的网络表示建立了相应的数据结构。将算法用于中医领域语义网络和语义场构建。试验结果表明,该算法具有较好的实用性。提出的基于图的语义网络构造算法,对于文本挖掘、知识获取技术研究有重要意义,也是中医专家知识获取的有效方法。     

基于分水岭和区域合并的图像分割算法*

提出一种应用分水岭与区域合并相结合的图像分割算法.本方法首先利用数学形态学分水岭算法对图像进行分割,然后对分割后的图像进行相似区域合并,以减少分水岭方法产生的过分割现象,从而得到较好的分割效果.     

基于多任务学习和知识图谱的面部表情识别

针对面部表情分类的模型中参数较复杂、识别准确率较低的问题,提出了一种基于知识图谱辅助识别的多任务学习算法模型（MLAM）,该模型由基于深度学习的识别模块与知识图谱嵌入模块两部分构成。首先从输入的数据中提取潜在的人脸局部表情特征,通过知识图谱实现局部表情和个体的复杂交互;然后在MLAM 模型中设计一个交叉压缩单元,关联这两个独立模块,自动学习局部表情和实体特征的高级交互,并在这两个任务之间传递交叉知识转移;最后,在FER2013和CK+的数据集上对比了同类算法,实验结果表明,该模型在上述数据集上分别得到了0.69和0.99的识别率,提高了面部表情识别准确率。     

一种基于图计算的电力系统故障建模方法

故障建模是电力系统仿真分析的重要基础,如何快速准确对某类（N-1、N-2等）故障进行建模一直困扰电网分析人员。首先,分析了电力系统故障建模需要考虑的故障发展路径、故障动作时序两个要素,其中故障发展路径的搜索是故障建模的难点;其次,结合电力系统数据结构特征,提出了基于图计算的电力系统故障建模方法;最后,通过一个规模较大的省级电网验证了所提方法的有效性。在未来“双碳”“双高”电力系统发展的背景下,所提方法为电力系统在线、离线仿真分析所依赖的全网故障建模提供了新的思路和工具。     

A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs

In recent years growing interest in local distributed algorithms has widely been observed. This results from their high resistance to errors and damage, as well as from their good performance, which is independent of the size of the network. A local deterministic distributed algorithm finding an approximation of a Minimum Dominating Set in planar graphs has been presented by Lenzen et al., and they proved that the algorithm returns a 130-approximation of the Minimum Dominating Set. In this article we will show that the algorithm is two times more effective than was previously assumed, and we prove that the algorithm by Lenzen et al. outputs a 52-approximation to a Minimum Dominating Set. Therefore the gap between the lower bound and the approximation ratio of the best yet local deterministic distributed algorithm is reduced by half.     

一种不确定图中最可靠最大流问题的解决方案

最可靠最大流是不确定图中可靠性最高的最大流,它是传统最大流问题在不确定图上的自然延伸.现有的最可靠最大流算法SDBA时间复杂性较高,无法满足实际中不同应用的需求,为此,文中提出一种具有普遍适用性的最可靠最大流解决方案.该方案包含面向不同需求的3种算法:基于负权群落消去的NWCE算法、基于时间约束优先单环消去的SPEA-t算法和基于概率阈值约束优先单环消去的SPEA-p算法.其中,NWCE算法借鉴最小费用最大流的"流平移"思想并基于文中提出的负权群落概念,在辅助剩余图中不断地消去可使可靠性增加而流量不变的负权群落,可证当消去所有负权群落时对应的最大流即为最可靠最大流.根据负权群落中由单环组成的群落占很高比例且相对于多环组成的群落更易查找和消去的性质,同时考虑到NWCE算法为了获得最优解,往往为了消去最后少数几个对概率提高贡献很小的负权群落却花费了很长时间的现象,提出SPEA-t和SPEA-p两种快速近似算法,前者是以规定时间内尽可能逼近最优解为目标,后者是以最少时间达到预设的概率阈值为目标,它们都采用了优先消去概率-时间效益较好的单环群落的策略,加快对最优解的逼近速度,减少或放弃时间开销较大的多环群落的消去,以满足那些对算法时间性能要求很高而结果以近似最优即可的应用需求.实验表明,相对于SDBA算法,NWCE算法结合概率剪枝策略在时间性能上有了数量级的提高,而SPEA-t算法和SPEA-p算法则具有更高的性能和更好的适用性.     

基于全网能量均衡的WirelessHART图路由算法

如何均衡使用网络节点能量并生成高可靠路由是WirelessHART网络研究的一个难题,为此提出了一种GRAEB（graph routing algorithm based on energy balancing）图路由算法。首先,网络被初始化为连通的图结构,能够提高丰富的冗余路径。网络管理器根据全网节点剩余能量、通信周期、链路分布等因子生成节点鲁棒系数矩阵,节点通过比较邻居的鲁棒系数来选择最优路径。另外,规定了邻居节点数的上限阈值,每次路由更新只保留鲁棒系数最优的邻居。仿真结果表明GRAEB不仅提高了网络可靠性,而且延长了网络寿命。