A wealth of evidence shows that real-world networks are endowed with the small-world property, i.e., that the maximal distance between any two of their nodes scales logarithmically rather than linearly with their size. In addition, most social networks are organized so that no individual is more than six connections apart from any other, an empirical regularity known as the six degrees of separation. Why social networks have this ultrasmall-world organization, whereby the graph’s diameter is independent of the network size over several orders of magnitude, is still unknown. We show that the “six degrees of separation” is the property featured by the equilibrium state of any network where individuals weigh between their aspiration to improve their centrality and the costs incurred in forming and maintaining connections. We show, moreover, that the emergence of such a regularity is compatible with all other features, such as clustering and scale-freeness, that normally characterize the structure of social networks. Thus, our results show how simple evolutionary rules of the kind traditionally associated with human cooperation and altruism can also account for the emergence of one of the most intriguing attributes of social networks.
We explore the metric structure of networks with higher-order interactions and introduce a novel definition of distance for hypergraphs that extends the classic methods reported in the literature. The new metric incorporates two critical factors: (1) the inter-node distance within each hyperedge, and (2) the distance between hyperedges in the network. As such, it involves the computation of distances in a weighted line graph of the hypergraph. The approach is illustrated with several ad hoc synthetic hypergraphs, where the structural information unveiled by the novel metric is highlighted. Moreover, the method’s performance and effectiveness are shown through computations on large real-world hypergraphs, which indeed reveal new insights into the structural features of networks beyond pairwise interactions. Namely, using the new distance measure, we generalize the definitions of efficiency, closeness and betweenness centrality for the case of hypergraphs. Comparing the values of these generalized measures with their analogs calculated for the hypergraph clique projections, we show that our measures provide significantly different assessments on the characteristics (and roles) of the nodes from the information-transferability point of view. The difference is brighter for hypergraphs in which hyperedges of large sizes are frequent, and nodes relating to these hyperedges are rarely connected by other hyperedges of smaller sizes.
The concept of distance is a fundamental idea in graphs and hypergraphs. However, its extension to weighted hypergraphs is challenging, since it may result in inconsistencies, especially if the weights are arbitrarily assigned to the hyperedges. We address this challenge by proposing a general distance measure for weighted hypergraphs. Our measure is well-defined, and it reduces to the classic graph distance if the edges in the hypergraph are all pairwise links. We demonstrate the applicability of our definition by analyzing a number of real-world higher-order datasets, including the network of preprints in the arXiv repository, for which we choose the weights in a way that reflects the notion of cognitive distance, which measures the conceptual remoteness between fields. Our results demonstrate that, when higher-order edges cannot be neglected, the use of a full hypergraph measure is necessary to avoid the information loss that would result from commonly used approaches, such as clique projection.
We introduce a method for assessing the robustness of community detection and apply it to a world input-output network (WION) to obtain economically plausible results. This method enabled us to rank communities in the WION in terms of their robustness and stability. The algorithmic assignment variability index proposed in this study is shown to have predictive power in terms of forthcoming community rearrangement. We also provide several new approaches for identifying key economic communities. These approaches are based on the application of several centrality measures to a synthetic network in which nodes represent WION communities. Using these methods, we show that in 2000–2014, United States and Japan-centered communities demonstrated decreasing trends, while the importance of the China-centered community predominantly increased. A notable feature of the Germany-centered community rank evolution is that its influence grew only as a result of the inclusion of the Netherlands and Belgium in 2013.