Modeling the Homophily Effect between Links and Communities for Overlapping Community Detection

Hongyi Zhang, Tong Zhao, Irwin King, Michael R. Lyu

Abstract

In network science, identifying overlapping communities is a critical task. Most existing models rely on the "Community-to-Link" assumption, where community memberships dictate link formation. This paper introduces HNMF (Homophily-based Non-negative Matrix Factorization), a model that treats homophily as a bidirectional relationship. By combining traditional Matrix Factorization with network embedding techniques, HNMF captures both how communities generate links and how links define community profiles. Experimental results on large-scale datasets like Amazon and DBLP demonstrate that HNMF significantly outperforms state-of-the-art baselines in both accuracy and modularity.

Introduction

Communities in real-world networks—such as social circles, professional affiliations, or product categories—frequently overlap. A central challenge in community detection is accurately modeling these overlaps. Standard Matrix Factorization (MF) approaches typically adopt a "Community-to-Link" perspective: if two nodes share many communities, they are likely to be linked.

However, this ignores the "Link-to-Community" perspective, which suggests that a node's community membership can be inferred from its neighbors. The authors argue that homophily is symmetric. To support this, they analyzed the Amazon and DBLP datasets, finding that linked nodes share significantly more communities (6.7 on average for Amazon) compared to random pairs (0.17). This empirical evidence strongly supports the need for a bidirectional model.

Distribution of linked node pairs over common communities for Amazon and DBLP datasets.

Methodology: The HNMF Model

The proposed HNMF model unifies two distinct perspectives into a single objective function:

  1. Community-to-Link (Pairwise Preference): This component assumes that nodes sharing more communities have a higher probability of being linked. It uses a pairwise objective function to maximize the likelihood of observed links based on community overlap.
  2. Link-to-Community (Network Embedding): Inspired by the Skip-Gram model (e.g., DeepWalk), this component treats a node’s neighbors as its "context." It learns community representations such that a node's profile can effectively predict the profiles of its neighbors.

To ensure scalability for networks with millions of nodes, the authors implemented the model using Asynchronous Stochastic Gradient Descent, a lock-free approach that enables efficient parallel training. The full algorithm is detailed below.

The HNMF algorithm for learning the node-community weight matrix.

Experimental Results

The authors evaluated HNMF against several baselines, including BigCLAM and PNMF, using both large-scale networks and small benchmark datasets.

Large-Scale Performance

On the Amazon product co-purchasing network (335k nodes), HNMF achieved an F1 score of 0.122, nearly tripling the performance of BigCLAM (0.044) and PNMF (0.042). Similar improvements were observed on the DBLP scientific co-authorship network (317k nodes).

Modularity and Scalability

On Newman’s benchmark datasets (e.g., Dolphins, Les Misérables, American College Football), HNMF consistently achieved the highest modularity scores, outperforming every baseline. Furthermore, the model demonstrated strong scalability, converging in approximately 4 to 6 hours on a standard 24-core server for the largest datasets.

Conclusion

HNMF successfully bridges the gap between Matrix Factorization and network embedding for community detection. By modeling the bidirectional homophily effect, it provides a more robust representation of overlapping groups. While the model requires a threshold for final community assignments and careful tuning of the homophily coefficient ($\beta$), its performance gains make it a powerful tool for large-scale network analysis. Future work could extend this framework to directed or weighted networks.

Summary updated

Abstract

Overlapping community detection has drawn much attention recently since it allows nodes in a network to have multiple community memberships. A standard framework to deal with overlapping community detection is Matrix Factorization (MF). Although all existing MF-based approaches use links as input to identify communities, the relationship between links and communities is still under-investigated. Most of the approaches only view links as consequences of communities (community-to-link) but fail to explore how nodes' community memberships can be represented by their linked neighbors (link-to-community). In this paper, we propose a Homophily-based Non-negative Matrix Factorization (HNMF) to model both-sided relationships between links and communities. From the community-to-link perspective, we apply a preference-based pairwise function by assuming that nodes with common communities have a higher probability to build links than those without common communities. From the link-to-community perspective, we propose a new community representation learning with network embedding by assuming that linked nodes have similar community representations. We conduct experiments on several real-world networks and the results show that our HNMF model is able to find communities with better quality compared with state-of-the-art baselines.
BibTeX
@inproceedings{zhang2016modeling,
  author = {Hongyi Zhang and Tong Zhao and Irwin King and Michael R. Lyu},
  title = {{Modeling the Homophily Effect between Links and Communities for Overlapping Community Detection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure