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

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

Minimum spanning trees for community detection

A simple deterministic algorithm for community detection is provided by using two rounds of minimum spanning trees. By comparing the first round minimum spanning tree (1st-MST) with the second round spanning tree (2nd-MST) of the network, communities are detected and their overlapping nodes are also identified. To generate the two MSTs, a distance matrix is defined and computed from the adjacent matrix of the network. Compared with the resistance matrix or the communicability matrix used in community detection in the literature, the proposed distance matrix is very simple in computation. The proposed algorithm is tested on real world social networks, graphs which are failed by the modularity maximization, and the LFR benchmark graphs for community detection.     

A local fuzzy method based on “p-strong” community for detecting communities in networks

In this paper,we propose a local fuzzy method based on the idea of "p-strong" community to detect the disjoint and overlapping communities in networks.In the method,a refined agglomeration rule is designed for agglomerating nodes into local communities,and the overlapping nodes are detected based on the idea of making each community strong.We propose a contribution coefficient b_v~(ci)to measure the contribution of an overlapping node to each of its belonging communities,and the fuzzy coefficients of the overlapping node can be obtained by normalizing the b_v~(ci) to all its belonging communities.The running time of our method is analyzed and varies linearly with network size.We investigate our method on the computergenerated networks and real networks.The testing results indicate that the accuracy of our method in detecting disjoint communities is higher than those of the existing local methods and our method is efficient for detecting the overlapping nodes with fuzzy coefficients.Furthermore,the local optimizing scheme used in our method allows us to partly solve the resolution problem of the global modularity.     

Overlapping community detection using a generative model for networks

Detecting overlapping communities is a challenging task in analyzing networks, where nodes may belong to more than one community. Many present methods optimize quality functions to extract the communities from a network. In this paper, we present a probabilistic method for detecting overlapping communities using a generative model. The model describes the probability of generating a network with the model parameters, which reflect the communities in the network. The community memberships of each node are determined based on a probabilistic approach using those model parameters, whose values can be obtained by fitting the model to the network. This method has the advantage that the node participation degrees in each community are also computed. The proposed method is compared with some other community detection methods on both synthetic networks and real-world networks. The experiments show that this method is efficient at detecting overlapping communities and can provide better performance on the networks where a majority of nodes belong to more than one community.     

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.     

Adjusting from disjoint to overlapping community detection of complex networks

The investigation of community structures is one of the most important problems in the field of complex networks and has countless applications in different disciplines: biology, computer, social sciences, etc. Many community detection algorithms have been developed in various fields recently. The vast majority of these algorithms only find disjoint communities; however, in many real-world networks communities often overlap to some extent. In this paper, we propose an efficient method for adjusting these classical algorithms to match the requirement for discovering overlapping communities in complex networks, which is based on a local definition of community strength. The method can in principle be applied with any clustering algorithm. Tests on a set of computer generated and real-world networks give excellent results. In particular, we show that the method can also allow one to availably analyze the problem of unstable nodes in community detection, which is very helpful for understanding the structural properties of the networks correctly and comprehensively.     

Ant colony clustering with fitness perception and pheromone diffusion for community detection in complex networks

Community structure detection in complex networks has been intensively investigated in recent years. In this paper, we propose an adaptive approach based on ant colony clustering to discover communities in a complex network. The focus of the method is the clustering process of an ant colony in a virtual grid, where each ant represents a node in the complex network. During the ant colony search, the method uses a new fitness function to percept local environment and employs a pheromone diffusion model as a global information feedback mechanism to realize information exchange among ants. A significant advantage of our method is that the locations in the grid environment and the connections of the complex network structure are simultaneously taken into account in ants moving. Experimental results on computer-generated and real-world networks show the capability of our method to successfully detect community structures.     

Joint Detection of Community and Structural Hole Spanner of Networks in Hyperbolic Space

