Detecting community structure using label propagation with weighted coherent neighborhood propinquity

Community detection has become an important methodology to understand the organization and function of various real-world networks. The label propagation algorithm (LPA) is an almost linear time algorithm proved to be effective in finding a good community structure. However, LPA has a limitation caused by its one-hop horizon. Specifically, each node in LPA adopts the label shared by most of its one-hop neighbors; much network topology information is lost in this process, which we believe is one of the main reasons for its instability and poor performance. Therefore in this paper we introduce a measure named weighted coherent neighborhood propinquity (weighted-CNP) to represent the probability that a pair of vertices are involved in the same community. In label update, a node adopts the label that has the maximum weighted-CNP instead of the one that is shared by most of its neighbors. We propose a dynamic and adaptive weighted-CNP called entropic-CNP by using the principal of entropy to modulate the weights. Furthermore, we propose a framework to integrate the weighted-CNP in other algorithms in detecting community structure. We test our algorithm on both computer-generated networks and real-world networks. The experimental results show that our algorithm is more robust and effective than LPA in large-scale networks.     

Detecting community structure using label propagation with consensus weight in complex network

Community detection is a fundamental work to analyse the structural and functional properties of complex networks.The label propagation algorithm(LPA) is a near linear time algorithm to find a good community structure. Despite various ubsequent advances, an important issue of this algorithm has not yet been properly addressed. Random update orders within the algorithm severely hamper the stability of the identified community structure. In this paper, we executed the asic label propagation algorithm on networks multiple times, to obtain a set of consensus partitions. Based on these onsensus partitions, we created a consensus weighted graph. In this consensus weighted graph, the weight value of the dge was the proportion value that the number of node pairs allocated in the same cluster was divided by the total number f partitions. Then, we introduced consensus weight to indicate the direction of label propagation. In label update steps,y computing the mixing value of consensus weight and label frequency, a node adopted the label which has the maximum mixing value instead of the most frequent one. For extending to different networks, we introduced a proportion parameter o adjust the proportion of consensus weight and label frequency in computing mixing value. Finally, we proposed an pproach named the label propagation algorithm with consensus weight(LPAcw), and the experimental results showed that he LPAcw could enhance considerably both the stability and the accuracy of community partitions.     

Overlapping Community Detection Based on Membership Degree Propagation

A community in a complex network refers to a group of nodes that are densely connected internally but with only sparse connections to the outside. Overlapping community structures are ubiquitous in real-world networks, where each node belongs to at least one community. Therefore, overlapping community detection is an important topic in complex network research. This paper proposes an overlapping community detection algorithm based on membership degree propagation that is driven by both global and local information of the node community. In the method, we introduce a concept of membership degree, which not only stores the label information, but also the degrees of the node belonging to the labels. Then the conventional label propagation process could be extended to membership degree propagation, with the results mapped directly to the overlapping community division. Therefore, it obtains the partition result and overlapping node identification simultaneously and greatly reduces the computational time. The proposed algorithm was applied to a synthetic Lancichinetti–Fortunato–Radicchi (LFR) dataset and nine real-world datasets and compared with other up-to-date algorithms. The experimental results show that our proposed algorithm is effective and outperforms the comparison methods on most datasets. Our proposed method significantly improved the accuracy and speed of the overlapping node prediction. It can also substantially alleviate the computational complexity of community structure detection in general.     

LPA-MNI: An Improved Label Propagation Algorithm Based on Modularity and Node Importance for Community Detection

Community detection is of great significance in understanding the structure of the network. Label propagation algorithm (LPA) is a classical and effective method, but it has the problems of randomness and instability. An improved label propagation algorithm named LPA-MNI is proposed in this study by combining the modularity function and node importance with the original LPA. LPA-MNI first identify the initial communities according to the value of modularity. Subsequently, the label propagation is used to cluster the remaining nodes that have not been assigned to initial communities. Meanwhile, node importance is used to improve the node order of label updating and the mechanism of label selecting when multiple labels are contained by the maximum number of nodes. Extensive experiments are performed on twelve real-world networks and eight groups of synthetic networks, and the results show that LPA-MNI has better accuracy, higher modularity, and more reasonable community numbers when compared with other six algorithms. In addition, LPA-MNI is shown to be more robust than the traditional LPA algorithm.     

