Assessing the relevance of node features for network structure

By Ginestra Bianconi, Paolo Pin, Matteo Marsili. 2008

175 citations recorded by the source corpus.

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 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 U.S. schools, to the protein-interaction network of Saccharomyces cerevisiae and to the U.S. airport network, showing that the proposed measure provides information that complements other known measures.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Community detection in graphs (2009, background): “Bianconi et al. proposed 72 the following indicator of clustering significance Θ~k,~q = Σ~k,~q − 〈Σ~k,π(~q)〉π√ 〈δΣ2~k,π(~q)〉π , (85) where Σ~k,~q is the entropy of the graph configurations with given degree sequence ~k and clustering ~q (with fixed numbers of inter-cluster edges A(q1, q2)), and 〈Σ~k”
The structure and dynamics of multilayer networks (2014, background): “Both the network ensembles and their entropy can be used on several inference problems to extract information from a given network [147,148].”
Hierarchical block structures and high-resolution model selection in large networks (2013, methodology): “[89] Ginestra Bianconi, Paolo Pin, and Matteo Marsili, “Assessing the relevance of node features for network structure,” Proceedings of the National Academy of Sciences 106, 11433 –11438 (2009).”
Link Prediction in Complex Networks: A Survey (2010, background): “It is known to be relevant to the existence of an airline, and the number of airlines decays with the increasing of corresponding distance [59,145].”
Network resilience (2020, background): “r, decays with exponent δ = 3 [586].”
A small world of weak ties provides optimal global integration of self-similar modules in functional brain networks (2011, background): “This precise scaling is found in the US airport network (46), where a cost limitation applies to maximize profits.”
Finding Statistically Significant Communities in Networks (2010, unknown): “Scholars have just begun to assess the issue of significance of clusters [30,31].”
Growing Homophilic Networks Are Natural Navigable Small Worlds (2015, unknown): “Power law link length distributions with α = d + 1 are encountered in real-life networks like airport connections networks[52] and functional brain networks[53, 54].”