An improved multi-objective evolutionary algorithm for simultaneously detecting separated and overlapping communities

In our previous work, a multi-objective evolutionary algorithm (MEA_CDPs) was proposed for detecting separated and overlapping communities simultaneously. However, MEA_CDPs has a couple of defects, like individuals cannot be transformed to community structure by the decoder when the quality of community structure is lower certain thresholds, many vertices with weak overlapping nature are identified as overlapping nodes, and the objective functions can not control the ratio of separated nodes to overlapping nodes. Therefore, in this paper, to overcome these defects, we improve MEA_CDPs by designing more efficient objective functions. We also extend MEA_CDPs’ capability in detecting hierarchical community structures. The improved algorithm is named as iMEA_CDPs. In the experiments, a set of computer-generated networks are first used to test the effect of parameters in iMEA_CDPs, and then four real-world networks are used to validate the performance of iMEA_CDPs. The experimental results show that iMEA_CDPs outperforms MEA_CDPs. Moreover, compared with MEA_CDPs, iMEA_CDPs can detect various kinds of overlapping and hierarchical community structures.     

基于广义后缀树的二分网络社区挖掘算法

近年来,二分网络的社区挖掘问题得到了极大的关注。提出了一种基于广义后缀树的二分网络社区挖掘算法。首先从二分网络的邻接矩阵中提取网络中每个节点的链接节点序列,然后构建广义后缀树。广义后缀树的每个节点表示二分网络的一个完全二分团,由此获取并调整完全二分团。通过引入二分团的紧密度得到初始的社区划分,最后再对孤立点进行处理以得到最终的社区划分。所提算法不仅能发现重叠社区,而且能得到一对多关系的社区。在人工数据集和真实数据集上的实验表明,所提算法能准确地识别二分网络中的社区个数,获得很好的划分效果。     

一种优化标签传播过程的重叠社区发现算法*

随着社区规模的不断扩大,基于标签传播思想的重叠社区发现算法得到较大发展。经典重叠社区发现算法虽然很好的利用了标签随机传播特性实现了重叠社区发现,但是也导致该算法输出结果很不稳定、社区生成质量较差。本文的主要贡献在于,采用最新的ClusterRank为所有节点排序降低随机性带来的结果稳定性差的弊端;引入最大社区节点数以控制最大社区节点数目防止远大于其他社区的Monster出现。采用真实数据集和人工网络验证,结果证实,改良后算法可行有效。     

重叠社区发现的两段策略

复杂网络中的社区特别是重叠社区在信息传播与推荐、舆情控制、商业营销等领域中具有重要作用。在实际的网络中,由于有些节点天然地属于多个功能团体,重叠社区的挖掘越来越受到重视。提出了一种重叠社区挖掘的两段策略算法:初始社区抽取与社区合并。在社区抽取阶段,选择网络中最大度节点及其紧密的邻居节点作为初始社区,将与此初始社区联系紧密的节点也一并加入;在社区合并阶段,如果两个社区合并之后使得模块度增加,则合并这两个社区。用包括大规模网络在内的3个实际网络对所提算法进行了测试,结果表明,该算法可有效挖掘网络中的重叠社区。     

基于核心节点扩散的有向网络重叠社团发现算法

复杂网络中的社团结构探测是当前复杂网络研究领域的一个热点问题。传统的社团划分算法主要以无向、无权网络作为分析对象,不能够适用于现实世界中各种有向网络、加权网络。在分析和研究各种社团划分算法的基础上,提出一种新的重叠社团发现算法。该算法从网络中的核心节点开始,不断合并适应度最大邻居节点,最终将网络划分为多个重叠的社团。最后,将该算法应用到两个有向网络中,实验表明该算法能够很好地划分出有向网络中的重叠社团。     

一种基于局部扩展优化的重叠社区发现算法

