Community mining using three closely joint techniques based on community mutual membership and refinement strategy

Community structure has become one of the central studies of the topological structure of complex networks in the past decades. Although many advanced approaches have been proposed to identify community structure, those state-of-the-art methods still lack efficiency in terms of a balance between stability, accuracy and computation time. Here, we propose an algorithm with different stages, called TJA-net, to efficiently identify communities in a large network with a good balance between accuracy, stability and computation time. First, we propose an initial labeling algorithm, called ILPA, combining K-nearest neighbor (KNN) and label propagation algorithm (LPA). To produce a number of sub-communities automatically, ILPA iteratively labels a node in a network using the labels of its adjacent nodes and their index of closeness. Next, we merge sub-communities using the mutual membership of two communities. Finally, a refinement strategy is designed for modifying the label of the wrongly clustered nodes at boundaries. In our approach, we propose and use modularity density as the objective function rather than the commonly used modularity. This can deal with the issue of the resolution limit for different network structures enhancing the result precision. We present a series of experiments with artificial and real data set and compare the results obtained by our proposed algorithm with the ones obtained by the state-of-the-art algorithms, which shows the effectiveness of our proposed approach. The experimental results on large-scale artificial networks and real networks illustrate the superiority of our algorithm.     

LinkLPA: A Link‐Based Label Propagation Algorithm for Overlapping Community Detection in Networks

Community detection is an important methodology for understanding the intrinsic structure and function of complex networks. Because overlapping community is one of the characteristics of real‐world networks and should be considered for community detection, in this article, we propose an algorithm, called link‐based label propagation algorithm (LinkLPA), to detect overlapping communities. Because the link partition is conceptually natural for the problem of overlapping community detection, LinkLPA first transforms node partition problem into link partition problem and employs a new label propagation algorithm with preference on links instead of nodes to detect communities due to the simplicity and efficiency of label propagation algorithm. Then the proposed LinkLPA performs a postprocessing to refine the detected overlapping communities by avoiding over‐overlapping and incorrect partition of weak ties. Experimental results on a large number of real‐world and synthetic networks show that the proposed method achieves high accuracy on detecting overlapping communities in networks.     

基于网络嵌入与局部合力的复杂网络社区划分算法

社区划分可以揭示复杂网络中的内在结构和行为动态特点,是当前的研究热点。文中提出了一种基于网络嵌入和局部合力的社区划分算法。该算法将网络的拓扑空间转化成欧氏空间,把网络节点转换成向量表示的数据点,首先基于重力模型和网络拓扑结构,提出局部合力和局部合力余弦中心性指标(Local Resultant Force Cosine Centrality,LFC),通过节点的LFC和节点间的距离来确定各个初始小社区的中心节点,然后将网络中其他的非中心节点划入与其最近的中心节点所在的初始小社区内,最后通过优化模块度的方法来合并初始小社区并找到最优的网络社区结构。在6个现实世界网络和可调参数人工网络上与6种知名社区划分方法进行比较,比较结果表明了新算法良好的社区划分的性能。     

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

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

基于节点相似性和网络嵌入的复杂网络社区发现算法

社区发现算法对分析复杂网络的拓扑和层次结构、预测复杂网络的演化趋势等具有十分重要的意义.传统的社区发现算法划分精度不高,忽略了网络嵌入的重要性.针对这样的问题,提出了基于节点相似性和网络嵌入Node2Vec方法的无参数社区发现算法.首先,使用网络嵌入Node2Vec方法将网络节点映射成欧氏空间中低维向量表示的数据点,计...     

社会语义网社区发现标签传递算法研究

针对在线社会网络的特性和现有社区发现算法的不足,提出一种基于语义网技术的在线社会网络社区发现算法ISLPA(Improved Semantic Label Propagation Algorithm),即一种适用于大规模在线社会网络的社区发现和标识算法。ISLPA算法对语义标签算法SemTagP进行改进,在社区划分过程中将在线社会网络视为有向加权图,通过语义网和社会化标签技术,充分结合在线社会网络丰富的语义信息和网络拓扑特征进行社区划分。ISLPA算法不需要预先设定社区数量和大小,就能实现社区发现,并能根据标签自动识别划分的社区。算法接近线性时间复杂度,具有较高的效率。通过实验表明,ISLPA算法能有效划分和标识真实在线社会网络。     