Growth curve based label propagation algorithm for community detection

How to better and faster identify the community structure is a hot issue in complex networks. During the past decades, various attempts have been made to solve this issue. Amongst them, without doubt, label propagation algorithm (LPA) is one of the most satisfying answers, especially for large-scale networks. However, it has one major flaw that when the community structure is not clear enough, a monster community tends to form. To address this issue, we set a growth curve for communities, gradually increasing from a low capacity to a higher capacity over time. Further, we improve the mechanism of label choosing for small communities to escape from local maximum. The experimental results on both synthetic and real networks demonstrate that our algorithm not only enhances the detection ability of the traditional label propagation algorithm, but also improves the quality of the identified communities.     

Efficient algorithm based on neighborhood overlap for community identification in complex networks

Community structure is an important feature in many real-world networks. Many methods and algorithms for identifying communities have been proposed and have attracted great attention in recent years. In this paper, we present a new approach for discovering the community structure in networks. The novelty is that the algorithm uses the strength of the ties for sorting out nodes into communities. More specifically, we use the principle of weak ties hypothesis to determine to what community the node belongs. The advantages of this method are its simplicity, accuracy, and low computational cost. We demonstrate the effectiveness and efficiency of our algorithm both on real-world networks and on benchmark graphs. We also show that the distribution of link strength can give a general view of the basic structure information of graphs.     

Community detection in social networks based on improved Label Propagation Algorithm and balanced link density

Nowadays, community detection has been raised as one of the key research areas in the online social networks mining. One of the most common algorithms in this field is label propagation algorithm (LPA). Even though the LPA method has advantages such as simplicity in understanding and implementation, as well as linear time complexity, it has an important disadvantage of the uncertainty and instability in outcomes, that is, the algorithm detects and reports different combinations of communities in each run. This problem originates from the nature of random selection in the LPA method. In this paper, a novel method is proposed based on the LPA method and the inherent structure, that is, link density feature, of the input network. The proposed method uses a sensitivity parameter (balance parameter); by choosing the appropriate values for it, the desired qualities of the identified communities can be achieved. The proposed method is called Balanced Link Density-based Label Propagation (BLDLP). In comparison with the basic LPA, the proposed method has an advantage of certainty and stability in the output results, whereas its time complexity is still comparable with the basic LPA and of course lowers than many other approaches. The proposed method has been evaluated on real-world known datasets, such as the Facebook social network and American football clubs, and by comparing it with the basic LPA, the effectiveness of the proposed method in terms of the quality of the communities found and the time complexity has been shown.     

A fast and efficient heuristic algorithm for detecting community structures in complex networks

Community structure is an important property of complex networks. How to detect the communities is significant for understanding the network structure and to analyze the network properties. Many algorithms, such as K-L and GN, have been proposed to detect community structures in complex networks. According to daily experience, a community should have many nodes and connections. Based on these principles and existing researches, a fast and efficient algorithm for detecting community structures in complex networks is proposed in this paper. The key strategy of the algorithm is to mine a node with the closest relations with the community and assign it to this community. Four real-world networks are used to test the performance of the algorithm. Experimental results demonstrate that the algorithm proposed is rather efficient for detecting community structures in complex networks.     

Detecting community structure in complex networks via node similarity

The detection of the community structure in networks is beneficial to understand the network structure and to analyze the network properties. Based on node similarity, a fast and efficient method for detecting community structure is proposed, which discovers the community structure by iteratively incorporating the community containing a node with the communities that contain the nodes with maximum similarity to this node to form a new community. The presented method has low computational complexity because of requiring only the local information of the network, and it does not need any prior knowledge about the communities and its detection results are robust on the selection of the initial node. Some real-world and computer-generated networks are used to evaluate the performance of the presented method. The simulation results demonstrate that this method is efficient to detect community structure in complex networks, and the ZLZ metrics used in the proposed method is the most suitable one among local indices in community detection.     

