Assessing the relevance of node features for network structure

Abstract

Networks describe a variety of interacting complex systems in social science, biology and information technology. Usually the nodes of real networks are identified not only by their connections but also by some other characteristics. Examples of characteristics of nodes can be age, gender or nationality of a person in a social network, the abundance of proteins in the cell taking part in a protein-interaction networks or the geographical position of airports that are connected by directed flights. Integrating the information on the connections of each node with the information about its characteristics is crucial to discriminating between the essential and negligible characteristics of nodes for the structure of the network. In this paper we propose a general indicator, based on entropy measures, to quantify the dependence of a network's structure on a given set of features. We apply this method to social networks of friendships in US schools, to the protein-interaction network of Saccharomyces cerevisiae and to the US airport network, showing that the proposed measure provides information which complements other known measures.

(7 pages, 6 figures, for related matlab codes see http://nuweb.neu.edu/gbianconi/EntropyPNAS.html)

References in corpus (13)

• Uncovering the overlapping community structure of complex networks in nature and society
• Resolution limit in community detection
• Comparing community structure identification
• Hierarchical structure and the prediction of missing links in networks
• Statistical Mechanics of Community Detection
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Mixture models and exploratory analysis in networks
• Navigability of Complex Networks
• The entropy of network ensembles
• The entropy of randomized network ensembles
• Propagation of large concentration changes in reversible protein binding networks
• Extended navigability of small world networks: exact results and new insights
• Predicting protein functions with message passing algorithms

Cited by in corpus (82)

• Community detection in graphs
• The structure and dynamics of multilayer networks
• Link Prediction in Complex Networks: A Survey
• Spatial Networks
• Community detection algorithms: a comparative analysis
• Finding statistically significant communities in networks
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Limits of modularity maximization in community detection
• The ground truth about metadata and community detection in networks
• Sustaining the Internet with Hyperbolic Mapping
• A small-world of weak ties provides optimal global integration of self-similar modules in functional brain networks
• Entropy measures for complex networks: Toward an information theory of complex topologies
• Narrow scope for resolution-limit-free community detection
• Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Network resilience
• Weighted Multiplex Networks
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Tolerating the Community Detection Resolution Limit with Edge Weighting
• Designing optimal transport networks
• Spectral entropies as information-theoretic tools for complex network comparison
• Social network dynamics of face-to-face interactions
• The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
• Significant Scales in Community Structure
• Entropy of stochastic blockmodel ensembles
• Link Prediction with Node Clustering Coefficient
• Statistical significance of communities in networks
• Bayesian stochastic blockmodeling
• Social significance of community structure: Statistical view
• Me, My Echo Chamber, and I: Introspection on Social Media Polarization
• Emergence of overlap in ensembles of spatial multiplexes and statistical mechanics of spatial interacting networks ensembles
• Gibbs entropy of networks ensembles by cavity methods
• Clustering implies geometry in networks
• Entropy of dynamical social networks
• Extracting Information from Multiplex Networks
• Mesoscopic Structures Reveal the Network Between the Layers of Multiplex Datasets
• Complex Networks and Symmetry I: A Review
• The interplay of microscopic and mesoscopic structure in complex networks
• A testing based extraction algorithm for identifying significant communities in networks
• Preferential attachment in growing spatial networks
• Entropy distribution and condensation in random networks with a given degree distribution
• Complex networks embedded in space: Dimension and scaling relations between mass, topological distance and Euclidean distance
• Supersampling and network reconstruction of urban mobility
• Correlations between weights and overlap in ensembles of weighted multiplex networks
• Stochastic cycle selection in active flow networks
• Network constraints on the mixing patterns of binary node metadata
• Statistical Mechanics of Multi-Edge Networks
• Identifying overlapping communities in social networks using multi-scale local information expansion
• Generalized Rich-Club Ordering in Networks
• Improving local clustering based top-L link prediction methods via asymmetrical link clustering information
• Scale-free networks embedded in fractal space
• Discovering Network Structure Beyond Communities
• Duality between equilibrium and growing networks
• Approximate entropy of network parameters
• Information sharing in Quantum Complex Networks
• Entropy rate of non-equilibrium growing networks
• Features and heterogeneities in growing network models
• Structural Bounds on the Dyadic Effect
• Spatial effects in real networks: measures, null models, and applications
• Non-parametric resampling of random walks for spectral network clustering
• The role of adjacency matrix degeneration in maximum entropy weighted network models
• Infinite randomness critical behavior of the contact process on networks with long-range connections
• Statistical test for detecting community structure in real-valued edge-weighted graphs
• Growing homophilic networks are natural navigable small worlds
• Models, Entropy and Information of Temporal Social Networks
• Detecting the optimal number of communities in complex networks
• Entropy of labeled versus unlabeled networks
• Entropy rate of random walks on complex networks under stochastic resetting
• Hyperlink prediction via local random walks and Jensen-Shannon divergence
• Grand canonical ensembles of sparse networks and Bayesian inference
• The configuration multi-edge model: Assessing the effect of fixing node strengths on weighted network magnitudes
• Sparse power-law network model for reliable statistical predictions based on sampled data
• Tackling information asymmetry in networks: a new entropy-based ranking index
• Attributed Network Embedding via Subspace Discovery
• How to Measure Significance of Community Structure in Complex Networks
• Random walk in degree space and the time-dependent Watts-Strogatz model
• Sequential locality of graphs and its hypothesis testing
• Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
• Monochromaticity in Neutral Evolutionary Network Models
• Validation of community robustness
• A logic for networks
• Network Entropy measures applied to different systemic perturbations of cell basal state