Community detection and structural hole spanner (the node bridging different communities) identification, revealing the mesoscopic and microscopic structural properties of complex networks, have drawn much attention in recent years. As the determinant of mesoscopic structure, communities and structural hole spanners discover the clustering and hierarchy of networks, which has a key impact on transmission phenomena such as epidemic transmission, information diffusion, etc. However, most existing studies address the two tasks independently, which ignores the structural correlation between mesoscale and microscale and suffers from high computational costs. In this article, we propose an algorithm for simultaneously detecting communities and structural hole spanners via hyperbolic embedding (SDHE). Specifically, we first embed networks into a hyperbolic plane, in which, the angular distribution of the nodes reveals community structures of the embedded network. Then, we analyze the critical gap to detect communities and the angular region where structural hole spanners may exist. Finally, we identify structural hole spanners via two-step connectivity. Experimental results on synthetic networks and real networks demonstrate the effectiveness of our proposed algorithm compared with several state-of-the-art methods.     

Eigenvectors of network complement reveal community structure more accurately

We propose a general spectral method to find communities of a network based on network complement and anti-community concepts. Analytical and numerical results show that the eigenspace of matrices corresponding to a network complement reveals the community structure of a network more accurately than the eigenspace of matrices corresponding to the network itself. It is shown that the Laplacian eigenspace is the best candidate for spectral community detection especially in networks with a heterogeneous community structure. The method is applied to some computer-generated and real-world networks with known community structures.     

Surveying network community structure in the hidden metric space

Most real-world networks from various fields share a universal topological property as community structure. In this paper, we propose a node-similarity based mechanism to explore the formation of modular networks by applying the concept of hidden metric spaces of complex networks. It is demonstrated that network community structure could be formed according to node similarity in the underlying hidden metric space. To clarify this, we generate a set of observed networks using a typical kind of hidden metric space model. By detecting and analyzing corresponding communities both in the observed network and the hidden space, we show that the values of the fitness are rather close, and the assignments of nodes for these two kinds of community structures detected based on the fitness parameter are extremely matching ones. Furthermore, our research also shows that networks with strong clustering tend to display prominent community structures with large values of network modularity and fitness.     

Community Detection in Semantic Networks: A Multi-View Approach

The semantic social network is a complex system composed of nodes, links, and documents. Traditional semantic social network community detection algorithms only analyze network data from a single view, and there is no effective representation of semantic features at diverse levels of granularity. This paper proposes a multi-view integration method for community detection in semantic social network. We develop a data feature matrix based on node similarity and extract semantic features from the views of word frequency, keyword, and topic, respectively. To maximize the mutual information of each view, we use the robustness of L21-norm and F-norm to construct an adaptive loss function. On this foundation, we construct an optimization expression to generate the unified graph matrix and output the community structure with multiple views. Experiments on real social networks and benchmark datasets reveal that in semantic information analysis, multi-view is considerably better than single-view, and the performance of multi-view community detection outperforms traditional methods and multi-view clustering algorithms.     

一类高聚类系数的加权无标度网络及其同步能力分析

针对真实世界中大规模网络都具有明显聚类效应的特点, 提出一类具有高聚类系数的加权无标度网络演化模型, 该模型同时考虑了优先连接、三角结构、随机连接和社团结构等四种演化机制. 在模型演化规则中, 以概率p增加单个节点, 以概率1–p增加一个社团. 与以往研究的不同在于新边的建立, 以概率φ在旧节点之间进行三角连接, 以概率1–φ进行随机连接. 仿真分析表明, 所提出的网络度、强度和权值分布都是服从幂律分布的形式, 且具有高聚类系数的特性, 聚类系数的提高与社团结构和随机连接机制有直接的关系. 最后通过数值仿真分析了网络演化机制对同步动态特性的影响, 数值仿真结果表明, 网络的平均聚类系数越小, 网络的同步能力越强. 关键词： 无标度网络 加权网络 聚类系数 同步能力     

复杂网络中社团结构发现的多分辨率密度模块度

