一种基于信息扩散的复杂网络重叠社区发现算法

社区结构可以为网络的其他分析挖掘提供中观尺度的分析视角,在大规模复杂网络的各项研究中是一项非常重要而基础的工作。社区的重叠是真实世界网络中常见的一种现象,重叠社区结构可以更准确地描述网络中真实的结构信息,因此,复杂网络重叠社区发现具有更加突出的现实意义。在综合对比分析了当前主要的重叠社区发现算法的基础上,结合信息论的相关知识,给出了一种基于信息论的社区定义,并进一步借鉴信息传播理论,从单个节点对关于某种主题的信息的掌握程度的角度出发提出了一种复杂网络重叠社区结构发现算法。基于实际数据集的相关实验表明,与传统的社区定义和社区发现算法相比,本算法发现的重叠社区从内容角度来看具有更加明确的实际意义,并且具有较低的时间复杂度。     

Force-Based Incremental Algorithm for Mining Community Structure in Dynamic Network

Community structure is an important property of network. Being able to identify communities can provide invaluable help in exploiting and understanding both social and non-social networks. Several algorithms have been developed up till now. However, all these algorithms can work well only with small or moderate networks with vertexes of order 104. Besides, all the existing algorithms are off-line and cannot work well with highly dynamic networks such as web, in which web pages are updated frequently. When an already clustered network is updated, the entire network including original and incremental parts has to be recalculated, even though only slight changes are involved. To address this problem, an incremental algorithm is proposed, which allows for mining community structure in large-scale and dynamic networks. Based on the community structure detected previously, the algorithm takes little time to reclassify the entire network including both the original and incremental parts. Furthermore, the algorithm is faster than most of the existing algorithms such as Girvan and Newman＇s algorithm and its improved versions. Also, the algorithm can help to visualize these community structures in network and provide a new approach to research on the evolving process of dynamic networks.     

A novel multiobjective particle swarm optimization algorithm for signed network community detection

Signed graphs or networks are effective models for analyzing complex social systems. Community detection from signed networks has received enormous attention from diverse fields. In this paper, the signed network community detection problem is addressed from the viewpoint of evolutionary computation. A multiobjective optimization model based on link density is newly proposed for the community detection problem. A novel multiobjective particle swarm optimization algorithm is put forward to solve the proposed optimization model. Each single run of the proposed algorithm can produce a set of evenly distributed Pareto solutions each of which represents a network community structure. To check the performance of the proposed algorithm, extensive experiments on synthetic and real-world signed networks are carried out. Comparisons against several state-of-the-art approaches for signed network community detection are carried out. The experiments demonstrate that the proposed optimization model and the algorithm are promising for community detection from signed networks.     

基于动态有噪网络的增量社团发现算法

在动态社会网络中,诸如垃圾邮件之类的噪声会影响网络的稳定性,导致其社团结构难以被准确发现。针对该问题,提出一种采用增量结构的社团发现算法。利用相对熵处理噪声,通过改进的增量算法发现社团结构。实验结果表明,该算法针对不同动态社会网络的发现性能均优于传统动态社团发现算法,其模块度可达到0.8左右,互信息值变化也较平稳,可有效避免噪声对算法性能的影响。     

可探测社区稳定结构的局部社区发现算法

社交网络的动态变化使社区发现的精确度面临更高挑战。目前提出的大部分算法都是以寻求模块度最优解来发现社区,但往往会忽略所发现的社区结构是否稳定。根据力学平衡原理即当一个物体所受内部力和外部力平衡的条件下可达稳定状态,因此基于点的稳定性机制,判断节点来自社区内部连边数量与来自外部社区连边数量的最大值是否保持平衡,提出一种可探测稳定结构的局部社区发现算法。网络的稳定性大小与社区的结构有很大的关系,因此将网络的稳定性作为一种新的评价社区结构优良的标准。通过在真实网络和人工集成网络上进行实验对比发现提出的算法的社区结构稳定度比其他算法高,同时能发现精确度高的社区。     

基于权重信息挖掘社会网络中的隐含社团