挖掘复杂网络的重叠社区结构对研究复杂系统具有重要的理论和实践意义。提出一种基于局部扩展优化的重叠社区识别算法。 首先基于网络节点的聚集系数筛选种子节点,选取不相关的、局部聚集系数大的种子作为初始社区;然后采用贪心策略扩展初始社区,得到局部连接紧密的自然社区;最后检测并合并相似的社区,获得高覆盖率的重叠社区结构。在人工生成网络和真实网络数据集上的实验结果表明,与现有的基于局部扩展的代表性重叠社区发现算法相比,所提算法能在稀疏程度不同的网络上发现更高质量的重叠社区。     

基于群体智能的自组织重叠社团结构分析算法

社团结构分析是复杂网络研究的一项重要内容。基于群体智能思想提出了一种自组织的重叠社团结构分析算法SO^2CSA^2。基本思想是：把网络视为一个群体,网络节点是其中的一个个具有简单智能的个体,每个个体依据定义的社团连接分数自主决定要加入的社团（可同时加入多个社团）。首先在网络中寻找一组K-派系作为初始社团结构;在此基础上,所有个体迭代地选择其社团归属,最终整个网络的社团结构将逐渐生长出来;最后对获得的社团结构进行后处理,即调整少量节点的社团归属,以提高其质量。在一组合成网络和现实世界网络上的实验表明,SO^2CSA^2发现的社团结构的质量比两种对比算法（SLPA和OSLOM）更好,尤其是在网络中重叠节点较多或节点重叠度较大的情况下,社团结构质量的提升更为明显。     

Dual modularity optimization for detecting overlapping communities in bipartite networks

Many algorithms have been designed to discover community structure in networks. These algorithms are mostly dedicated to detecting disjoint communities. Very few of them are intended to discover overlapping communities, particularly the bipartite networks have hardly been explored for the detection of such communities. In this paper, we describe a new approach which consists in forming overlapping mixed communities in a bipartite network based on dual optimization of modularity. To this end, we propose two algorithms. The first one is an evolutionary algorithm dedicated for global optimization of the Newman’s modularity on the line graph. This algorithm has been tested on well-known real benchmark networks and compared with several other existing methods of community detection in networks. The second one is an algorithm that locally optimizes the graph Mancoridis modularity, and we have adapted to a bipartite graph. Specifically, this second algorithm is applied to the decomposition of vertices, resulting from the evolutionary process, and also characterizes the overlapping communities taking into account their semantic aspect. Our approach requires a priori no knowledge on the number of communities searched in the network. We show its interest on two datasets, namely, a group of synthetic networks and real-world network whose structure is also difficult to understand.     

Community-based anomaly detection in evolutionary networks

Networks of dynamic systems, including social networks, the World Wide Web, climate networks, and biological networks, can be highly clustered. Detecting clusters, or communities, in such dynamic networks is an emerging area of research; however, less work has been done in terms of detecting community-based anomalies. While there has been some previous work on detecting anomalies in graph-based data, none of these anomaly detection approaches have considered an important property of evolutionary networks??their community structure. In this work, we present an approach to uncover community-based anomalies in evolutionary networks characterized by overlapping communities. We develop a parameter-free and scalable algorithm using a proposed representative-based technique to detect all six possible types of community-based anomalies: grown, shrunken, merged, split, born, and vanished communities. We detail the underlying theory required to guarantee the correctness of the algorithm. We measure the performance of the community-based anomaly detection algorithm by comparison to a non?Crepresentative-based algorithm on synthetic networks, and our experiments on synthetic datasets show that our algorithm achieves a runtime speedup of 11?C46 over the baseline algorithm. We have also applied our algorithm to two real-world evolutionary networks, Food Web and Enron Email. Significant and informative community-based anomaly dynamics have been detected in both cases.     

融入K-核迭代因子的重叠社区发现算法