Detecting community structure in networks by representative energy

Network community has attractedmuch attention recently, but the accuracy and efficiency in finding a community structure is limited by the lower resolution of modularity. This paper presents a new method of detecting community based on representative energy. The method can divide the communities and find the representative of community simultaneously. The communities of network emerges during competing for the representative among nodes in network, thus we can sketch structure of the whole network. Without the optimizing by modularity, the community of network emerges with competing for representative among those nodes. To obtain the proximate relationships among nodes, we map the nodes into a spectral matrix. Then the top eigenvectors are weighted according to their contributions to find the representative node of a community. Experimental results show that the method is effective in detecting communities of networks.     

Detecting community structure in networks by representative energy

Network community has attractedmuch attention recently, but the accuracy and efficiency in finding a community structure is limited by the lower resolution of modularity. This paper presents a new method of detecting community based on representative energy. The method can divide the communities and find the representative of community simultaneously. The communities of network emerges during competing for the representative among nodes in network, thus we can sketch structure of the whole network. Without the optimizing by modularity, the community of network emerges with competing for representative among those nodes. To obtain the proximate relationships among nodes, we map the nodes into a spectral matrix. Then the top eigenvectors are weighted according to their contributions to find the representative node of a community. Experimental results show that the method is effective in detecting communities of networks.     

基于多标签传播的重叠社区发现优化算法

标签传播算法是一种被广泛应用的社区发现算法,该算法为网络中的每个节点分配一个初始标签,然后通过传播标签来发现复杂网络中的潜在社区,具有时间复杂度低的特点。当前基于标签传播的重叠社区发现算法存在忽略节点重要性差异、需要人为设置参数等不足。针对该类算法在重叠社区发现方面的缺陷,提出一种基于多标签传播的重叠社区发现优化算法。该算法使用K-核分解方法找出若干个社区核心节点,以这些节点为种子节点,逐层向外传播标签;在进行标签选择的时候以邻居节点标签的种类来决定重叠节点的标签个数。实验表明,该算法明显改善了社区发现的性能,提高了划分结果的稳定性和准确性。     

Network representation learning based on community-aware and adaptive random walk for overlapping community detection

The Network representation learning methods based on random walk aim to learn a low-dimensional embedding vector for each node in a network by randomly traversing the network to capture the features of nodes and edges, which is beneficial to many downstream machine learning tasks such as community detection. Most of the existing random-walk-based network representation learning algorithms emphasize the neighborhood of nodes but ignore the communities they may form and apply the same random walk strategy to all nodes without distinguishing the characteristics of different nodes. In addition, it is time-consuming to determine the most suitable random walk parameters for a given network. In this paper, we propose a novel overlapping community detection algorithm based on network representation learning which integrates community information into embedding vectors to improve the cohesion degree of similar nodes in the embedding space. First, a node-centrality-based walk strategy is designed to determine the parameters of random walk automatically to avoid the time-consuming manual selection. Second, two community-aware random walk strategies for high and low degree nodes are developed to capture the characteristics of the community centers and boundaries. The experimental results on the synthesized and real-world datasets demonstrate the effectiveness and efficiency of our algorithm on overlapping community detection compared with the state-of-the-art algorithms

     

基于节点依赖度和相似社团融合的社团结构发现算法

社团结构作为复杂网络的拓扑特性之一具有重要的理论和实践意义。提出一种基于节点依赖度和相似社团融合的社团结构发现算法,首先根据依赖度和相似度的定义将整个网络划分成若干个平均集聚系数较大的局部网络,构成网络的基础骨架社团;然后根据连接度的定义不断将社团边缘的节点和小社团吸收到相应的骨架网络中去,直到所有节点都得到准确的社团划分。算法在Zachary空手道俱乐部网络和海豚社会网络中进行了社团划分实验,并与GN算法和Newman快速算法进行了比较,结果表明该算法可以有效地划分社团边缘的模糊节点,社团划分结果具有较高的准确度。     