社团结构是一种普遍存在于各类真实网络中的结构特性.挖掘网络的社团结构对于理解网络的功能与行为有着重要作用.然而,现有的各种社团挖掘算法仅仅基于网络拓扑结构信息,而忽视了蕴涵于真实社会网络边权信息中丰富的语义信息.目前普遍使用的基于模块性最大化的社团挖掘算法倾向于将小社团合并,这使得语义上丰富的小社团容易湮灭于基于拓扑结构信息所挖掘出的大社团中.而挖掘出这些隐含于大社团中的有着丰富语义内涵的小社团对于加深社会网络语义层面的理解有着重要作用.为此,提出一个接近线性复杂度的有权网络社团挖掘算法.通过充分利用权重信息,算法可以将社会网络划分为富含语义信息的粒度较细且相对较小的隐含社团.通过对基于DBLP作者合作网络的实证分析,证实了新算法的有效性和高效性.     

动态加权网络中的演化社区发现算法研究

在动态网络中发现社区结构是一个非常复杂而有意义的过程,可以更好地观察和分析网络的演化情况。针对动态加权网络中的社区发现问题,提出了一种结合历史网络社区结构的算法,叫做动态加权网络中的演化社区发现算法（ECDA）。该算法分为两步：结合历史社区和网络结构信息,计算当前时间跳的输入矩阵;然后通过该输入矩阵计算得到结合历史时间跳信息的社区划分结果。该算法有以下优点：可以自动发现动态加权网络中每个时间跳的社区结构;对网络结构的变化和社区结构的变化具有较高的敏锐性。在人工数据集和真实数据集中进行了实验,实验结果证明该算法可以有效地发现动态加权网络中的社区结构,与其他算法相比具有较好的竞争力。     

基于联合矩阵分解的动态异质网络社区发现方法

动态网络的社区发现是目前复杂网络分析领域的重要研究内容,然而现有动态网络社区发现方法主要针对同质网络,当网络包含多种异质信息时,现有方法不再适用。针对这个问题,本文提出了一个基于联合矩阵分解的动态异质网络社区发现方法,首先计算动态异质网路中各个快照图的拓扑相似度矩阵和多关系相似度矩阵,其次利用时序联合非负矩阵分解方法,约束各个时刻快照图的社区划分,最后在真实网络数据集上的实验结果表明,该算法可以有效检测出动态异质网络中潜在的社区结构。     

Community Detection Using Jaacard Similarity with SIM-Edge Detection Techniques