基于局部扩展的重叠社区发现算法,利用社区的局部扩展特性可有效扩展出重叠社区,但是现有算法存在划分结果不稳定和准确性较低等问题,因此提出了一种基于[K]-核迭代因子和社区隶属度的重叠社区发现算法。该算法引用[K]-核迭代因子的思想,并且与节点密度值相结合,量化节点的影响力,找出节点影响力最大的节点,提高种子节点选择的稳定性和准确性;同时以影响力大的节点为种子节点,通过节点影响力计算得到邻接节点的社区隶属度,根据社区隶属度选择性地添加邻接节点进行社区扩展,提高社区发现的质量。在人工网络图和真实数据集上进行实验,结果表明所提的算法与现有的算法比较具有较高的稳定性和准确性。     

Identifying different community members in complex networks based on topology potential

There has been considerable interest in designing algorithms for detecting community structure in real-world complex networks. A majority of these algorithms assume that communities are disjoint, placing each vertex in only one cluster. However, in nature, it is a matter of common experience that communities often overlap and members often play multiple roles in a network topology. To further investigate these properties of overlapping communities and heterogeneity within the network topology, a new method is proposed to divide networks into separate communities by spreading outward from each local important element and extracting its neighbors within the same group in each spreading operation. When compared with the state of the art, our new algorithm can not only classify different types of nodes at a more fine-grained scale successfully but also detect community structure more effectively. We also evaluate our algorithm using the standard data sets. Our results show that it performed well not only in the efficiency of algorithm, but also with a higher accuracy of partition results.     

基于节点从属度的加权网络重叠社区划分算法

针对传统社区划分算法忽略现实世界网络特征导致社区划分准确率低的问题,提出了一种基于节点从属度的加权网络重叠社区划分算法。该算法提出加权网络模型,通过模型得到了能刻画出真实网络结构的加权网络;通过网络拓扑结构定义了核心社区,核心社区对社区划分的准确性有着重要作用。该算法计算节点与核心社区间的从属度,并与从属度阈值进行比较进行核心社区扩展,根据扩展模块度优化思想,通过不断地调整从属度阈值直到获得最优的社区结构,完成重叠社区划分。在人工网络数据集和真实世界网络数据集上与已有算法进行实验对比,实验结果验证了所提算法能够准确、有效地检测出重叠社区。     

复杂网络大数据中重叠社区检测算法

大数据时代互联网用户数量呈爆炸性增长,社交网络、电商交易网络等复杂网络规模快速发展,准确有效地检测复杂网络大数据中重叠社区结构对用户兴趣点推荐和热点传播具有重要意义。提出一种新的面向复杂网络大数据的重叠社区检测算法DOC（Detecting Overlapping Communities over complex network big data）,时间复杂度为O（nlog²（n））,算法基于模块度聚类和图计算思想应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法。相对于传统重叠节点检测算法,对每个节点分析的频率大大降低,可以在较低的算法运行时间下获得较高的识别准确率。复杂网络大数据集上的算法测试结果表明：DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法。     

True-link clustering through signaling process and subcommunity merge in overlapping community detection

To overcome the difficulty in detecting reliable overlapping communities in complex networks, “true-link” and “pseudo-link” are firstly proposed on the basis of the original network graph. Then, the “true-link” graph is obtained through the preprocessing of the original network graph. And then the line graph is partitioned by means of signaling process and single-linkage hierarchical clustering. Meanwhile, the subcommunities are merged based on the proposed similarity between communities, which eradicates the inherently redundant overlapping communities to a certain extent. Compared with other overlapping community detection algorithms, this proposed algorithm is of strong robustness and high accuracy. All the results of the experiments boil down to the conclusion that this True-link Clustering Community Detection is an overlapping community detection algorithm prevailing over others.

     

一种基于多维遗传算法的重叠社区发现方法*

社区结构的发现是社交网络分析研究的重要内容,与传统的重叠社区不同,最近的研究表明某些真实网络中在社区重叠部分要比社区内部节点间的连接更加密集,而现有的算法没有考虑此类社区结构。基于遗传算法,提出了一个新颖的方法来发现此类社区划分。为了刻画节点属于多个社区的重叠现象,首次将多维染色体和均匀块交叉算子引入到社区发现算法中。通过实验证明,提出的算法可以很好地发现社交网络中重叠和非重叠的社区结构。     

基于亲密度和吸引力的二分网络社区发现算法

