基于截断边扩展图的网络可靠度近似分析

小型网络可以快速计算出可靠度精确值,但对于大型网络,可靠性精确值的计算非常困难,因此提出一种基于截断边扩展图的网络可靠性近似分析算法。实验结果证明,该算法能够在生成较小边扩展图和等价BDD(Binary Decision Diagrams)的基础上得到误差较小的近似值。     

基于边图的重叠社团检测研究

社团检测吸引了大量的研究,在真实网络中,社团的层次性和重叠性交织在一起,然而到目前为止大部分工作只研究网络的层次性或重叠性。 2010年Ahn在Nature上发表的文章证明层次性和重叠性是网络相同现象的两个方面,针对社团检测在Ahn的方法的基础上提出了新算法：边图谱分析,将谱分析方法应用到边社团发现上,进行了兼顾层次性和重叠性的社团检测研究,实验中使用两个真实网络来对比边图谱分析算法、Ahn的算法和派系过滤算法,实验结果表明本文提出的边图谱分析算法实现了网络的重叠社团检测并且社团划分结果比较满意。     

一个基于中心度的社团结构发现新算法*

针对GN算法在社团结构发现中时间复杂度高等问题,提出一种基于中心度的GN改进算法（DCGN）。该算法根据节点中心度以及节点之间的最短路径首先确定社团结构中心节点集,然后逐步删除社团结构中心节点之间的最大边介数连边,完成社团结构划分。DCGN算法避免了GN算法边介数计算开销大的问题,算法的时间复杂度约为O(cmn),其中c为常数,n为网络成员数,m为网络连边数。将DCGN和GN算法同时应用到Zachary网络及计算机随机生成网络中并进行了比较。实验结果表明,所提出的DCGN算法在运行效率和效果方面较之GN算     

基于信息熵的复杂网络社团划分建模和验证

社团结构是复杂网络最普遍和最重要的拓扑属性之一,社团结构的划分方法对分析复杂网络相关统计特性具有十分重要的理论意义.为了提高社团划分精度,提出了一种新的基于信息熵(information entropy)模块度的社团划分算法(简称IE算法).在有着确定社团结构的数据集和不确定社团结构的数据集上,通过选取Q值、社团划分个数、社团最大连通分量大小和强弱社团个数比例4个重要参数,将IE算法与两种最主要的基于模块度的划分算法GN(Girvan-Newman)和FastGN(Fast Girvan-Newman)进行对比,实验结果证明了IE算法在社团划分性能上优于GN和FastGN;将IE和其他7种最主要的经典社团算法进行时间复杂度分析,并在随机网络和真实网络上进行实验,结果表明该算法时间复杂度在GN与FastGN之间,时间复杂度小于GN而精确度优于GN,证明了在大多数数据集上IE算法的社团划分准确度优于传统基于点边比率的社团划分算法的准确度.     

一种基于可变半衰期的机会网络社团兴趣值更新策略

为了掌握节点移动的历史信息,提出了MDIR (Mass-group Detected by Interest-value )算法。该算法引入了社团的概念,将节点的移动规律与其它节点的关系进行关联。理论上,在社会网络中节点的移动可以归结为在不同社团中移动的过程。因此在该算法中,消息更倾向于向包含目标节点的社团转发。此外,考虑到社会关系的动态性,算法还引入兴趣值概念来更新网络拓扑中的社团结构。实验测试数据表明,在不同的节点密集度和网络资源有限的情况下,相较于Epidemic、BDCR以及SREP算法,MDIR算法可通过计算效用值进行路由转发来产生较低的转发能耗以及稳定的送达率。     

无线传感器网络加权质心相对定位算法

针对基于接收信号强度指示的无线传感器网络加权质心定位算法在实际应用中计算复杂的缺点,提出一种改进型传感器网络加权质心相对定位算法（WCL-RSSI）。该算法主要采用参考节点精选机制和定位组合精选策略选择定位自评误差小的节点进行三边测距定位,以此重建定位权值函数来减小坐标定位误差,最后采用加权质心法计算坐标,并计算该节点的定位自评估误差。仿真实验表明,在同等计算复杂度下,该算法较传统定位方法的定位精度有了明显的提高。     

基于最大节点接近度的局部社团结构探测算法

