Report

Teaser, summary, work performed and final results

Periodic Reporting for period 1 - HIntNets (Higher-order interactions and Laplacian dynamics in complex networks: structure, dynamics and control)

Teaser

Complex networks underpin integral parts of our biological, physical and socio-economic universe. Understanding such networks is thus a core problem arising in many different applications. Thus far, such networks have been mainly represented as graphs. However, while graphs...

Summary

Complex networks underpin integral parts of our biological, physical and socio-economic universe. Understanding such networks is thus a core problem arising in many different applications. Thus far, such networks have been mainly represented as graphs. However, while graphs can capture pairwise interactions between nodes, fundamental interactions in networks often take place between multiple nodes. For example, in socio-economic networks, the joint coordinated activity of several agents (e.g. buyer, seller, broker); the formation and interactions of coalitions; the emergence of peer pressure; and the existence of triadic closure are all prevalent.

The objective of this interdisciplinary project is to investigate such non-binary, group-based relationships in complex networks and their dynamical implications. Specifically, we will examine how such interactions can be accounted for in the modelling, analysis and design of complex networks, and will investigate generalized network models. While data about group interactions is readily available in some cases, often the groupings or even the network of interactions might be unknown. We will thus further investigate techniques to infer (generalized) networks and group structures from available data.

To provide an analysis framework for non-binary interactions, we will extend the geometrical framework of simplicial complexes to account systematically for non-binary couplings of nodes, node-pairs, triplets, etc., allowing us to assess and design higher-order interactions. We will focus on consensus and random walks as prototypical examples of a range of phenomena. Working at the interface of Network Science and Control Theory, we will combine recent tools from both fields and apply our results to real data from different areas.

Work performed

\"During the outgoing phase of the project we have investigated group-based interactions in networks from different perspectives. Our main results so far are as follows.


1) We examined the use of simplicial complexes as a framework for modelling non-dyadic interactions and introduced a higher-order link prediction task to evaluate models for such interaction data. In this context we also investigated the phenomenon of simplicial closure as a higher-order analog of the well known process of triadic closure in networks.

This work has been consolidated in the publication:

Benson, Austin R., Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg. \"\"Simplicial closure and higher-order link prediction.\"\" Proceedings of the National Academy of Sciences 115, no. 48 (2018): E11221-E11230.


2) We investigated how diffusion processes on simplicial complexes can be defined and in how far such processes can be used to generalize the toolkit of network science to simplicial complexes, specifically focusing on extensions of PageRank and spectral embeddings for simplicial complexes. To this end we introduced a normalized 1-Hodge Laplacian operator, an extension of the normalized graph Laplacian for simplicial complexes.

M.T. Schaub, A.R. Benson, P. Horn, G. Lippner,and A. Jadbabaie.“Random walks on simplicial complexes and the normalized1-Hodge Laplacian”. under review at SIAM Review


3) In many problems modeled using graphs, the data of interest is located on the edges (as opposed to the nodes). A typical scenario of practical interest is a flow on the edges – signal, mass, energy, information – of a graph that is measured and has to be analyzed further, such as traffic flow associated with the edges of a traffic network. To analyze these types of signal we have developed techniques for analyzing the edge-space of graphs and simplicial complexes in more detail.
An important tool in this context is the Hodge decomposition, a decomposition of edge flows into intuitively interpretable components that are analogous to notions such as gradient flows or rotational flows from vector calculus. We have demonstrated how this decomposition can be leveraged for data analytics that extract information about the edge-space that complements and extends typical graph-based analysis.

Schaub M. T.; Segarra, S. “Flow smoothing and denoising: graph signal processing in the edge-space”. 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP), Anaheim, CA, USA, 2018, pp. 735-739.

Jia, J.; Segarra, S.; Schaub, M. T. & Benson, A. R. “Graph-based Semi-Supervised & Active Learning for Edge Flows”. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2019), ACM, 2019


4) Extending our previous work in this direction, we further investigated the detection of group structures in networks from a dynamical perspective. In contrast to many standard techniques for the detection of groups within networks, our work focusses on group structures that are defined in a dynamical manner.

M. T. Schaub, J.-C. Delvenne, R. Lambiotte, and M. Barahona. “Multiscale Dynamical Embeddings of Complex Networks”. Phys. Rev. E 99 (6 June 2019), p. 062308

M. Rosvall, J.-C. Delvenne, M. T. Schaub, and R. Lambiotte. “Different approaches to community detection”. In: Advances in network clustering and blockmodeling. Ed. by P. Doreian, V. Batagelj, and A. Ferligoj. (forthcoming). Wiley, 2018

M. T. Schaub, J.-C. Delvenne, R. Lambiotte, and M. Barahona. “Structured networks and coarse-grained descriptions: a dynamical perspective”. In: Advances in network clustering and blockmodeling. Ed. by P. Doreian, V. Batagelj, and A. Ferligoj. (forthcoming). Wiley, 2018.

M. Faccin, M. T. Schaub, and J.-C. Delvenne. “Entrograms and coarse graining of dynamics on complex networks”. Journal of Complex Networks (Nov. 2017), cnx055


5) We further investigated the inference of\"

Final results

This project advances the modelling of complex systems via the use of simplicial complexes and develops a first suite of tools for their analysis. Apart from the results already discussed in the previous section, we expect that during the return phase we will be able to publicize the action further and study another application example.

Website & more info

More info: https://michaelschaub.github.io/HIntNets/.