基于联系度的主题关注网络社区发现方法研究

目前,以兴趣或主题分享等为目的的兴趣型社交网络则引领着社交网络改革的浪潮。融合社交关系和兴趣爱好关系构建一个新型社交网络模型--主题关注模型。在此模型基础上,采用集对联系度刻画顶点间相似性度量指标,该度量方法可以更好地刻画网络结构特征,提高传统局部相似性度量指标对某些顶点间相似性值的计算精度,降低全局相似性度量指标的计算复杂度。综合考虑主题影响和社交关系,将集对联系度与凝聚型聚类算法相结合,提出一种新的主题社区发现方法。在Karate网络和豆瓣数据集上进行主题社区发现,实验结果表明,考虑主题影响的划分具有更好的社区结构。     

Remodeling the network for microgroup detection on microblog

In this paper, we focus on the problem of community detection on Sina weibo, the most popular microblogging system in China. By characterizing the structure and content of microgroup (community) on Sina weibo in detail, we observe that different from ordinary social networks, the degree assortativity coefficients are negative on most microgroups. In addition, we find that users from the same microgroup tend to share some common attributes (e.g., followers, tags) and interests extracted from their published posts. Inspired by these new findings, we propose a united method to remodel the network for microgroup detection while maintaining the information of link structure and user content. Firstly, the link direction is concerned by assigning greater weight values to more surprising links, while the content similarity is measured by the Jaccard coefficient of common features and interest similarity based on Latent Dirichlet Allocation model. Then, both link direction and content similarity between two users are uniformly converted to the edge weight of a new remodeled network, which is undirected and weighted. Finally, multiple frequently used community detection algorithms that support weighted networks could be employed. Extensive experiments on real-world social networks show that both link structure and user content play almost equally important roles in microgroup detection on Sina weibo. Our method outperforms the traditional methods with average accuracy improvement up to 39 %, and the number of unrecognized users decreased by about 75 %.     

Topological characterization and modeling of dynamic evolving power distribution networks

Existing complex network models are either with unvaried network size or based on simple growth mechanisms which cannot accurately describe the operational dynamics and characteristics of realistic networks. In this paper, we exploit the dynamic evolving phenomenon of power distribution networks covering its growth, reconnection and shrinking characteristics from the network topology perspective, and attempt to produce a novel dynamic evolving model through introducing the locating probability and shrinking mechanism. The proposed modeling approach is assessed and validated through extensive numerical simulation experiments for a range of standard IEEE power test systems. The statistical results reveal that the node degree distribution of the power network follows the power-law distribution and the node removal probability of the network dynamic has a significant impact on the network evolvement and robustness. Such macroscopic topological findings can greatly benefit the power distribution network operators (DNOs) from many aspects, including network planning, vulnerability analysis, fault prediction and cost-effective reinforcement.     

一种时序有向网络中的链路预测方法

真实网络大多是有向的，且网络结构随时间动态变化，传统的链路预测方法大多适用于无向网络，其分析方法不能有效挖掘真实网络中的信息。针对以上问题，提出了一种基于归一化AA和LAS的时序有向的链路预测算法，该算法基于共同邻居、节点度属性及局部社团相似性，为每个链接分配时间影响因子并将其引入NALAS指标进行计算，考虑了网络有向性和网络历史结构的影响。在真实社会网络数据集上对该算法进行了仿真并与Salton、Jaccard等算法进行对比。结果表明，提出的算法与其他算法相比，预测精度得到了提高，说明该算法可以有效地在时序有向的社会网络中进行链路预测。     

小世界网络中的删边扩容效应

不同于无标度网络,小世界网络中体现负载特性的介数分布和体现连接特征的度分布这两种结构差异很大,依据这个差异,我们提出了有效的删边扩容方法并进行了仿真实验,并进一步从容量与最大介数的关系理论分析确证了实验结果.接着,我们分析了小世界网络中介数分布的差异性与删边扩容效果的相关性,把基于介数的基尼系数变化用于度量删边扩容的效果,指出了结构差异是导致删边扩容效应的必要条件.还指出了无论从容量与介数的定义、仿真结果、结构差异与删边扩容效果的关系来看,都应该从介数入手来实现删边扩容方法,这种方法反直觉,有很多变种,并且实现方便、节省成本,作为一类新的路由策略可以广泛地应用于各类通信网络和交通网络等领域.     

