New paper focuses on degree centrality in networks

February 26, 2015 by William G. Gilroy, University of Notre Dame

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 () 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 ."

Explore further: New paper examines the significant social strategies in human communication

More information: "Predicting Node Degree Centrality with the Node Prominence Profile." Scientific Reports 4, Article number: 7236 DOI: 10.1038/srep07236

Related Stories

Uncovering complex network structures in nature

December 10, 2014

The global spread of Ebola is due to the complex interactions between individuals, societies, and transportation and trade networks. Understanding and building appropriate statistical and mathematical models of these interactions ...

Researchers boost efficiency of multi-hop wireless networks

April 19, 2012

Multi-hop wireless networks can provide data access for large and unconventional spaces, but they have long faced significant limits on the amount of data they can transmit. Now researchers from North Carolina State University ...

Scientists review worldwide rise of 'network of networks'

December 3, 2014

The interdisciplinary field of network science has attracted enormous attention in the past 10 years, although most results have been obtained by analyzing isolated networks. However many real-world networks interact with ...

Recommended for you

Earwigs and the art of origami

March 22, 2018

ETH Zurich researchers have developed multifunctional origami structures, which they then fabricated into 4-D printed objects. The design principle mimics the structure of an earwig's wing.


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.