New Notre Dame paper focuses on degree centrality in networks

Author: William G. Gilroy

Nitesh Chawla Nitesh Chawla

Social networks such as Facebook, LinkedIn and Twitter play an increasingly central role in our lives. Centrality is also an important concept in the theory of social networks. Centrality of an individual, called a “node” in network theory, measures its relative importance within a network.

In a recent paper published in Scientific Reports, a Nature publication, University of Notre Dame researchers study the problem of dynamics and evolution of node’s centrality. Nitesh Chawla, the Frank Freimann Collegiate Associate Professor of Computer Science and Engineering and director of the University’s Interdisciplinary Center for Network Science and Applications, and his doctoral students Yang Yang and Yuxiao Dong point out that social networks are dynamic and evolve over time when new individuals (nodes) join a network, or new links form between nodes or old links diminish between nodes. A node’s centrality may change over time.

“Thus, the node and network co-evolve, where the node impacts the network and the network impacts the node, creating an intertwined effect of centrality and relative position of the node,” Chawla said.

Chawla and his students were interested in knowing the predictability of the centrality of a node. To that end, they developed a methodology titled the Node Prominence Profile (NPP) that accurately predicts the future degree centrality of nodes by incorporating both the macroscopic and microscopic properties of a social network.

“Our method can be effectively used in a variety of applications that rely on inferring a nodes’ importance in future; for example, predicting future important customers (support the advertisement strategy) or identifying individuals on the fringes that rise to be centric in adversaries’ network (early elimination of important targets in terrorists network),” Chawla said. “Our method has wide range of applications in critical human systems, such as financial markets and military operations.”

The research demonstrated that NPP is able to significantly outperform the current state-of-the-art methods in predicting node degree centrality.

“Our method, NPP, is helpful in the prediction of an individual’s future importance because it reconciles the trade-offs between two important principles that drive the evolution of social networks — preferential attachment and triadic closure,” Chawla said. “Additionally, NPP captures not only the node (or individual) attributes but also the social capital and dynamics in her/his immediate neighborhood as well.

“There are a number of applications of centrality, including inferring the success of an individual in a social network or who would rise to a position of power and influence in a network or who would play a critical role in information flow in a network,” Chawla said. “The development of nodes’ degree centrality is an essential element in the process of social network evolution.”

Although the research focused primarily on NPP in analyzing social networks, the researchers believe it also has the potential to be applied in biological networks, disease networks, protein interaction networks, food networks and transportation networks.

Chawla’s future research will further examine the ways individuals on the fringes rise to be centric in networks.

“Our work had shown that individuals in the early stage of network evolution display a distinctive and robust signature in their centrality trend, which can be adequately predicted by the NPP method,” Chawla said. “A key area in my research program is understanding and modeling the dynamics of social networks. Our work in NPP is a first step in that direction. We are developing a unified model and theory that goes from microscopic to macroscopic characterization of a network.”

The research described in the Scientific Reports paper can be accessed here.

Contact: Nitesh Chawla, 574-631-8716, nchawla@nd.edu