Skip to content

Network Science

Incorporating higher-order interactions: extending network models to simplicial complexes

Graph-based models have enjoyed a tremendous success for modelling complex systems and networks over the past decades, however, fundamental interactions in networks often take place between multiple nodes.

Indeed, concurrent dynamical dependencies between multiple nodes, although typically neglected, are present in many systems. Consider for instance socio-economic networks, where group-based interactions are commonplace, often involving the joint coordinated activity of multiple agents (e.g. buyer, seller, broker). The importance of non-binary (so called supra-dyadic) interactions has also been long debated in the social sciences. For instance, structural balance theory implies that triadic relations in social networks will evolve according to the colloquial rules “the friend of a friend is my friend” and “the enemy of my enemy is my friend.”

In all these examples, the joint coordinated interplay between multiple entities is crucial, and cannot be captured naturally with a simple pairwise (binary) interaction model (Figures 1a-b). As graphs are fundamentally focusing on pairwise interactions (edges denote interactions between pairs of nodes), graph based models may therefore be insufficient to represent faithfully the dynamics of the system. In this context, simplicial complexes (SCs) provide an appropriate formalism that can integrate higher-order interactions into network models and extend graph-based models. SCs are finite collections of simplices (nodes, edges, triangular faces, etc.) closed under intersections, which compared to generic hypergraphs have favorable algebraic properties and deep connections to algebraic topology that can be exploited for network analysis. For instance, SCs are naturally endowed with higher-order Laplacian operators (so called Hodge-Laplacians) — extensions of the well-known graph Laplacian that is pivotal for network analysis — which can be used to reveal additional information about the system under investigation.

Tahbaz-Salehi, A., & Jadbabaie, A. (2010). Distributed coverage verification in sensor networks without location informationIEEE Transactions on Automatic Control55(8), 1837-1849.
Molavi, P., & Jadbabaie, A. (2011, June). A topological view of estimation from noisy relative measurements. In American Control Conference (ACC), 2011 (pp. 3615-3620). IEEE.
Benson, A. R., Abebe, R., Schaub, M. T., Jadbabaie, A., & Kleinberg, J. (2018). Simplicial closure and higher-order link predictionarXiv preprint arXiv:1802.06916.
Schaub, M. T., Benson, A. R., Horn, P., Lippner, G., & Jadbabaie, A. (2018). Random Walks on Simplicial Complexes and the normalized Hodge LaplacianarXiv preprint arXiv:1807.05044.


Recovering network structure from data

We have studied the  problem of recovering the topology of a graph (or coarser features of it, such as communities) from observing snapshots of multiple independent network processes. For instance, we observe the opinion profiles of a group of agents for a set of independent topics and our goal is to recover the precise relationships between the agents (or detect communities), as specified by the unknown social network underlying the exchange of opinions. A key realization is that the covariance structure of the outputs of the observed network process contain essential information about the graph that we are trying to recover. Hence, we leverage concepts from spectral graph theory and convex optimization to unveil the underlying network structure.

Back to Research & Projects