基于重叠社区和结构洞度的社会网络结构洞识别算法

结构洞是社会网络中的关键位置,对信息扩散起中介作用。为高效、准确地辨识具有社团结构的社会网络中占据结构洞的节点,提出了一种基于重叠社区和结构洞度的结构洞识别算法,旨在找到一组最具信息优势和控制优势的节点。基本思想是首先定位社区之间的重叠节点,然后利用节点的邻接差异和连接的社区差异衡量其非冗余性,计算出重叠节点的结构洞度,通过对结构洞度值升序排列发现占据结构洞的节点集。应用于实际数据集的实验结果表明,与网络约束系数算法、中介中心度算法、MaxD算法相比,该算法的识别准确度最高,时间复杂度最低。     

Evolutionary virus immune strategy for temporal networks based on community vitality

Preventing viruses spreading in networks is a hot topic. Existing immune strategies are mainly designed for static networks, which become ineffective for temporal networks. In this paper, we propose an evolutionary virus immune strategy for temporal networks, which takes into account the community evolution. First, we define a new metric, community vitality (CV), to quantize the evolution characteristics of communities. Second, based on the community vitality, we propose an immune strategy which selects an optimized number of initial nodes according to node influence (NI). Third, a theoretical analysis is proposed to measure the immune effect of the evolutionary immune strategy. Compared with the random immunization, the targeted immunization and the acquaintance immune strategy, we show that the proposed strategy has a much larger coverage, i.e., more nodes will have immune ability given the same number of initial immune nodes.     

一种基于增量式谱聚类的动态社区自适应发现算法

针对当前复杂网络动态社区发现的热点问题, 提出一种面向静态网络社区发现的链接相关线性谱聚类算法, 并在此基础上提出一种基于增量式谱聚类的动态社区自适应发现算法. 动态社区发现算法引入归一化图形拉普拉斯矩阵呈现复杂网络节点之间的关 系,采用拉普拉斯本征映射将节点投影到k维欧式空间.为解决离群节点影响谱聚类的效果和启发式确定复杂网络社区数量的问题, 利用提出的链接相关线性谱聚类算法发现初始时间片的社区结构, 使发现社区的过程能够以较低的时间开销自适应地挖掘复杂网络社区结构. 此后, 对于后续相邻的时间片, 提出的增量式谱聚类算法以前一时间片聚类获得的社区特征为基础, 通过调整链接相关线性谱聚类算法实现对后一时间片的增量聚类, 以达到自适应地发现复杂网络动态社区的目的. 在多个数据集的实验表明, 提出的链接相关线性谱聚类算法能够有效地检测出复杂网络中的社区结构以及基于 增量式谱聚类的动态社区自适应发现算法能够有效地挖掘网络中动态社区的演化过程.     

A vector partitioning approach to detecting community structure in complex networks

In recent years, the problem of community structure detection has attracted more and more attention and many approaches have been proposed. Recently, Newman pointed out that this issue can be transformed into the problem of constrained maximization of the assignment matrix over possible divisions of a network. He presents further that this maximization process can be written in terms of the eigenspectrum of the “modularity matrix”. On the basis of this work and the vector partition approach in computer science, we propose a kind of multiway division approach for detecting community structure of complex networks. Experimental results indicate that the algorithm works well and is effective at finding both good communities and the appropriate number of communities.     

基于染色随机游走的可重叠社区发现

