Networks as Encodings of Social Attributes: Inference and Fundamental Limits (Research Area 10: Network Science)
Abstract
The problem of inferring latent structures in social networks has attracted significant attention in recent years. The primary example is the community detection problem, where one is interested in inferring the underlying group membership of nodes based on an observed network structure. Along with algorithmic development, recent research has focused on establishing fundamental limits on oneÕs ability to infer the communities in the first place. Results obtained for a class of generative models suggest that accurate recovery is possible in dense networks, where the average connectivity grows at least logarithmically with the number of nodes in the network. However, in sparse networks, the situation is very different, and the inference problem undergoes a sharp transition between detectable and undetectable regimes. The main objective of this research effort is to combine tools and methodologies from machine learning, statistical physics, and information theory, for addressing various aspects of statistical inference problems on networks, such as the community detection problem described above. In addition to theoretical developments and results on detectability transitions, the proposed work will lead to concrete algorithmic approaches for inferring meaningful hidden structures in networks. Those algorithms will be validated on both synthetically genera ted as well as real-world data.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 11, 2018
- Source ID
- W911NF1510259
Entities
People
- Aram Galstyan
Organizations
- Army Contracting Command
- United States Army
- University of Southern California