针对复杂网络社团结构挖掘算法复杂度高的问题,提出一种基于最大节点接近度的局部社团结构挖掘算法。该算法的时间复杂度为O(kd)。为验证该方法计算的准确性和计算的速度,与一种经典的挖掘局部社团结构方法——Clauset算法进行比较。实验结果表明,该算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有明显提高。     

基于最大节点接近度的局部社团结构探测算法

针对复杂网络社团结构挖掘算法复杂度高的问题,提出一种基于最大节点接近度的局部社团结构挖掘算法。该算法的时间复杂度为O（kd）。为验证该方法计算的准确性和计算的速度,与一种经典的挖掘局部社团结构方法——Clauset算法进行比较。实验结果表明,该算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有明显提高。     

一种改进的基于最大流的Web社区挖掘算法

针对原始最大流算法给每条边的边容量分配一个常量值,在社区质量及成员数量上造成的问题,提出了一种改进的Web社区挖掘算法。该算法考虑不同边的重要性差异,将加权PageRank算法中页面的重要度转化为衡量页面之间边重要性的传递概率值,并使用该值对边容量进行赋值。实验结果表明,改进的算法有效地提高了Web社区的质量。     

一种基于聚集系数的复杂网络社团划分算法

;社团划分算法是复杂网络研究中的一个热点问题,为发现复杂网络中的社团结构,更好的研究复杂网络的社团性质,本文利用网络中聚集系数提出了一种新的社团划分的算法,该算法综合运用复杂网络中点和边的信息,根据节点和边的聚集系数,计算出节点问的连接紧密程度,由局部到整体来划分出所有的社团结构。传统的复杂网络社团划分算法通过获得全局网络的信息,但随着网络规模的增加,获得全局网络的信息的难度也随之增加,本文提出的新算法避免这一难度所带来的问题。将该算法应用到Zachary空手道俱乐部网络和海豚社会网络,测试结果证明了该算法的可行性。     

基于子网络结构属性的网络分割研究

Girvan和Newman等人提出了一种基于“中间状态边”概念的网络分割算法,成为研究网络结构的代表性算法。根据“中间状态边”概念,提出了一种新颖的网络分割算法：该算法通过分析构成子网络的两个结构属性,给出了一种划分子网络的方法。根据计算机生成的随机网络和一些真实世界网络的子网络划分实验表明,该算法具有划分准确、计算量小的优点。     

Fast approximation of betweenness centrality through sampling

Betweenness centrality is a fundamental measure in social network analysis, expressing the importance or influence of individual vertices (or edges) in a network in terms of the fraction of shortest paths that pass through them. Since exact computation in large networks is prohibitively expensive, we present two efficient randomized algorithms for betweenness estimation. The algorithms are based on random sampling of shortest paths and offer probabilistic guarantees on the quality of the approximation. The first algorithm estimates the betweenness of all vertices (or edges): all approximate values are within an additive factor \(\varepsilon \in (0,1)\) from the real values, with probability at least \(1-\delta \). The second algorithm focuses on the top-K vertices (or edges) with highest betweenness and estimate their betweenness value to within a multiplicative factor \(\varepsilon \), with probability at least \(1-\delta \). This is the first algorithm that can compute such approximation for the top-K vertices (or edges). By proving upper and lower bounds to the VC-dimension of a range set associated with the problem at hand, we can bound the sample size needed to achieve the desired approximations. We obtain sample sizes that are independent from the number of vertices in the network and only depend on a characteristic quantity that we call the vertex-diameter, that is the maximum number of vertices in a shortest path. In some cases, the sample size is completely independent from any quantitative property of the graph. An extensive experimental evaluation on real and artificial networks shows that our algorithms are significantly faster and much more scalable as the number of vertices grows than other algorithms with similar approximation guarantees.     

基于回溯机制的互联网AS拓扑的Betweenness算法

Betweenness能够刻画节点或边在网络中的重要程度．在Internet中，Betweenness直接反应了特定网络拓扑结构下节点或链路可能承载的网络流量，能够对网络的动态行为进行预测．但传统的Betweenness计算复杂度较高，为O（n^3），但这些算法是为加权网络设计的，而很多实际的网络模型并没有考虑权重．另一方面，目前的算法都没有考虑边的语义，而互联网AS（autonomous system）拓扑中的边具有语义．针对简单无权网络提出一种基于回溯的时间复杂度为O（nm）的Betweenness计算方法．在进一步考虑Internet AS拓扑的特殊性，即任意两个相连的AS都具有某种商业关系的基础上提出了互联网AS层拓扑的Betweenness计算方法．     

