Search

Community evolution remains a heavily researched and challenging area in the analysis of dynamic complex network structures. Currently, the primary limitation of traditional event-based approaches for community evolution analysis is the lack of strict constraint conditions for distinguishing evolutionary events, which entails that as the cardinality of discovered events increases, so does the number of redundant events. Another limitation of existing approaches is the lack of consideration for weak events. Weak events can be generated by small changes in communities, which are empirically prevalent, and are typically not captured by traditional events. To manage these two aforementioned limitations, this research aims to formalize a weak and strong events-based framework, which includes the following newly discovered events: “weak shrink,” “weak expand,” “weak merge,” and “weak splity” predicated on the community overlapping degree and community degree membership, this article refines these traditional strong events, as well as new constraints for weak events. In addition, a community evolution mining framework, which is based on both strong and weak events, is proposed and denoted by a weak-event-based community evolution method (WECEM). The framework can be summarized by the following: 1) communities in complex networks with adjacent time-stamps are compared to determine the community overlapping degree and community membership degree; 2) the values of the community overlapping degree and membership degree meet the definition of events; and 3) weak events are effectively identified. Extensive experimental results, on real and synthetic data sets consisting of dynamic complex networks and online social networks, demonstrate that WECEM is able to identify weak events more effectively than traditional frameworks. Specifically, WECEM outperforms traditional frameworks by 22.9% in the number of discovered strong events. The detection accuracy of evolutionary events is approximately 12.2% higher than that of traditional event-based frameworks. It is also worth noting that, as the cardinality of the data grows, the proposed framework, when compared with traditional frameworks, can more effectively, and efficiently, mine large-scale complex networks. [ABSTRACT FROM AUTHOR]

In recent years, due to the rise of social, biological, and other rich content graphs, several novel community detection methods using structure and node attributes have been proposed. Moreover, nodes in a network are naturally characterized by multiple community memberships and there is growing interest in overlapping community detection algorithms. In this paper, we design a weighted vertex interaction model based on distance dynamics to divide the network, furthermore, we propose a distance Dynamics‐based Overlapping Semantic Community detection algorithm(DOSC) for node‐attribute networks. The method is divided into three phases: Firstly, we detect local single‐attribute subcommunities in each attribute‐induced graph based on the weighted vertex interaction model. Then, a hypergraph is constructed by using the subcommunities obtained in the previous step. Finally, the weighted vertex interaction model is used in the hypergraph to get global semantic communities. Experimental results in real‐world networks demonstrate that DOSC is a more effective semantic community detection method compared with state‐of‐the‐art methods. [ABSTRACT FROM AUTHOR]

Community structures are very common in complex networks. Detecting these communities is important for understanding the hidden features of networks. Besides, each community usually has one leader, which presents its significant influence over the whole community. However, most existing methods just focus on the problem of graph clustering, ignoring the role of community leaders. To solve this problem, in this paper, we propose a novel leader-aware community detection algorithm, which can find community structures as well as leaders of each community. This algorithm measures the leadership of each node and lets each one adhere to its local leader, forming dependence trees. Once all dependence trees are definitely settled, the community structures emerge because one tree actually is a cluster. Additionally, each root node of the tree is exactly the leader of corresponding community. This method can quickly determine the belonging of each node. Experimental results on real-world and benchmark networks demonstrate the effectiveness and the efficiency of our algorithm compared with other state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

Community detection plays a significant role in understanding the essence of a network. A recently proposed algorithm Attractor, which is based on distance dynamics, can spot communities effectively, but it depends on a cohesion parameter. Moreover, no efficient way is provided to find an optimal cohesion parameter setting. In this paper, we propose a parameter-free community detection algorithm by synchronizing distances iteratively. In each iteration, the distance of each edge will change dynamically according to the effect generated by its related neighbours. Several iterations later, distances between vertices belonging to the same community will synchronize to 0, while distances between vertices not in the same community will synchronize to 1. Besides, merging and division strategies are built up in the process of community detection. Experiments on both real-world and synthetic networks demonstrate benefits of our method compared to the baseline methods. [ABSTRACT FROM AUTHOR]

Clustering is an important technique for mining the intrinsic community structures in networks. The density-based network clustering method is able to not only detect communities of arbitrary size and shape, but also identify hubs and outliers. However, it requires manual parameter specification to define clusters, and is sensitive to the parameter of density threshold which is difficult to determine. Furthermore, many real-world networks exhibit a hierarchical structure with communities embedded within other communities. Therefore, the clustering result of a global parameter setting cannot always describe the intrinsic clustering structure accurately. In this paper, we introduce a novel density-based network clustering method, called graph-skeleton-based clustering (gSkeletonClu). By projecting an undirected network to its core-connected maximal spanning tree, the clustering problem can be converted to detect core connectivity components on the tree. The density-based clustering of a specific parameter setting and the hierarchical clustering structure both can be efficiently extracted from the tree. Moreover, it provides a convenient way to automatically select the parameter and to achieve the meaningful cluster tree in a network. Extensive experiments on both real-world and synthetic networks demonstrate the superior performance of gSkeletonClu for effective and efficient density-based clustering. [ABSTRACT FROM AUTHOR]

The investigation of community structure in networks has aroused great interest in multiple disciplines. One of the challenges is to find local communities from a starting vertex in a network without global information about the entire network. Many existing methods tend to be accurate depending on a priori assumptions of network properties and predefined parameters. In this paper, we introduce a new quality function of local community and present a fast local expansion algorithm for uncovering communities in large-scale networks. The proposed algorithm can detect multiresolution community from a source vertex or communities covering the whole network. Experimental results show that the proposed algorithm is efficient and well-behaved in both real-world and synthetic networks. [ABSTRACT FROM AUTHOR]

Community search is individualized and targeted, which identifies local communities containing query nodes and meeting specific conditions only according to users. Community search is only interested in communities that satisfy the designated criteria, and has a wide range of application scenarios in the real world. Traditional community search only uses the topology information, without considering the impact of node attributes information. And many existing algorithms can only deal with a single query node. Therefore, this paper defines the attribute community search problem of multiple query nodes on attribute graphs, which utilizes the edge connectivity as the structural tightness constraint and designs an attribute function as the attribute tightness constraint. To solve this problem, we design a framework that firstly finds the maximum k edge connected-component containing query as a candidate subgraph, then iteratively deletes the node with the least contribution to the attribute function from the candidate subgraph and adjusts the subgraph according to the structural constraints. We also design the attribute Steiner distance that synthesizes the structural information and attribute information, and propose an efficient heuristic expansion algorithm based on distance. The experimental results on several datasets show our proposed methods can find the community containing all query nodes with high tightness of structure and homogeneity of attributes. [ABSTRACT FROM AUTHOR]