现实中的许多复杂网络呈现出明显的模块性或社团性.模块度是衡量社团结构划分优劣的效益函数, 它也通常被用作社团结构探测的目标函数,但最为广泛使用的Newman-Girvan模块度却存在着分辨率限制问题,多分辨率模块度也不能克服误合并社团和误分裂社团同时存在的缺陷. 本文在网络密度的基础上提出了多分辨率的密度模块度函数, 通过实验和分析证实了该函数能够使社团结构的误划分率显著降低, 而且能够体现出网络社团结构是一个有机整体,不是各个社团的简单相加.     

Detecting overlapping communities in networks via dominant label propagation

Community detection is an important methodology for understanding the intrinsic structure and function of a realworld network.In this paper,we propose an effective and efficient algorithm,called Dominant Label Propagation Algorithm(Abbreviated as DLPA),to detect communities in complex networks.The algorithm simulates a special voting process to detect overlapping and non-overlapping community structure in complex networks simultaneously.Our algorithm is very efficient,since its computational complexity is almost linear to the number of edges in the network.Experimental results on both real-world and synthetic networks show that our algorithm also possesses high accuracies on detecting community structure in networks.     

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.     

GTIP: A Gaming-Based Topic Influence Percolation Model for Semantic Overlapping Community Detection

Community detection in semantic social networks is a crucial issue in online social network analysis, and has received extensive attention from researchers in various fields. Different conventional methods discover semantic communities based merely on users’ preferences towards global topics, ignoring the influence of topics themselves and the impact of topic propagation in community detection. To better cope with such situations, we propose a Gaming-based Topic Influence Percolation model (GTIP) for semantic overlapping community detection. In our approach, community formation is modeled as a seed expansion process. The seeds are individuals holding high influence topics and the expansion is modeled as a modified percolation process. We use the concept of payoff in game theory to decide whether to allow neighbors to accept the passed topics, which is more in line with the real social environment. We compare GTIP with four traditional (GN, FN, LFM, COPRA) and seven representative (CUT, TURCM, LCTA, ACQ, DEEP, BTLSC, SCE) semantic community detection methods. The results show that our method is closer to ground truth in synthetic networks and has a higher semantic modularity in real networks.     

Detecting community structure from coherent oscillation of excitable systems

Many networks are proved to have community structures. On the basis of the fact that the dynamics on networks are intensively affected by the related topology, in this paper the dynamics of excitable systems on networks and a corresponding approach for detecting communities are discussed. Dynamical networks are formed by interacting neurons; each neuron is described using the FHN model. For noisy disturbance and appropriate coupling strength, neurons may oscillate coherently and their behavior is tightly related to the community structure. Synchronization between nodes is measured in terms of a correlation coefficient based on long time series. The correlation coefficient matrix can be used to project network topology onto a vector space. Then by the K-means cluster method, the communities can be detected. Experiments demonstrate that our algorithm is effective at discovering community structure in artificial networks and real networks, especially for directed networks. The results also provide us with a deep understanding of the relationship of function and structure for dynamical networks.     

Robust network community detection using balanced propagation

Label propagation has proven to be an extremely fast method for detecting communities in large complex networks. Furthermore, due to its simplicity, it is also currently one of the most commonly adopted algorithms in the literature. Despite various subsequent advances, an important issue of the algorithm has not yet been properly addressed. Random (node) update orders within the algorithm severely hamper its robustness, and consequently also the stability of the identified community structure. We note that an update order can be seen as increasing propagation preferences from certain nodes, and propose a balanced propagation that counteracts for the introduced randomness by utilizing node balancers. We have evaluated the proposed approach on synthetic networks with planted partition, and on several real-world networks with community structure. The results confirm that balanced propagation is significantly more robust than label propagation, when the performance of community detection is even improved. Thus, balanced propagation retains high scalability and algorithmic simplicity of label propagation, but improves on its stability and performance.     

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.