社区划分是二分网络研究中的一个热门话题,针对现有的二分网络社区发现算法存在从不同节点出发社区划分准确率低的问题,提出了基于亲密度和吸引力的二分网络社区发现算法（Intimacy and Attraction Algorithm,IAA）。该算法将[U]类中的每一个节点看作一个社区,通过计算出每一个社区的亲密度和社区间的吸引力来合并社区,从而得到[U]类节点的划分,最后[V]类节点划分到已有的社区中得到完整的社区划分结果。在人工数据集和真实网络上进行分析,分别利用互信息和模块度作为评价指标,实验结果表明,IAA能够更有效挖掘二分网络社区结构,具有良好的社区划分效果。     

An efficient algorithm for community mining with overlap in social networks

Detecting communities in social networks represents a significant task in understanding the structures and functions of networks. Several methods are developed to detect disjoint partitions. However, in real graphs vertices are often shared between communities, hence the notion of overlap. The study of this case has attracted, recently, an increasing attention and many algorithms have been designed to solve it. In this paper, we propose an overlapping communities detecting algorithm called DOCNet (Detecting overlapping communities in Networks). The main strategy of this algorithm is to find an initial core and add suitable nodes to expand it until a stopping criterion is met. Experimental results on real-world social networks and computer-generated artificial graphs demonstrate that DOCNet is efficient and highly reliable for detecting overlapping groups, compared with four newly known proposals.     

利用改进蚁群算法的重叠社团检测分析方法

针对重叠社团检测准确率提升问题,提出了一种基于改进蚁群算法的新型重叠社团检测算法。该算法包含位置初始化、运动和后处理三个阶段,分别通过初始位置识别与标签列表存储、基于节点间相似度的启发式信息重定义、合作保持标签列表等方式,使算法在合成数据集与现实世界数据集中的重叠社团与节点检测方面具有更好的性能。实验结果表明,在合成网络与现实世界网络平台上使用不同检测算法,所提出的方法对重叠社团与重叠节点的检测准确率较传统检测方法来说更高,因而对重叠社区检测问题求解与理解网络功能结构具有重要的参考与借鉴意义。     

一种新的基于标签传播的复杂网络重叠社区识别算法

针对现有基于标签传播的复杂网络重叠社区识别方法所存在的社区识别精度不稳定,以及随机性较强等缺陷,提出一种新的基于标签传播的复杂网络重叠社区识别算法NOCDLP(a novel algorithm for overlapping community detection based on label propagation).该算法首先搜索网络中若干以度较高节点为中心的完全子图,并以这些完全子图为起点进行标签传播;其次通过分析节点与社区连接强度以及社区接纳某节点后的社区内部连接紧密度情况给出节点归属社区强度函数,以此作为标签传播的依据提高社区的识别精度;再次,在标签传播过程中,NOCDLP算法设置标签传播控制标记,以避免标签传播算法随机性较强的缺陷;最后,在已形成的社区中通过整理重叠节点获得更准确的重叠社区结构.算法在人工网络与真实网络中完成测试,同时与多个经典算法进行对比分析,实验结果验证了NOCDLP算法是有效的、可行的.     

Overlapping community detection in social networks using coalitional games

Community detection is a significant research problem in various fields such as computer science, sociology and biology. The singular characteristic of communities in social networks is the multimembership of a node resulting in overlapping communities. But dealing with the problem of overlapping community detection is computationally expensive. The evolution of communities in social networks happens due to the self-interest of the nodes. The nodes of the social network acts as self-interested players, who wish to maximize their benefit through interactions in due course of community formation. Game theory provides a systematic framework tox capture the interactions between these selfish players in the form of games. In this paper, we propose a Community Detection Game (CDG) that works under the cooperative game framework. We develop a greedy community detection algorithm that employs Shapley value mechanism and majority voting mechanism in order to disclose the underlying community structure of the given network. Extensive experimental evaluation on synthetic and real-world network datasets demonstrates the effectiveness of CDG algorithm over the state-of-the-art algorithms.