Stochastic block model and exploratory analysis in signed networks

Abstract

We propose a generalized stochastic block model to explore the mesoscopic structures in signed networks by grouping vertices that exhibit similar positive and negative connection profiles into the same cluster. In this model, the group memberships are viewed as hidden or unobserved quantities, and the connection patterns between groups are explicitly characterized by two block matrices, one for positive links and the other for negative links. By fitting the model to the observed network, we can not only extract various structural patterns existing in the network without prior knowledge, but also recognize what specific structures we obtained. Furthermore, the model parameters provide vital clues about the probabilities that each vertex belongs to different groups and the centrality of each vertex in its corresponding group. This information sheds light on the discovery of the networks' overlapping structures and the identification of two types of important vertices, which serve as the cores of each group and the bridges between different groups, respectively. Experiments on a series of synthetic and real-life networks show the effectiveness as well as the superiority of our model.

12 pages, 8 figures, 2 tables. arXiv admin note: text overlap with arXiv:1110.1976 by other authors

References in corpus (28)

• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Functional cartography of complex metabolic networks
• Comparing community structure identification
• Hierarchical structure and the prediction of missing links in networks
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Quantifying social group evolution
• Multirelational Organization of Large-scale Social Networks in an Online World
• Missing and spurious interactions and the reconstruction of complex networks
• Mixture models and exploratory analysis in networks
• Community detection in networks with positive and negative links
• Fuzzy communities and the concept of bridgeness in complex networks
• Phase transition in the detection of modules in sparse networks
• Comparing Community Structure to Characteristics in Online Collegiate Social Networks
• Analysis of community structure in networks of correlated data
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• On network bipartivity
• Finding instabilities in the community structure of complex networks
• Role models for complex networks
• Currency and commodity metabolites: Their identification and relation to the modularity of metabolic networks
• Exploring the structural regularities in networks
• Modularity functions maximization with nonnegative relaxation facilitates community detection in networks
• Mesoscopic analysis of networks: applications to exploratory analysis and data clustering

Cited by in corpus (6)

• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• A Survey of Signed Network Mining in Social Media
• Signed graphs in data sciences via communicability geometry
• Assessing frustration in real-world signed networks: a statistical theory of balance
• A Hybrid Membership Latent Distance Model for Unsigned and Signed Integer Weighted Networks
• A Block-based Generative Model for Attributed Networks Embedding