Ranking constituents in complex systems from local and aggregate information

Many complex systems exhibit a natural hierarchy in which elements can be ranked according to a notion of “influence”: from characterising how species of an ecosystem interact with each other (according to their trophic levels), to determining how central nodes in a social network are in propagating information.  Typically, quantifying a node’s influence necessitates the full knowledge of all constituents’ interactions—a requirement often unattainable in real-world scenarios.

Using a low-rank approximation, I will instead show that local and aggregate information about the neighbourhood of nodes is often enough to reliably estimate how influential they are, without the need to infer or reconstruct the whole map of interactions. I will connect the accuracy of the approximation with the spectral properties of the underlying network, and I will present an approach based on cavity/belief propagation to gain further analytical insights on the influence distribution in ensemble of random locally tree-like networks.

Event resources