基于混沌神经网络的盲检测改进新算法

针对Hopfield神经网络的多起点问题,提出了一种新的基于混沌神经网络的盲信号检测算法,实现了二进制移相键控信号盲检测.据此进一步提出双sigmoid混沌神经网络模型,构造了新的能量函数,且证明了该模型的稳定性,并对网络参数进行配置.仿真实验表明:混沌神经网络能够避免局部极小点且具备较强的抗噪性能,双sigmoid混沌神经网络则继承了其所有的优点,且其收敛速度更快,仅需更短的接收数据即可到达全局真实平衡点,从而降低了算法的计算复杂度,减少了运行时间.     

Detecting communities in clustered networks based on group action on set

In this paper, we propose a well targeted algorithm (GAS algorithm) for detecting communities in high clustered networks by presenting group action technology on community division. During the processing of this algorithm, the underlying community structure of a clustered network emerges simultaneously as the corresponding partition of orbits by the permutation groups acting on the node set are achieved. As the derivation of the orbit partition, an algebraic structure r-cycle can be considered as the origin of the community. To be a priori estimation for the community structure of the algorithm, the community separability is introduced to indicate whether a network has distinct community structure. By executing the algorithm on several typical networks and the LFR benchmark, it shows that this GAS algorithm can detect communities accurately and effectively in high clustered networks. Furthermore, we compare the GAS algorithm and the clique percolation algorithm on the LFR benchmark. It is shown that the GAS algorithm is more accurate at detecting non-overlapping communities in clustered networks. It is suggested that algebraic techniques can uncover fresh light on detecting communities in complex networks.     

A brief study on coevolution of Ising dynamics

Community structure appears to be an intrinsic property of many complex real-world networks. However, recent work shows that real-world networks reveal even more sophisticated modules than classical cohesive (link-density) communities. In particular, networks can also be naturally partitioned according to similar patterns of connectedness among the nodes, revealing link-pattern communities. We here propose a propagation based algorithm that can extract both link-density and link-pattern communities, without any prior knowledge of the true structure. The algorithm was first validated on different classes of synthetic benchmark networks with community structure, and also on random networks. We have further applied the algorithm to different social, information, technological and biological networks, where it indeed reveals meaningful (composites of) link-density and link-pattern communities. The results thus seem to imply that, similarly as link-density counterparts, link-pattern communities appear ubiquitous in nature and design.     

A game theoretic algorithm to detect overlapping community structure in networks

Community detection can be used as an important technique for product and personalized service recommendation. A game theory based approach to detect overlapping community structure is introduced in this paper. The process of the community formation is converted into a game, when all agents (nodes) cannot improve their own utility, the game process will be terminated. The utility function is composed of a gain and a loss function and we present a new gain function in this paper. In addition, different from choosing action randomly among join, quit and switch for each agent to get new label, two new strategies for each agent to update its label are designed during the game, and the strategies are also evaluated and compared for each agent in order to find its best result. The overlapping community structure is naturally presented when the stop criterion is satisfied. The experimental results demonstrate that the proposed algorithm outperforms other similar algorithms for detecting overlapping communities in networks.     

基于联合矩阵分解的节点多属性网络社团检测

发现复杂网络中的社团结构在社会网络、生物组织网络和在线网络等复杂网络中具备十分重要的意义. 针对社交媒体网络的社团检测通常需要利用两种信息源: 网络拓扑结构特征和节点属性特征, 丰富的节点内容属性信息为社团检测的增加了灵活性和挑战. 传统方法是要么仅针对这两者信息之一进行单独挖掘, 或者将两者信息得到的社团结果进行线性叠加判决, 不能有效进行信息源的融合. 本文将节点的多维属性特征作为社团划分的一种有效协同学习项进行研究, 将两者信息源进行融合分析, 提出了一种基于联合矩阵分解的节点多属性网络社团检测算法CDJMF, 提高了社团检测的有效性和鲁棒性. 实验表明, 本文所提的方法能够有效利用节点的属性信息指导社团检测, 具备更高的社团划分质量.     

Advanced modularity-specialized label propagation algorithm for detecting communities in networks

