How to find important nodes in multilayer networks

“We want to find out the most valuable seller and the most prospective buyer among 100 million subscribers,” one of the digital engineers with Ant Financial Services Group talks about this challenge at work.

“The framework we have created may help,” replies HE Shibo, a prinicipal investigator with the College of Control Science and Engineering, Zhejiang University, “At the core of this issue is the evaluation of every single node in a multilayer network.”

The research team led by Prof. CHEN Jiming publishes their findings in the July 17 issue of PNAS. They develop a tensor-based framework for characterizing eigenvector multicentrality in general multilayer networks. While assessing such multilayer networks as information networks, traffic networks and social networks, particularly in terms of which node carries most weight in a network, people can employ a more precise and rational method in the future.

This research is headed by the State Key Laboratory of Industrial Control Technology at Zhejiang University and jointly conducted by Arizona State University, Princeton University and Harvard University. 

In this day and age, mankind is marching into a world of intricate multilayer networks. Anybody or anything may well become a crucial node in a myriad of networks ranging from the ecological system and the Internet to the transportation network and the financial market. Then, how do nodes affect the stability and efficiency of a network?

Examples of multilayer networks. (A) A network of web pages in Wikipedia can be considered as a multilayer network. Layers represent subjects, and nodes denote words (or terms) connected by hyperlinks. Colorized links are intralayer links while gray ones are interlayer links. (B) A European airline network with 3 layers can be modeled as a multiplex network, which contains the same set of nodes in all layers.

Meanwhile, mankind is the sum of all social relationships. A “dad” in a family relationship may be a “CEO” in the workplace, or even “somebody” in social networks. He carries different identity “tags” across different social networks. So how do we evaluate the multiple “him” as a whole?

“The major difficulty in this research has much to do with the complexity of multilayer and interconnected networks,” says Prof. CHEN Jiming. This question appears to be far-flung and network scientists have endeavored to develop a relatively universal mathematical model so as to help people engage in exploratory research and make predictions, which is heavily dependent on the characterization of networks.

First, networks are multi-layer. Take, for example, the transportation network. The urban traffic system is comprised of airports, railway stations, highways, railways and subways, which are independent but interconnected. The over-crowdedness in the subway may be related to the sudden flow of passengers into the subway due to the simultaneous arrival of trains and buses.

Second, networks are heterogeneous. When assessing the same node on different layers, we tend to adopt different ways to assess it. For example, if we want to evaluate the importance of a particular person, we will rely on different indicators which are contingent on heterogeneous networks. How can we make an objective evaluation and a sensible comparison? 

“An effective framework for studying centrality in multilayer networks is still lacking,” says HE Shibo, “The complexity of networks and the heterogeneity and interplay of different layers render it far from satisfactory to simply aggregate a multilayer network into a single-layer one, so we need to develop a novel framework and design efficient algorithms.”

In this study, a tensor-based framework is introduced to study eigenvector multicentrality, which enables the quantification of the impact of interlayer influence on multicentrality, providing a systematic way to delineate how multicentrality propagates across different layers. This framework can leverage prior knowledge about the interplay among layers to better characterize multicentrality for varying scenarios.

Researchers present two interesting cases—a network of web pages in Wikipedia and the European airline network—to illustrate how to model multilayer influence by choosing appropriate functions of interlayer influence and design algorithms to calculate eigenvector multicentrality.

This proposed tensor-based framework can be applied to more empirical networks in various scenarios, including social networks, transportation networks, biological networks, etc.