社区发现是一个基础性的且被广泛研究的问题。现有的社区发现方法大多聚焦于网络拓扑结构,然而随着真实网络中实体可用属性的激增,捕获图中结构和属性的丰富交互关系来进行社区发现变得尤为必要。据此面向属性图提出了一种基于染色随机游走的可重叠社区发现算法OCDC,该算法解决了传统的基于随机游走的社区发现算法利用结构转移矩阵造成社区发现效果不佳的问题。具体地,首先利用经典的初始种子策略选出网络中差异度较大的节点,在此基础上设计种子替换策略,挖掘网络中质量更佳的种子替换路径集合对初始种子集合进行替换;其次构建结构-属性交互节点转移矩阵并执行染色随机游走过程得到高质量种子节点的染色分布向量;最后基于融合结构和属性的并行电导值对社区进行扩展。在人工网络和现实网络上的实验表明,本文提出的算法能够准确地识别属性社区并显著优于基准算法。     

基于社团多特征融合嵌入表示的时序链路预测方法

时序动态网络在静态网络基础上综合了时间属性的概念,包含了网络结构的复杂性、动态性等内涵,是研究复杂网络链路预测问题的较优思维对象,因在现实世界中具有较高应用价值而备受关注。目前大部分传统方法研究对象仍局限于静态网络,存在对网络时域演化信息利用不充分、时间复杂度较高等问题。结合社会学理论,提出一种基于社团多特征融合嵌入表示的时序链路预测方法,该方法的核心思想是通过分析网络动态演化特性,在社团范围内学习节点的嵌入表示向量,融合多特征以衡量节点间连边的生成概率。利用网络集体影响力的方法对节点和连边的权值进行计算,基于集体影响的连边权值进行社团划分,将网络划分为若干个社团子图,得到基于集体影响的相似性指标。在社团范围内,利用有偏的随机游走,结合梯度优化的Skip-gram方法获取所有节点的嵌入表示向量,得到基于社团范围游走的相似性指标。融合节点的集体影响、社团范围节点的多个中心性特征和学习到的节点表示向量,得到多特征融合的相似性指标,3 种新指标都可以用于衡量节点之间形成连边的概率。对比基于移动平均、嵌入表示、图神经网络等经典时序链路预测方法,在 6 个真实数据集上的实验结果表明,所提基于社团多特征融合的方法在 AUC评价标准下取得更优的预测性能。     

Mesoscopic analysis of networks with genetic algorithms

The detection of communities is an important problem, intensively investigated in recent years, to uncover the complex interconnections hidden in networks. In this paper a genetic based approach to discover communities in networks is proposed. The algorithm optimizes a simple but efficacious fitness function able to identify densely connected groups of nodes with sparse connections between groups. The method is efficient because the variation operators are modified to take into consideration only the actual correlations among the nodes, thus sensibly reducing the search space of possible solutions. Experiments on synthetic and real life networks show the ability of the method to successfully detect the network structure.     

基于复杂网络社区划分的网络拓扑结构可视化布局算法

许多真实的网络都可以用复杂网络的思想进行研究和解释,而社区结构是复杂网络的一个重要特征.为此,提出一种基于社区结构的网络布局算法.首先利用复杂网络社区发现算法对网络中的节点进行社区划分,并将一个社区抽象为一个节点,以社区间的关联为边构建新的网络;在此基础上,运用物理类比方法确定社区中心点的位置,并根据社区的规模确定社区的区域范围;最后运用条件择优的方式填充社区内部节点以完成网络拓扑的布局.仿真实验结果证明,该算法与传统的可视化布局算法相比,具有计算量更少、收敛速度快、结构清晰的特点,更具有实际应用的价值.     

融合拓扑势的社交网络层次化社区发现算法

社交网络的社区结构呈现层次性。针对传统凝聚式层次化社区发现算法效率不高以及生成的层次谱图复杂的问题，提出一种融合拓扑势的层次化社区发现算法，利用拓扑势场呈现的自然峰谷结构揭示社交网络社区间的层次关系。该算法搜索局部极大势值节点，并根据局部极大势值节点完成社区的初始划分；根据局部极大势值节点间的距离对初始社区进行迭代合并，直到所有社区被合并为一个社区。在真实社交网络和人工网络上的实验结果表明，该算法能够高效地发现社区的层次结构，生成的层次谱图简单直观。