Multidimensional networks: foundations of structural analysis

Complex networks have been receiving increasing attention by the scientific community, thanks also to the increasing availability of real-world network data. So far, network analysis has focused on the characterization and measurement of local and global properties of graphs, such as diameter, degree distribution, centrality, and so on. In the last years, the multidimensional nature of many real world networks has been pointed out, i.e. many networks containing multiple connections between any pair of nodes have been analyzed. Despite the importance of analyzing this kind of networks was recognized by previous works, a complete framework for multidimensional network analysis is still missing. Such a framework would enable the analysts to study different phenomena, that can be either the generalization to the multidimensional setting of what happens in monodimensional networks, or a new class of phenomena induced by the additional degree of complexity that multidimensionality provides in real networks. The aim of this paper is then to give the basis for multidimensional network analysis: we present a solid repertoire of basic concepts and analytical measures, which take into account the general structure of multidimensional networks. We tested our framework on different real world multidimensional networks, showing the validity and the meaningfulness of the measures introduced, that are able to extract important and non-random information about complex phenomena in such networks.     

A Community Structure‐Based Approach for Network Immunization

We propose a community structure‐based approach that does not require community labels of nodes, for network immunization. Social networks have been widely used as daily communication infrastructures these days. However, fast spreading of information over networks may have downsides such as computer viruses or epidemics of diseases. Because contamination is propagated among subgraphs (communities) along links in a network, use of community structure of the network would be effective for network immunization. However, despite various research efforts, it is still difficult to identify ground‐truth community labels of nodes in a network. Because communities are often interwoven through intermediate nodes, we propose to identify such nodes based on the community structure of a network without requiring community labels. By regarding the community structure in terms of nodes, we construct a vector representation of nodes based on a quality measure of communities. The distribution of the constructed vectors is used for immunizing intermediate nodes among communities, through the hybrid use of the norm and the relation in the vector representation. Experiments are conducted over both synthetic and real‐world networks, and our approach is compared with other network centrality‐based approaches. The results are encouraging and indicate that it is worth pursuing this path.     

Internet自治系统级拓扑复杂网络特征分析与验证

为深入理解和认清Internet复杂巨系统的不变特征和动态规律,分析研究Internet自治系统级拓扑的复杂网络特征,给出幂律分布和无标度条件的数学描述以及寻找两者之间的关系,分析小世界网络的两个重要特征,即较短平均路径长度和较大聚集系数,讨论匹配性问题和富人俱乐部现象,基于上述理论结果和BGP经验数据计算自治系统级拓扑的最大节点度、平均节点度、聚集系数和最大团数,发现自治系统级拓扑具有幂律分布、异配性以及富人俱乐部现象等复杂网络特征,得到幂指数、匹配系数以及富人俱乐部系数等重要特征参数。     

Algebraic connectivity metric for spare capacity allocation problem in survivable networks

For studying survivability of telecommunication networks, one should be able to differentiate topologies of networks by means of a robust numerical measure that can characterize the degree of immunity of a given network to possible failures of its elements. An ideal metric should be also sensitive to such topological features as the existence of nodes or links whose failures are catastrophic in that they lead to disintegration of a given network structure. In this paper, we show that the algebraic connectivity, adopted from spectral graph theory, namely the second smallest eigenvalue of the Laplacian matrix of the network topology, is a numerical index that characterizes a network’s survivability better than the average node degree that has been traditionally used for this purpose. This proposition is validated by extensive studies involving solutions of the spare capacity allocation problem for a variety of networks.     

一种基于模糊相似关系的局部社区发现方法