The structure and dynamic nature of real-world networks can be revealed by communities that help in promotion of recommendation systems. Social Media platforms were initially developed for effective communication, but now it is being used widely for extending and to obtain profit among business community. The numerous data generated through these platforms are utilized by many companies that make a huge profit out of it. A giant network of people in social media is grouped together based on their similar properties to form a community. Community detection is recent topic among the research community due to the increase usage of online social network. Community is one of a significant property of a network that may have many communities which have similarity among them. Community detection technique play a vital role to discover similarities among the nodes and keep them strongly connected. Similar nodes in a network are grouped together in a single community. Communities can be merged together to avoid lot of groups if there exist more edges between them. Machine Learning algorithms use community detection to identify groups with common properties and thus for recommendation systems, health care assistance systems and many more. Considering the above, this paper presents alternative method SimEdge-CD (Similarity and Edge between's based Community Detection) for community detection. The two stages of SimEdge-CD initially find the similarity among nodes and group them into one community. During the second stage, it identifies the exact affiliations of boundary nodes using edge betweenness to create well defined communities. Evaluation of proposed method on synthetic and real datasets proved to achieve a better accuracy-efficiency trade-of compared to other existing methods. Our proposed SimEdge-CD achieves ideal value of 1 which is higher than existing sim closure like LPA, Attractor, Leiden and walktrap techniques.     

Detecting community structure in complex networks using genetic algorithm based on object migrating automata

Community structure is an important topological feature of complex networks. Detecting community structure is a highly challenging problem in analyzing complex networks and has great importance in understanding the function and organization of networks. Up until now, numerous algorithms have been proposed for detecting community structure in complex networks. A wide range of these algorithms use the maximization of a quality function called modularity. In this article, three different algorithms, namely, MEM-net, OMA-net, and GAOMA-net, have been proposed for detecting community structure in complex networks. In GAOMA-net algorithm, which is the main proposed algorithm of this article, the combination of genetic algorithm (GA) and object migrating automata (OMA) has been used. In GAOMA-net algorithm, the MEM-net algorithm has been used as a heuristic to generate a portion of the initial population. The experiments on both real-world and synthetic benchmark networks indicate that GAOMA-net algorithm is efficient for detecting community structure in complex networks.     

Change-aware community detection approach for dynamic social networks

Community mining is one of the most popular issues in social network analysis. Although various changes may occur in a dynamic social network, they can be classified into two categories, gradual changes and abrupt changes. Many researchers have attempted to propose a method to discover communities in dynamic social networks with various changes more accurately. Most of them have assumed that changes in dynamic social networks occur gradually. This presumption for the dynamic social network in which abrupt changes may occur misleads the problem. Few methods have tried to detect abrupt changes, but they used the statistical approach which has such disadvantages as the need for a lot of snapshots. In this paper, we propose a novel method to detect the type of changes using the least information of social networks and then, apply it to a new community detection framework named change-aware model. The experimental results on different benchmark and real-life datasets confirmed that the new method and framework have improved the performance of community detection algorithms.     

节点不对称转移概率的网络社区发现算法

社区发现是当前社会网络研究领域的一个热点和难点,现有的研究方法包括：（1）优化以网络拓扑结构为基础的社区质量指标;（2）评估节点间的相似性并进行聚类;（3）根据特定网络设计相应的社区模型等.这些方法存在如下问题：（1）通用性不高,难以同时在无向网络和有向网络上发挥出好的效果;（2）无法充分利用网络的结构信息,在真实数据集上表现不佳.针对上述问题,提出一种基于节点不对称转移概率的网络社区发现算法CDATP.该算法通过分析网络拓扑结构来设计节点转移概率,并使用random walk方法评估节点对网络社区的重要性.最后,以重要性较高的节点作为核心构造网络社区.与现有的基于random walk的方法不同,CDATP为网络中节点设计的转移概率具有不对称性,并只通过节点局部转移来评估节点对社区的重要程度.通过大量仿真实验表明,CDATP在人工模拟数据集和真实数据集上均比其他最新算法有更好的表现.     

复杂网络的局部社团结构挖掘算法

挖掘复杂网络的社团结构对研究复杂系统具有重要的理论和实践意义.其中,相较于全局社团,局部社团的挖掘难度更大,相关文献更少.现有的局部社团挖掘算法大都精度较低、稳定性较差.本文提出了一个有效的局部社团挖掘算法,称为内外夹推法（Shell interception and core expansion,SICE）.算法有两个创新之处:1）将节点相似度模型引入到局部社团挖掘算法中（节点相似度模型在局部社团挖掘中较难应用）,并提出了“一次一个子图”的社团扩展模式;2）提出了一种“内外夹推”的思想.这两个创新使SICE算法摆脱了缺乏网络全局信息的困扰,并解决了以往算法的一个致命缺陷,从而使算法具有很高的精度和稳定性.通过理论分析和实验比较,证明SICE算法要远好于当前的同类算法,甚至不逊色于性能较好的全局社团挖掘算法.     

Overlapping community detection based on discrete biogeography optimization

Community detection can be used to help mine the potential information in social networks, and uncovering community structures in social networks can be regarded as clustering optimization problems. In this paper, an overlapping community detection algorithm based on biogeography optimization is proposed. Firstly, the algorithm takes the method of label propagation based on local max degree and neighborhood overlap for initial network partitioning. The preliminary partition result used to construct initial population by cloning and mutating to accelerate the algorithm’s convergence. Next, to make biogeography optimization algorithm suitable for community detection, we design problem-specific migration rules and mutation operators based on a novel affinity degree to improve the effectiveness of the algorithm. Experiments on benchmark test data, including two synthetic networks and four real-world networks, show that the proposed algorithm can achieve results with better accuracy and stability than the compared evolutionary algorithms.     

基于引力因子的加权网络重叠社区识别算法

通过挖掘大数据来识别复杂社会网络上的社区,有利于对经济、政治、人口等方面的重要问题进行定量研究,社区的识别算法已经成为当前研究的热点问题。重点研究了重叠社区识别问题,提出了基于引力因子的加权复杂网络的重叠社区识别算法GWCR。该算法首先选取万有引力因子大的节点为中心节点,将节点与中心节点之间的引力因子作为衡量标准,并将节点归入社区引力因子大于某一阈值的社区,最后通过识别重叠节点来识别重叠社区。在3个真实网络数据集上的实验结果表明,与传统的重叠社区识别算法相比,GWCR算法划分的社区的模块度较高。     

COMPARISON AND SELECTION OF OBJECTIVE FUNCTIONS IN MULTIOBJECTIVE COMMUNITY DETECTION

Detecting communities of complex networks has been an effective way to identify substructures that could correspond to important functions. Conventional approaches usually consider community detection as a single‐objective optimization problem, which may confine the solution to a particular community structure property. Recently, a new community detection paradigm is emerging: multiobjective optimization for community detection, which means simultaneously optimizing multiple criteria and obtaining a set of community partitions. The new paradigm has shown its advantages. However, an important issue is still open: what type of objectives should be optimized to improve the performance of multiobjective community detection? To exploit this issue, we first proposed a general multiobjective community detection solution (called NSGA‐Net) and then analyzed the structural characteristics of communities identified by a variety of objective functions that have been used or can potentially be used for community detection. After that, we exploited correlation relations (i.e., positively correlated, independent, or negatively correlated) between any two objective functions. Extensive experiments on both artificial and real networks demonstrate that NSGA‐Net optimizing over a pair of negatively correlated objectives usually leads to better performances compared with the single‐objective algorithm optimizing over either of the original objectives, or even to other well‐established community detection approaches.     

基于节点相似性度量的社团结构划分方法

针对复杂网络结构划分过程复杂、准确性差的问题,定义了节点全局和局部相似性衡量指标,并构建节点的相似性矩阵,提出一种基于节点相似性度量的社团结构划分算法.其基本思路是将节点(或社团)按相似性合并条件划分到同一个社团中,如果合并后的节点(或社团)仍然满足相似性合并条件,则继续合并,直到所有节点都得到准确的社团划分.实验结果表明,所提算法能成功正确地划分出真实网络中的社团结构, 性能比标签传播算法(LPA)、GN(Girvan-Newman)、CNM(Clauset-Newman-Moore)等算法优秀,能有效提高结果的准确性和鲁棒性.     

一种新的社区/动态社区优化方法

社区结构作为复杂网络的重要 拓扑特性之一,成为当前的研究热点。本文提出了一种基于边排序和模块度优化的社区发现方法。该方法首先对初始的静态网络进行稀疏化,然后在稀疏化后的网络上依据边的重要程度对边进行排序,给出了一种模块度最大化、快速边合并的社区发现方法(Fast rank base d community detection, F RCD)。在初始网络社区划分结果的基础上,将该方法推广到动态、实时社区划分上,给出了一种快速、鲁棒的动态社区划分方法(Incremental dynamic community detection, IDCD)。理论分析 表明FRCD相对于边具有线性时间复杂度。在实际 和人工网络上的实验结果均表明,本文提出的方法无论在静态网络社区划分还是在动态网络社区追踪上都优于已有方法。     

基于随机游走的改进标签传播算法

社区发现是挖掘社交网络隐藏信息的一个有用的工具，而标签传播算法（LPA）是社区发现算法中的一种常见算法，不需要任何的先验知识，且运行速度快。针对标签传播算法有很强的随机性而导致的社区发现算法结果不稳定的问题，提出了一种基于随机游走的改进标签传播算法（LPARW）。首先，根据在网络上进行随机游走确定了节点重要性的排序，从而得到节点的更新顺序；然后，遍历节点的更新序列，对每个节点将其与排序在其之前的节点进行相似性计算，若该节点与排序在其之前的节点是邻居节点且它们之间的相似性大于阈值，则将排序在其之前的节点选为种子节点；最后，将种子节点的标签传播给其余的节点，得到社区的最终划分结果。将所提算法与一些经典的标签传播算法在4个有标签的网络和5个无标签的真实网络上进行比较分析，实验结果表明所提算法在标准互信息（NMI）、调整兰德系数（ARI）和模块度等经典的评价指标上的性能均优于其余对比算法，可见该算法具有很好的社区划分效果。     

社团挖掘和话题监控的互动模型研究

社团挖掘是Web信息挖掘领域的重要应用,而话题监控是文本信息研究领域的重要应用,目前这两种技术是各自独立的。为更好地应用于互联网形成的复杂社会网络,将这两种技术结合起来研究,发现了社团和话题之间的关系,创建了社团挖掘和话题监控的静态和动态互动模型,设计了社团挖掘、话题识别以及社团跟踪算法。