基于网络权重的多社团网络结构划分算法

利用社团网络的统计特性,提出一种适于社团网络线性时间复杂度的多社团识别算法.构造复杂网络中节点的权重计算函数,进而生成计算序列,用迭代算法对复杂网络各种类型的节点进行集合分配.通过多个不同规模的网络结构数据对算法的性能进行测试,实验结果表明该算法时间复杂度为线性,能够在较短时间内对复杂网络中的社团数和社团结构进行发现,该算法还表现出对不同密度网络社团识别良好的适应性.     

基于共享最近邻探测社团结构的算法

针对经典重叠社团结构发现的派系过滤算法中派系定义过于严格、算法缺乏实用性、时间复杂度高等问题,提出了一种基于共享最近邻的社团结构发现算法. 该算法不仅可以对网络进行社团结构的划分, 而且可以很好地把网络中的桥点找出,算法的时间复杂 度约为O(nhk), 其中n为网络中的节点数,h为核心社团的数目, k为网络中节点的 最大节点度.为了验证该算法的正确率和性能, 把该算法应用到计算机生成网络和真实网络中, 并与著名的社团探测算法——GN算法和NF快速算法进行了比较.实验的结果表明所提出的算法是有效可行的.     

复杂网络中的社团结构分析算法研究综述

许多实际网络中都存在着社团结构.为了寻找大规模复杂网络中的社团结构,人们提出了很多算法.本文综述了近几年来比较有代表性的一些算法.首先介绍了计算机科学中最有名的谱平分法和Kernighan-Lin算法,然后介绍了社会学中具有代表性的分裂算法和凝聚算法,并着重分析了最新提出来的一种寻找网络中彼此重叠的社团结构的派系过滤算法.最后指出了进一步的研究方向.     

基于节点相似性的LFM社团发现算法

传统的局部适应度社团发现算法(LFM)在社团结构模糊的网络中精度下降严重。针对此问题,提出LFMJ算法。利用邻居节点信息和改进的杰卡德系数重构网络,使网络结构更为清楚,社团划分结果更为准确。为验证算法,选择了5种算法在LFR网络和真实网络中进行测试,包括LFMJ、LFM和传统的LPA算法以及性能较好的WT和FUA算法。结果表明:在标准LFR网络中,LFMJ精度高于LFM和LPA,与FUA和WT相当;在真实网络和具有重叠结构的LFR网络中,LFMJ精度优于其他4种算法。     

节点重要度贡献的复杂网络节点重要度评估方法

引入m阶邻居节点的概念,提出了一种基于m阶邻居节点重要度贡献的复杂网络节点重要度方法,并引入α和γ两个参数,用于调节节点重要度评估对节点自身特性及m阶邻居节点的依赖程度。综合考虑了节点自身及1到m阶邻居节点的重要度贡献。为检验算法的有效性,采用ARPA网络拓扑并针对算法在不同m取值条件下的节点重要度情况进行了评估。评估结果显示,与度值法、介数法、节点删除法等评估方法相比,具有更高的评估精度,能显著地区分复杂网络中节点之间的重要性差异,能准确地确定网络中关键节点,保证节点重要度评估的准确性;此外,实验结果还揭示了一个重要动力学现象,即当邻居节点所考察的深度m值大于网络的平均路径长度L时,该方法可得到可靠且精度较高的评估结果。     

基于同步理论的股票网络社团识别研究

利用股票价格波动时间序列的相关特性,基于同步理论研究股票网络的社团结构。通过对关联矩阵的谱分析确定股票网络中存在复杂的社团结构。随后,利用基于Kuramoto模型的同步聚类算法对网络节点(股票)进行动态分组,由局部序参量确定算法的收敛性并得到稳定的社团结构。通过与快速社团检测算法的对比验证,表明基于Kuramoto模型的同步聚类算法能够正确得到股票网络的社团结构,且更符合股票的属性分类。     

利用堆数据结构实现邻域重叠社团结构挖掘

