Node attributes and edge structure for large-scale big data network analytics and community detection

Abstract

Identifying network communities is one of the most important tasks when analyzing complex networks. Most of these networks possess a certain community structure that has substantial importance in building an understanding regarding the dynamics of the large-scale network. Intriguingly, such communities appear to be connected with unique spectral property of the graph Laplacian of the adjacency matrix and we exploit this connection by using modified relationship between Laplacian and adjacency matrix. We propose modularity optimization based on a greedy agglomerative method, coupled with fast unfolding of communities in large-scale networks using Louvain community finding method. Our proposed modified algorithm is linearly scalable for efficient identification of communities in huge directed/undirected networks. The proposed algorithm shows great performance and scalability on benchmark networks in simulations and successfully recovers communities in real network applications. In this paper, we develop communities from node attributes and edge structure. New modified algorithm statistically models the interaction between the network structure and the node attributes which leads to more accurate community detection as well as helps for identifying robustness of the network structure. We also show that any community must contain a dense Erdos-Renyi (ER) subgraph. We carried out comparisons of the Chung and Lu (CL) and Block Two-Level Erdos-Renyi (BTER) models with four real-world data sets. Results demonstrate that it accurately captures the observable properties of many real-world networks.