近几年,在线社交媒体发展飞速,出现了大规模社会网络.传统的基于网络全局结构的社区发现方法难以有效地处理这些大网络.局部社区发现作为一种无需知道网络的全局结构、仅通过分析给定节点的周围节点之间的关系即可找出给定节点所在社区的方法,在社会网络大数据分析中具有重要的应用意义.针对真实世界网络结构中个体间的相似关系是模糊的或不确定性的,提出了一种基于模糊相似关系的局部社区发现方法.首先,采用模糊关系来描述两个节点之间的相似关系,以节点对的相似度作为该模糊关系的隶属函数;然后证明了该关系是一种模糊相似关系,将局部社区定义为给定节点关于模糊相似关系的等价类,进而采用最大连通子图算法求得给定节点所在的社区.分别在仿真网络和真实网络上进行了实验,实验结果表明,该算法能够有效地揭示出给定节点所在的局部社区,相比其他算法,具有更高的F-score.     

复杂网络重叠社区结构发现的演化算法研究

复杂网络重叠社区结构的划分已成为复杂网络研究的一个热点,目前已提出了很多关于社区结构发现的算法。提出了一种基于个体从众的演化算法ICEA,基本思想是由节点邻居组成的个体依概率进行从众和变异操作,用较短时间找到最优(或拟最优)模块度的社区划分,社区结构确定后利用邻居投票机制NV发现网络的重叠节点,完成重叠社区的划分。在真实网络的实验结果表明,此算法的使用时间和划分结果都优于典型算法。     

基于社区划分的多智能体网络快速蜂拥控制

针对复杂网络社区特性对多智能体系统协同控制效率的影响,面向具有ER(Erdos-renyi)网络或BA (Barabasi-albert)网络性质的多智能体系统,提出一种基于社区划分的快速蜂拥控制算法.该算法充分考虑社区内个体的相对密集特性,通过在社区间引入虚拟领导者作用,避免系统在演化过程中因通信受限而导致的“分块”现象,可有效提高系统拓扑的代数连通度.仿真结果表明:具有相应性质的多智能体系统蜂拥行为的收敛速度与ER和BA网络的平均度以及BA网络度分布的幂指数正相关;优化社区个数有利于提高蜂拥收敛速度.     

图聚类算法的评价模型

关系数据可抽象为网络,在通常情况下,缺乏对这些现实网络背景知识的了解。为了评价图聚类算法在现实网络上的性能表现,构建了一种接近现实的网络模型,通过算法在模型网络上的性能表现来推断其分析现实网络的能力。为了确保此推断的合理性,构建的模型网络具有与所研究网络完全相同的一阶统计特征。同时,构建的模型网络可具有任意设定的集团结构,这就相当于给定了背景知识,即真实的分类信息是已知的。实例说明,构建的模型为客观评价图聚类算法提供了一条途径。     

稳定的标签传播社团划分算法研究

快速稳定地发现复杂网络中的社团是近年来社团划分研究的热点。标签传播算法(LPA)具有接近线性的时间复杂度,能快速发现复杂网络中的社团结构,但是该算法在标签传播过程中存在不确定性和随机性,降低了划分结果的准确性和稳定性。为了解决这一问题,设计了一种稳定的标签传播社团划分算法(S-LPA)。该算法利用改进的K-Shell算法来计算节点全局影响力,并结合能反映节点局部影响力的度值以及邻居节点信息,计算节点综合影响力;在标签传播过程中,根据标签影响力更新标签;当网络中所有节点的标签不再变化或者迭代次数达到最大值时,拥有相同标签的节点划分到同一社团中。在真实网络和人工合成网络上的实验结果表明,S-LPA算法不仅具有线性时间复杂度,而且提高了社团划分的质量和稳定性。     

基于社团划分的网络聚类布局算法

复杂网络日益受到广大专家和学者们的关注,对其进行可视化展示可以帮助用户发现复杂网络表征的复杂系统中隐藏的知识信息,对计算机科学、社会学、生物学等领域具有重要的意义。力导引布局算法是复杂网络可视化领域的主流算法,它用节点连接图的形式对复杂网络进行抽象表示,布局遵循一定的美学标准如节点的均匀分布、边长尽量一致等,这在一定程度上阻碍了对复杂网络的社团结构的展示。针对以上问题,本文提出引入基于度中心性的社团斥力与引力对力导引算法进行改进,以对复杂网络进行聚类布局。实验结果表明,本文算法可有效地展示复杂网络的社团结构,同时又能保留社团之间边缘节点的信息。     