基于当前复杂网络中社团划分算法普遍存在算法复杂度过高以及重叠节点挖掘不准确的局限性,提出了一种高效、快速、准确的社团划分算法。基于贪婪算法,建立最大模块度矩阵,并采用堆数据结构,划分非邻域重叠社团。通过分析局部网络的连边情况,计算邻域社团的划分密度,以准确挖掘社团间的重叠节点。新算法经过仿真分析和实证研究表明,算法复杂度降到近线性。     

基于非负矩阵分解的复杂网络重构

将网络连边的产生机制和其社团结构结合在一起,基于社团结构决定网络连边的假设推导出节点间的连接概率矩阵并表达为矩阵乘积的形式,然后利用非负矩阵分解得到节点间的连接概率矩阵进行网络重建。设计实验并在几个真实的网络数据上测试,相比基于相似度的网络重构算法,该算法取得了更好的网络重构效果。     

基于邻接信息熵的网络节点重要性识别算法

通过研究节点与其直接相邻和间接相邻节点之间的关联关系,提出了基于邻接信息熵的网络节点重要性识别算法,算法只需获取节点与其直接邻居及间接邻居间的关联关系,通过计算网络各节点的邻接度,进而计算各节点的信息熵,利用节点信息熵的大小表征节点在网络中的重要性.通过对一个基础网络、无向无权ARPA网络和加权有向ARPA网络进行实验仿真,证明该算法对不同类型网络的通用性;利用该算法对网络按节点重要性进行节点删除实验,研究网络形成子网络的数量与规模,证明了算法的准确性.     

一种有向网络中社团结构划分的启发式算法

复杂网络中的社团发现和探测是当前复杂网络分析领域中的一个热点研究问题,并且具有非常广泛的应用前景。但是,传统的社团划分算法主要以无向、无权网络为对象进行分析,不能够适用于现实世界中更多的有向网络、赋权网络等。以有向网络为研究对象,研究其中的社团划分算法。鉴于前人提出的有向网络中社团划分算法存在着计算时间复杂度问题,引入模拟退火算法对其进行改进,并在改进算法中考虑了节点的网络结构属性。通过对不同规模的计算机生成的有向网络进行算法测试,验证了本文算法的正确性。最后,对一个实际复杂网络进行了社团划分,进一步验证了算法的有效性。     

Distributed Algorithm for Robust Resource Allocation with Polyhedral Uncertain Allocation Parameters

This paper studies a distributed robust resource allocation problem with nonsmooth objective functions under polyhedral uncertain allocation parameters. In the considered distributed robust resource allocation problem, the (nonsmooth) objective function is a sum of local convex objective functions assigned to agents in a multi-agent network. Each agent has a private feasible set and decides a local variable, and all the local variables are coupled with a global affine inequality constraint, which is subject to polyhedral uncertain parameters. With the duality theory of convex optimization, the authors derive a robust counterpart of the robust resource allocation problem. Based on the robust counterpart, the authors propose a novel distributed continuous-time algorithm, in which each agent only knows its local objective function, local uncertainty parameter, local constraint set, and its neighbors’ information. Using the stability theory of differential inclusions, the authors show that the algorithm is able to find the optimal solution under some mild conditions. Finally, the authors give an example to illustrate the efficacy of the proposed algorithm.     

基于博弈论的多传感器交叉提示算法

针对传感器交叉提示技术在目标探测中的应用问题展开研究,首先介绍多传感器交叉提示技术基本理论,建立了具有社区性的传感器网络模型和基于多Agent技术的分布式传感器管理结构,分析了传感器交叉提示发生的条件和类型,其次提出了传感器网络效能评价函数,最后设计了基于博弈论的多传感器交叉提示算法。仿真结果表明,提出的多传感器交叉提示模型符合实际作战场景,能够生成传感器联盟方案对目标检测和跟踪,并进行目标交接,与拍卖算法和人工蜂群算法相比,博弈论算法求解质量较高,收敛速度明显提高,更适用于作战态势较紧急的情形。     

基于体系破击的联合火力打击目标价值评估