A modularity-specialized label propagation algorithm (LPAm) for detecting network communities was recently proposed. This promising algorithm offers some desirable qualities. However, LPAm favors community divisions where all communities are similar in total degree and thus it is prone to get stuck in poor local maxima in the modularity space. To escape local maxima, we employ a multistep greedy agglomerative algorithm (MSG) that can merge multiple pairs of communities at a time. Combining LPAm and MSG, we propose an advanced modularity-specialized label propagation algorithm (LPAm+). Experiments show that LPAm+ successfully detects communities with higher modularity values than ever reported in two commonly used real-world networks. Moreover, LPAm+ offers a fair compromise between accuracy and speed.     

Detection of community overlap according to belief propagation and conflict

Most existing methods for detection of community overlap cannot balance efficiency and accuracy for large and densely overlapping networks. To quickly identify overlapping communities for such networks, we propose a new method that uses belief propagation and conflict (PCB) to occupy communities. We first identify triangles with maximal clustering coefficients as seed nodes and sow a new type of belief to the seed nodes. Then the beliefs explore their territory by occupying nodes with high assent ability. The beliefs propagate their strength along the graph to consolidate their territory, and conflict with each other when they encounter the same node simultaneously. Finally, the node membership is judged from the belief vectors. The PCB time complexity is nearly linear and its space complexity is linear. The algorithm was tested in extensive experiments on three real-world social networks and three computer-generated artificial graphs. The experimental results show that PCB is very fast and highly reliable. Tests on real and artificial networks give excellent results compared with three newly proposed overlapping community detection algorithms.     

变时延移动Ad-Hoc网络容量非合作规划博弈模型的渐近稳定性

移动Ad-Hoc网络容量的稳定性是保证其服务质量的关键性质之一.本文提出一种新颖的考虑时变传播时延的非合作规划博弈移动Ad-Hoc网络容量分析模型稳定性控制技术.首先求得加入时变传播时延项的非合作规划博弈移动Ad-Hoc网络容量分析模型的源节点发送流量速率演化方程组—–一类非线性时变时滞微分方程组,在此基础上采用描述器技术结合线性矩阵不等式技术得到该模型的渐进稳定性准则,并设计了模型稳定性控制的迭代算法.由于是基于等价模型变换,所提出的渐近稳定性判别准则具有较小的保守性.仿真实验验证了本算法的有效性.本建模与分析方法虽以具体的非合作规划博弈移动Ad-Hoc网络容量分析模型为例,但其可以应用于一般的移动Ad-Hoc网络容量稳定性控制问题.     

Fuzzy modularity and fuzzy community structure in networks

To find the fuzzy community structure in a complex network, in which each node has a certain probability of belonging to a certain community, is a hard problem and not yet satisfactorily solved over the past years. In this paper, an extension of modularity, the fuzzy modularity is proposed, which can provide a measure of goodness for the fuzzy community structure in networks. The simulated annealing strategy is used to maximize the fuzzy modularity function, associating with an alternating iteration based on our previous work. The proposed algorithm can efficiently identify the probabilities of each node belonging to different communities with random initial fuzzy partition during the cooling process. An appropriate number of communities can be automatically determined without any prior knowledge about the community structure. The computational results on several artificial and real-world networks confirm the capability of the algorithm.     

有限步传播范围期望指标判别节点传播影响力

在线社交网络逐渐成为人们不可或缺的重要工具,识别网络中具有高影响力的节点作为初始传播源,在社会感知与谣言控制等方面具有重要意义.本文基于独立级联模型,给出了一个描述有限步传播范围期望的指标-传播度,并设计了一种高效的递推算法.该指标在局部拓扑结构信息的基础上融合了传播概率对影响力进行刻画,能够较好地反映单个节点的传播影响力.对于多传播源影响力极大化问题,本文提出了一种基于传播度的启发式算法-传播度折扣算法,使得多个传播源的联合影响力最大.最后,将上述方法应用到三个真实网络中,与经典指标和方法相比,该方法不需要知道网络的全局结构信息,而是充分了利用网络的局部结构信息,可以较快地筛选出高传播影响力的传播源.