HellRank: a Hellinger-based centrality measure for bipartite social networks

Seyed Mohammad Taheri, Hamidreza Mahyar, Mohammad Firouzi, Elahe Ghalebi K., Radu Grosu, Ali Movaghar

TL;DR

This paper introduces HellRank, a novel centrality measure for bipartite social networks that identifies "behaviorally representative" users. By leveraging the Hellinger distance between node degree distributions, HellRank offers a more nuanced understanding of user importance than traditional metrics, particularly in complex social structures like recommender systems.

What Problem Does This Paper Address?

Measuring the importance of users (centrality) in social networks is crucial for understanding influence, identifying key actors, and building effective systems like recommender engines. However, many real-world social networks are inherently bipartite (e.g., users and items, authors and papers), and traditional centrality measures, designed for non-bipartite networks, often fall short. Projecting bipartite networks into single-mode networks can lose valuable information and introduce artifacts. Furthermore, existing measures may not accurately capture "behaviorally representative" users – those who truly embody the collective behavior of a group, rather than just having many connections. This paper addresses the challenge of accurately identifying such users in bipartite networks without resorting to problematic projections.

Methods

The core of HellRank lies in its use of the Hellinger distance, a metric that quantifies the similarity between two probability distributions. In this context, the probability distributions are derived from the degree distributions of the neighbors of nodes within the bipartite network. Specifically, for two nodes on the same side of the bipartite graph, HellRank calculates the Hellinger distance between vectors representing the degrees of their respective neighbors. This distance is then used to compute a similarity score. The authors theoretically analyze the properties of the Hellinger distance in this context, proving it satisfies metric properties and deriving upper and lower bounds. The final HellRank score for a node is derived from the average of the inverse of these distances to all other nodes on its side of the network, effectively measuring how "similar" a node is to the collective behavior of its peers. A key advantage is that this calculation can be distributed, relying only on local neighborhood information.

Datasets

The paper evaluates HellRank on two datasets:

  • South Davis Women dataset: A common bipartite dataset representing women and events, where a link indicates a woman's presence at an event.
  • OPSAHL-collaboration network: A bipartite network connecting authors and publications in the arXiv condensed matter section.

Key Insights and Ideas

  • Beyond simple connections: Traditional centrality measures often focus on the number of connections (degree) or shortest paths. HellRank, by considering the distribution of neighbor degrees, captures a more subtle aspect of a node's role and influence.
  • Behavioral representation matters: The paper argues that identifying "behaviorally representative" users is distinct from identifying "influential" users. HellRank aims to capture the former, which is crucial for tasks like building representative user profiles or understanding community dynamics.
  • Hellinger distance is a good fit: The Hellinger distance is chosen over other f-divergences because it satisfies metric properties (symmetry, triangle inequality) and is intuitively suited for comparing probability distributions, which is what the neighbor degree distributions represent.
  • Local information is sufficient: A significant practical advantage is that HellRank can be computed using only local neighborhood information, making it scalable to very large networks where global topology is not readily available.

Key Results

  • Partial correlation with existing metrics: Experimental results show a partial correlation between HellRank and established centrality measures like bipartite Degree, Betweenness, and PageRank. This suggests HellRank captures some shared aspects of importance but also offers a unique perspective.
  • Distinguishing nodes: The paper highlights cases where HellRank effectively separates nodes that traditional metrics struggle to differentiate, particularly in identifying "behavioral representatives." For instance, in the Davis dataset, HellRank identified node 'B' as more representative, a distinction missed by other metrics.
  • Scalability potential: The distributed computation aspect of HellRank makes it suitable for large-scale networks, a significant advantage over many other centrality measures that require global network knowledge.

Limitations and Future Work

  • Limitations: The paper acknowledges that while there's a partial correlation, HellRank doesn't perfectly align with all traditional metrics, implying different objectives. The current implementation focuses on unweighted bipartite networks, though an extension to weighted networks is mentioned.
  • Future Work: The authors suggest extending HellRank to weighted bipartite networks. They also propose incorporating more meta-data beyond just links and exploring its application in Recommender Systems. Additionally, they mention the potential for using HellRank with compressive sensing techniques for detecting central nodes without full network knowledge.

Summary updated

Abstract

Measuring centrality in a social network, especially in bipartite mode, poses several challenges such as requirement of full knowledge of the network topology and lack of properly detection of top-k behavioral representative users. In this paper, to overcome the aforementioned challenging issues, we propose an accurate centrality measure, called HellRank, to identify central nodes in bipartite social networks. HellRank is based on the Hellinger distance between two nodes on the same side of a bipartite network. We theoretically analyze the impact of the Hellinger distance on a bipartite network and find an upper and lower bounds for this distance. The computation of HellRank centrality measure can be distributed by letting each node uses only local information on its immediate neighbors and therefore do not need a central entity to have full knowledge of the network topological structure. We experimentally evaluate performance of the HellRank measure in correlation with other centrality measures on real-world networks. The results show partial ranking similarity between the HellRank and the other conventional metrics according to the Kendall and Spearman rank correlation coefficient.
BibTeX
@article{taheri2017hellrank,
  author = {Seyed Mohammad Taheri and Hamidreza Mahyar and Mohammad Firouzi and Elahe Ghalebi K. and Radu Grosu and Ali Movaghar},
  title = {{HellRank: a Hellinger-based centrality measure for bipartite social networks}},
  journal = {Soc. Netw. Anal. Min.},
  year = {2017},
  doi = {10.1007/s13278-017-0440-7},
}
Figure