Generative model for reciprocity and community detection in networks
arXiv:2012.08215 · doi:10.1103/PhysRevResearch.3.023209
Abstract
We present a probabilistic generative model and efficient algorithm to model reciprocity in directed networks. Unlike other methods that address this problem such as exponential random graphs, it assigns latent variables as community memberships to nodes and a reciprocity parameter to the whole network rather than fitting order statistics. It formalizes the assumption that a directed interaction is more likely to occur if an individual has already observed an interaction towards her. It provides a natural framework for relaxing the common assumption in network generative models of conditional independence between edges, and it can be used to perform inference tasks such as predicting the existence of an edge given the observation of an edge in the reverse direction. Inference is performed using an efficient expectation-maximization algorithm that exploits the sparsity of the network, leading to an efficient and scalable implementation. We illustrate these findings by analyzing synthetic and real data, including social networks, academic citations and the Erasmus student exchange program. Our method outperforms others in both predicting edges and generating networks that reflect the reciprocity values observed in real data, while at the same time inferring an underlying community structure. We provide an open-source implementation of the code online.
References in corpus (21)
- From Louvain to Leiden: guaranteeing well-connected communities
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- The statistical mechanics of networks
- Structure and Evolution of the World Trade Network
- The ground truth about metadata and community detection in networks
- Patterns of link reciprocity in directed networks
- An efficient and principled method for detecting communities in networks
- Structure and inference in annotated networks
- Pseudo-likelihood methods for community detection in large sparse networks
- Community detection, link prediction, and layer interdependence in multilayer networks
- Stacking Models for Nearly Optimal Link Prediction in Complex Networks
- Random graph models for dynamic networks
- Reciprocity of weighted networks
- Modeling sequences and temporal networks with dynamic community structures
- Coauthorship and Citation Networks for Statisticians
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Community detection with node attributes in multilayer networks
- Multi-species grandcanonical models for networks with reciprocity
- The impossibility of low rank representations for triangle-rich complex networks
- Community detection in networks without observing edges
- User recommendation in reciprocal and bipartite social networks -- a case study of online dating
Cited by in corpus (13)
- Inference of hyperedges and overlapping communities in hypergraphs
- Community Detection in Large Hypergraphs
- Disentangling homophily, community structure and triadic closure in networks
- Reciprocity, community detection, and link prediction in dynamic networks
- Latent Network Models to Account for Noisy, Multiply-Reported Social Network Data
- Structure and inference in hypergraphs with node attributes
- Anomaly detection and community detection in networks
- Community detection and reciprocity in networks by jointly modeling pairs of edges
- Temporal patterns of reciprocity in communication networks
- The interplay between ranking and communities in networks
- The hidden architecture of connections: How do multidimensional identities shape our social networks?
- Modeling Node Exposure for Community Detection in Networks
- Anomaly, reciprocity, and community detection in networks