Search

The purpose of community detection is to discover closely connected groups of entities in complex networks such as interest groups, proteins and vehicles in social, biological and transportation networks. Recently, autoencoders have become a popular technique to extract nonlinear relationships between nodes by learning their representation vectors through an encoder-decoder neural structure, which is beneficial to discovering communities with vague boundaries. However, most of the existing autoencoders take restoring a network's adjacency matrix as their objective, which puts emphasis on the first-order relationships between the nodes and neglects their higher-order relationships that may be more useful for community detection. In this paper, we propose a novel attentional-walk-based autoencoder (AWBA) which integrates random walk considering attentional coefficients between each pair of nodes into the encoder to mine their high-order relationships. First, the attention layers are added to the encoder to learn the influence of a node's different neighbors on it in encoding. Second, we develop a new random walk strategy that embeds the attention coefficients and the community membership of the nodes obtained by a seed-expansion-based clustering algorithm into the computation of the transition probability matrix to instill both low and high order relationships between the nodes into the representation vectors. The experimental results on synthetic and real-world networks verify the superiority of our algorithm over the baseline algorithms. [ABSTRACT FROM AUTHOR]

Community detection is an essential task in network analysis and is challenging due to the rapid growth of network scales. Recently, discovering communities from the local perspective of some specified nodes called seeds, rather than requiring the global information of the entire network, has become an alternative approach to addressing this challenge. Some seeding algorithms have been proposed in the literature for finding seeds, but many of them require an excessive amount of effort because of the global information or intensive computation involved. In our study, we formally summarize a unified framework for local seeding by considering only the local information of each node. In particular, both popular local seeding algorithms and new ones are instantiated from this unified framework by adopting different centrality metrics. We categorize these local seeding algorithms into three classes and compare them experimentally on a number of networks. The experiments demonstrate that the degree-based algorithms usually select the fewest seeds, while the denseness-based algorithms, except the one with node mass as the centrality metric, select the most seeds; using the conductance of the egonet as the centrality metric performs best in discovering communities with good quality; the core-based algorithms perform best overall considering all the evaluation metrics; and among the core-based algorithms, the one with the Jaccard index works best. The experimental results also reveal that all the seeding algorithms perform poorly in large networks, which indicates that discovering communities in large networks is still an open problem that urgently needs to be addressed. [ABSTRACT FROM AUTHOR]

Community identification refers to the process of selecting dense clusters with sparse connections to the rest of the graph. These communities naturally overlap in many social networks, while each node can participate in several communities. Revealing these structures represents an important task in network analysis. In fact, it allows to understand the features of networks. However, many community detection approaches fail to provide communities with high quality and better ground truth correspondence in reasonable execution time. The key idea of this paper is to propose a coupled-seed expansion method for the overlapping community detection. Specifically, we construct a coupled-seed by choosing a node and its most similar neighbor and then expand this coupled-seed using a fitness function that improves the identification of local communities. The overlapping modularity, the F-score and the extended normalized mutual information measures are used to evaluate the proposed algorithm. The experimental results on 10 instances of real networks and four sets of LFR networks prove that the proposed method is effective and outperforms the existing algorithms (BigClam, OSLOM, SE, Demon, UMSTMO, LC, Ego-Splitting). [ABSTRACT FROM AUTHOR]

Copyright of Journal of Harbin University of Science & Technology is the property of Journal of Harbin University of Science & Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Community plays an important role in the field of sociology, biology and especially in domains of computer science, where systems are often represented as networks. And community detection is of great importance in the domains. A community is a dense subgraph of the whole graph with more links between its members than between its members to the outside nodes, and nodes in the same community probably share common properties or play similar roles in the graph. Communities overlap when nodes in a graph belong to multiple communities. A vast variety of overlapping community detection methods have been proposed in the literature, and the local expansion method is one of the most successful techniques dealing with large networks. The paper presents a density-based seeding method, in which dense disjoint local clusters are searched and selected as seeds. The proposed method selects a seed by the total degree and density of local clusters utilizing merely local structures of the network. Furthermore, this paper proposes a novel community refining phase via minimizing the conductance of each community, through which the quality of identified communities is largely improved in linear time. Experimental results in synthetic networks show that the proposed seeding method outperforms other seeding methods in the state of the art and the proposed refining method largely enhances the quality of the identified communities. Experimental results in real graphs with ground-truth communities show that the proposed approach outperforms other state of the art overlapping community detection algorithms, in particular, it is more than two orders of magnitude faster than the existing global algorithms with higher quality, and it obtains much more accurate community structure than the current local algorithms without any priori information. [ABSTRACT FROM AUTHOR]