A deluge of new data on real-world networks suggests that interactions among system units are not limited to pairs, but often involve a higher number of nodes. To properly encode higher-order interactions, richer mathematical frameworks such as hypergraphs are needed, where hyperedges describe interactions among an arbitrary number of nodes. Here we systematically investigate higher-order motifs, defined as small connected subgraphs in which vertices may be linked by interactions of any order, and propose an efficient algorithm to extract complete higher-order motif profiles from empirical data. We identify different families of hypergraphs, characterized by distinct higher-order connectivity patterns at the local scale. We also propose a set of measures to study the nested structure of hyperedges and provide evidences of structural reinforcement, a mechanism that associates higher strengths of higher-order interactions for the nodes that interact more at the pairwise level. Our work highlights the informative power of higher-order motifs, providing a principled way to extract higher-order fingerprints in hypergraphs at the network microscale.
Recent empirical evidence has shown that in many real-world systems, successfully represented as networks, interactions are not limited to dyads, but often involve three or more agents at a time. These data are better described by hypergraphs, where hyperlinks encode higher-order interactions among a group of nodes. In spite of the extensive literature on networks, detecting informative hyperlinks in real world hypergraphs is still an open problem. Here we propose an analytic approach to filter hypergraphs by identifying those hyperlinks that are over-expressed with respect to a random null hypothesis, and represent the most relevant higher-order connections. We apply our method to a class of synthetic benchmarks and to several datasets, showing that the method highlights hyperlinks that are more informative than those extracted with pairwise approaches. Our method provides a first way, to the best of our knowledge, to obtain statistically validated hypergraphs, separating informative connections from noisy ones.
Network motifs are recurrent, small-scale patterns of interactions observed frequently in a system. They shed light on the interplay between the topology and the dynamics of complex networks across various domains. In this work, we focus on the problem of counting occurrences of small sub-hypergraph patterns in very large hypergraphs, where higher-order interactions connect arbitrary numbers of system units. We show how directly exploiting higher-order structures speeds up the counting process compared to traditional data mining techniques for exact motif discovery. Moreover, with hyperedge sampling, performance is further improved at the cost of small errors in the estimation of motif frequency. We evaluate our method on several real-world datasets describing face-to-face interactions, co-authorship and human communication. We show that our approximated algorithm allows us to extract higher-order motifs faster and on a larger scale, beyond the computational limits of an exact approach.
Network dismantling has recently gained interest in the fields of intelligence agencies, anti-corruption analysts and criminal investigators due to its efficiency in disrupting the activity of malicious agents. Here, we apply this approach to detect effective strategies for targeted attacks to Cosa Nostra by analysing the collaboration network of affiliates that participate to the same crimes. We preliminarily detect statistically significant homophily patterns induced by being member of the same mafia syndicate. We also find that links between members belonging to different mafia syndicates play a crucial role in connecting the network into a unique component, confirming the relevance of weak ties. Inspired by this result we investigate the resilience properties of the network under random and targeted attacks with a percolation based toy model. Random removal of nodes results to be quite inefficient in dismantling the network. Conversely, targeted attacks where nodes are removed according to ranked network centralities are significantly more effective. A strategy based on a removal of nodes that takes into account how much a member collaborates with different mafia syndicates has an efficiency similar to the one where nodes are removed according to their degree. The advantage of such a strategy is that it does not require a complete knowledge of the underlying network to be operationally effective.
Understanding the collective dynamics behind the success of ideas, products, behaviors, and social actors is critical for decision-making across diverse contexts, including hiring, funding, career choices, and the design of interventions for social change. Methodological advances and the increasing availability of big data now allow for a broader and deeper understanding of the key facets of success. Recent studies unveil regularities beneath the collective dynamics of success, pinpoint underlying mechanisms, and even enable predictions of success across diverse domains, including science, technology, business, and the arts. However, this research also uncovers troubling biases that challenge meritocratic views of success. This review synthesizes the growing, cross-disciplinary literature on the collective dynamics behind success and calls for further research on cultural influences, the origins of inequalities, the role of algorithms in perpetuating them, and experimental methods to further probe causal mechanisms behind success. Ultimately, these efforts may help to better align success with desired societal values.
The opportunities to empirically study temporal networks nowadays are immense thanks to Internet of Things technologies along with ubiquitous and pervasive computing that allow a real-time fine-grained collection of social network data. This empowers data analytics and data scientists to reason about complex temporal phenomena, such as disease spread, residential energy consumption, political conflicts etc., using systematic methologies from complex networks and graph spectra analysis. However, a misuse of these methods may result in privacy-intrusive and discriminatory actions that may threaten citizens' autonomy and put their life under surveillance. This paper studies highly sparse temporal networks that model social interactions such as the physical proximity of participants in conferences. When citizens can self-determine the anonymized proximity data they wish to share via privacy-preserving platforms, temporal networks may turn out to be highly sparse and have low quality. This paper shows that even in this challenging scenario of privacy-by-design, significant information can be mined from temporal networks such as the correlation of events happening during a conference or stable groups interacting over time. The findings of this paper contribute to the introduction of privacy-preserving data analytics in temporal networks and their applications.