针对体系破击战法中的目标选择问题,设计了适用于多属性指标融合的熵权理想点法。并从超网络体系架构出发,设计了以信息流循环效率为评估标准的目标体系价值评估算法。针对联合火力打击多目标同步打击特点,设计了目标组合的体系价值评估算法。在上述算法基础上实现了目标多属性评估,以及基于单目标和目标组合的体系价值评估。实验分析表明,该方法能够快速实现联合火力打击目标的价值量化评估,并且用量化数据验证了联合火力打击中应遵循的3条基本原则,结合目标属性表和体系关联网络找到体系破击的关键目标或目标组合,输入条件简单易行,具备工程应用的基础条件。     

基于体系破击的联合火力打击目标价值评估

针对体系破击战法中的目标选择问题,设计了适用于多属性指标融合的熵权理想点法。并从超网络体系架构出发,设计了以信息流循环效率为评估标准的目标体系价值评估算法。针对联合火力打击多目标同步打击特点,设计了目标组合的体系价值评估算法。在上述算法基础上实现了目标多属性评估,以及基于单目标和目标组合的体系价值评估。实验分析表明,该方法能够快速实现联合火力打击目标的价值量化评估,并且用量化数据验证了联合火力打击中应遵循的3条基本原则,结合目标属性表和体系关联网络找到体系破击的关键目标或目标组合,输入条件简单易行,具备工程应用的基础条件。     

探讨复杂系统中的群体结构

为探讨恰当划分复杂系统群体蛄构的新方法，提出了改进边介数法。在对网络实例空手道俱乐部的研究中，将谊方法与传统社会学聚类方法和GN算法进行了对照比较。其实证结果表明了谊方法对于正确分析系统的群体结构的有效性。     

基于节点动态连接度的网络社团划分算法

首先定义了节点动态连接度这一概念,然后介绍了基于节点动态连接度的网络社团划分算法,之后再对其中相关参数的取值范围和社团划分结果之间的关系进行了分析,并以Zachary网络为例验证了分析结论。在此基础上,以dolphins、polbooks和football 3个实际网络为对象,进行了社团划分实验,证明了本算法可通过动态调整参数实现对不同网络的社团划分。最后将实验结果与其他几种常见的社团划分算法结果进行了比较,证明了算法的优势,并对算法中需要注意的一些问题进行了说明。     

Distributed localization for anchor-free sensor networks

Geographic location of nodes is very useful in a sensor network. Previous localization algorithms assume that there exist some anchor nodes in this kind of network, and then other nodes are estimated to create their coordinates. Once there are not anchors to be deployed, those localization algorithms will be invalidated. Many papers in this field focus on anchor-based solutions. The use of anchors introduces many limitations, since anchors require external equipments such as global position system, cause additional power consumption. A novel positioning algorithm is proposed to use a virtual coordinate system based on a new concept--virtual anchor. It is executed in a distributed fashion according to the connectivity of a node and the measured distances to its neighbors. Both the adjacent member information and the ranging distance result are combined to generate the estimated position of a network, one of which is independently adopted for localization previously. At the position refinement stage the intermediate estimation of a node begins to be evaluated on its reliability for position mutation; thus the positioning optimization process of the whole network is avoided falling into a local optimal solution. Simulation results prove that the algorithm can resolve the distributed localization problem for anchor-free sensor networks, and is superior to previous methods in terms of its positioning capability under a variety of circumstances.     

Remarks on Network Community Properties

This paper discusses a popular community definition in complex network research in terms of the conditions under which a community is minimal, that is, the community cannot be split into several smaller communities or split and reorganized with other network elements into new communities. The result provides a base on which further optimization computation of the quantitative measure for community identification can be realized.     

基于像素合作博弈的非刚性图像配准方法

用离散位移场表示形变,将非刚性图像配准问题转化为马尔可夫随机场中的最大后验概率推理问题,从而等价于吉布斯随机场中的能量极小问题。为获得能量极小点,将配准视为像素间的博弈,提出了基于多人合作博弈的非刚性图像配准方法,设计了相应的确定性算法。博弈配准时,每个像素尝试与邻居结盟选择一致的位移向量,使自身和联盟的收益都最大化,迭代地完成配准。新方法能配准复杂的形变,精度高、鲁棒性好,非常适用于图像的精配准。实验结果验证了合作博弈配准方法的可行性和有效性。