基于社团强度系数的社团结构发现算法

社团结构是复杂网络普遍存在的拓扑特性之一.为了将复杂网络中的社团结构有效地划分出来,在对强社团定义的基础上,引入社团强度系数的概念,提出了一种基于社团强度系数的社团结构发现算法.该算法具有较低的时间复杂度,通过不断寻找网络最大度数的节点及其邻居节点,计算其社团强度系数来衡量社团如何划分.主要针对Zachary网络和Dolphin网络等进行了仿真实验,结果表明该算法具有较高的社团划分准确度、较好的敏感性和良好的可扩展性,充分验证了其可行性和有效性.     

Synchronisation between two different networks with multi-weights and its application in public traffic network

The paper established a conventional bus traffic network and a subway network by using the method of space R based on the existing public traffic network model. Regarding these two networks as the sub-networks, this paper presented a new two-layer-coupled public traffic network with multi-weights through the transfer relationship between conventional bus lines and subway lines. Every edge of this model’s two sub-networks has one or several different property weights, and the coupling edges between two sub-networks have one weight. Based on the method of network split, the paper splits the complex networks with multi-weights into several different single-weighted two-layer-coupled public traffic networks and then investigates its global synchronisation. Finally, according to the synchronisation theory of coupling networks with multi-weights and taking ‘Lorenz system’ as the network node, some numerical examples are given to show the impact of congestion degree, passenger-flow density, transfer degree and capacity matching degree to the two-layer-coupled public traffic network balance.     

An improved algorithm for finding community structure in networks with an application to IPv6 backbone network

The discovery of community structure in a large number of complex networks has attracted lots of interest in recent years. One category of algorithms for detecting community structure, the divisive algorithms, has been proposed and improved impressively. In this paper, we propose an improved divisive algorithm, the basic idea of which is to take more than one parameters into consideration to describe the networks from different points of view. Although its basic idea appears to be a little simple, it is shown experimentally that it outperforms some other algorithms when it is applied to the networks with a relatively obscure community structure. We also demonstrate its effectiveness by applying it to IPv6 backbone network. The communities detected by our algorithm indicate that although underdeveloped compared with IPv4 network, IPv6 network has already exhibited a preliminary community structure. Moreover, our algorithm can be further extended and adapted in the future. In fact, it suggests a simple yet possibly efficient way to improve algorithms.     

一种基于粗糙集和密度峰值的重叠社区发现方法

随着互联网和社会的发展,各个领域每天都会产生大量相互关联、彼此依赖的数据,这些数据根据不同的主题形成了各种复杂网络。挖掘社区结构是复杂网络领域中的一项重要研究内容,因为其在推荐系统、行为预测和信息传播等方面具有极其重要的意义。社区结构中的重叠社区结构在生活中普遍存在,更具有实际研究意义。为有效发现复杂网络中的重叠社区,文中引入了粗糙集理论对社区进行分析,识别出重叠节点,进而提出了一种基于粗糙集和密度峰值的重叠社区发现方法OCDRD(Overlapping Community Detection Algorithm Based on Rough Sets and Density Peaks)。该方法在传统网络节点局部相似性度量的基础上,结合灰色关联分析方法求出网络节点间的全局相似性,进而将其转化为节点间距离。将密度峰值聚类算法的思想应用于该算法中,以根据网络结构自动选取社区中心节点。依据网络中节点的距离比例关系,定义了社区的上近似、下近似以及边界域。最后,不断调整距离比率阈值并进行划分迭代,在每次迭代中针对社区的边界域进行计算,从而获得最佳重叠社区划分结构。在LFR基准人工网络数据集和真实网络数据集上,基于标准互信息(Normalized Mutual Information,NMI)和具有重叠性模块度EQ这两个评价指标,将OCDRD方法与近几年效果较好的其他社区发现算法进行测试比较。实验结果显示,OCDRD方法在社区划分结构方面整体优于其他社区发现算法,表明了该算法的可行性和有效性。