Edge betweenness centrality: A novel algorithm for QoS-based topology control over wireless sensor networks

In this paper we propose a novel topology-control algorithm, called edge betweenness centrality (EBC). EBC is based on the concept of betweenness centrality, which has been first introduced in the context of social network analysis (SNA), and measures the “importance” of each node in the network. This information allows us to achieve high quality of service (QoS) in wireless sensor networks by evaluating relationships between entities of the network (i.e., edges), and hence identifying different roles among them (e.g., brokers, outliers), thus controlling information flow, message delivery, latency and energy dissipation among nodes. The experimental evaluation and analysis of EBC in comparison to other state-of-the-art topology control algorithms shows that our algorithm outperforms the competitor ones in all observed cases.     

基于连边相似度的重叠社区发现算法研究

针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN。算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,因此节点可以被划分到不同的社区,从而发现重叠社区。EGN算法首先需要构造网络节点之间连边关系的边图;然后根据边图中节点的关系计算网络图中连边的相似度,在节点之间相似度的基础上提出了连边之间相似度的计算方法;再按照相似度由小到大对边图删除边,构建出边图的树状图。树状图的每一层对应网络的一个划分,采用划分密度函数来衡量划分的质量,以此寻找最优的划分。最后将算法应用到Zachary空手道俱乐部网络中,并与GN算法进行对比,实验结果表明EGN算法能够很好地发现重叠社区。     

一种面向大型网络的快速随机化社区挖掘算法

寻找网络的社区结构对于理解真实网络的自组织机制、可视化大网络有重要的作用.然而,现有的社区挖掘算法由于性能较低,还难以处理大型网络,特别是有着百万顶点的网络.然而,百万规模的大网络却在越来越多的真实应用中大量涌现,这对于高效的有效社区识别算法提出新的需求.为此,一种新颖的随机算法被提出,能够在接近线性时间内,从大型网络上高效地挖掘质量较高的网络社区:新算法的核心思路是在每一随机步骤中对网络中的顶点进行基于深度优先顺序的编码,这样的编码有助于有效地识别社区之间的边.最后,通过针对模拟网络和真实网络的一系列实验验证了新算法的高效性和有效性.     

Estimating graph distance and centrality on shared nothing architectures

We present a parallel toolkit for pairwise distance computation in massive networks. Computing the exact shortest paths between a large number of vertices is a costly operation, and serial algorithms are not practical for billion‐scale graphs. We first describe an efficient parallel method to solve the single source shortest path problem on commodity hardware with no shared memory. Using it as a building block, we introduce a new parallel algorithm to estimate the shortest paths between arbitrary pairs of vertices. Our method exploits data locality, produces highly accurate results, and allows batch computation of shortest paths with 7% average error in graphs that contain billions of edges. The proposed algorithm is up to two orders of magnitude faster than previously suggested algorithms and does not require large amounts of memory or expensive high‐end servers. We further leverage this method to estimate the closeness and betweenness centrality metrics, which involve systems challenges dealing with indexing, joining, and comparing large datasets efficiently. In one experiment, we mined a real‐world Web graph with 700 million nodes and 12 billion edges to identify the most central vertices and calculated more than 63 billion shortest paths in 6 h on a 20‐node commodity cluster. Copyright © 2014 John Wiley & Sons, Ltd.     

基于代数连通性的复杂网络割边模型研究

传统的GN算法每次迭代删除一条边,时间复杂度高,其变种时间复杂度有所下降,但分割精度也有待于提高;在复杂网络图中,图的连通性是由拉普拉斯矩阵的第二小特征值决定的,通过最小化网络连通性,提出了贪婪谱优化割边模型,该模型在GN算法基础上,一次删除多条边,为避免出现边过度分割,每条边设置了权重;为了进一步降低时间复杂度,选择网络代数连通性下降最快的边进行删除,提出了基于边中心性测度的割边模型,与传统的利用最短距离和随机游走不同,模型采取谱分析方法对每条边定义边中心性测度,速度更快,分割精度能到达要求,适合处理中规模社区结构。