Exploiting k-Degree Locality to Improve Overlapping Community Detection

Hongyi Zhang, Michael R. Lyu, Irwin King

Introduction

In real-world social networks, individuals often belong to multiple social circles simultaneously—such as professional groups, hobbyist clubs, and family units. Detecting these overlapping communities is a fundamental task in network science with applications ranging from recommendation systems to viral marketing. Traditional approaches often struggle to accurately capture these overlaps, especially in sparse networks where the majority of potential connections are missing.

This paper, originally presented at IJCAI 2015, introduces Locality-based Non-negative Matrix Factorization (LNMF). The core intuition is simple yet powerful: a "friend of a friend" is more likely to share a community membership than a distant stranger. By formalizing this "k-degree locality," the authors improve the precision of community detection by refining how non-neighbors are treated during the optimization process.

Problem Statement: The "Zero" Problem in Matrix Factorization

Most community detection algorithms utilize Matrix Factorization (MF) to approximate the adjacency matrix of a graph. However, standard MF models often treat all "zeros" (non-links) in the adjacency matrix as equally indicative of a lack of community relationship.

Preference-based models like PNMF improved upon this by using pairwise rankings, asserting that a node prefers its neighbors over its non-neighbors. Yet, these models still fail to distinguish between "local non-neighbors" (nodes just a few steps away) and "distant non-neighbors" (nodes in entirely different parts of the graph). In reality, a local non-neighbor often represents a "missing link" within a shared community, whereas a distant non-neighbor is truly unrelated.

Methodology: k-Degree Locality

The authors propose a three-level preference hierarchy to better model community structures. Instead of a binary neighbor/non-neighbor split, LNMF categorizes relationships based on their proximity in the graph.

Table of notations defining the sets used in the LNMF model, distinguishing between neighbors, local non-neighbors, and distant non-neighbors.

As shown in the notation table above, the model distinguishes between:

  1. Neighbors ($N^+$): Direct connections.
  2. Local Non-neighbors ($S_k$): Nodes within $k$ steps (typically $k=2$) that are not direct neighbors.
  3. Distant Non-neighbors ($T_k$): All other nodes in the network.

The objective function of LNMF maximizes the likelihood of the preference order: Neighbors > Local Non-neighbors > Distant Non-neighbors. To ensure scalability, the authors employ a Stochastic Gradient Descent (SGD) strategy that samples "quadruples" $(u, i, j, d)$, representing a source node and one representative from each of the three levels. A locality coefficient ($\lambda$) is introduced to balance the influence of local versus distant nodes, preventing the vast number of distant nodes from drowning out local signals.

Experimental Setup

The model was rigorously tested across various network types, ranging from small benchmark datasets to massive real-world social graphs.

Summary of the small-scale benchmark datasets used for evaluation, including node (V) and edge (E) counts.

The evaluation used two primary metrics:

  • Modularity: Applied to small-scale networks like Dolphins and American college football to measure the strength of the detected community structure.
  • F1 Score: Applied to large-scale SNAP datasets (DBLP, Amazon, YouTube) where ground-truth community memberships were available.

Key Insights and Results

The experimental results validated the importance of local proximity in community detection:

  • Superior Performance: LNMF consistently outperformed state-of-the-art baselines like BigCLAM and PNMF. Notably, it achieved a 47% relative improvement in modularity on the "Books about US Politics" dataset.
  • The Optimal k: The researchers found that $k=2$ (friends of friends) provides the best balance between accuracy and computational cost. Higher values of $k$ did not significantly improve results but increased the search space for local non-neighbors.
  • Scalability: The SGD sampling approach allowed the model to converge efficiently even on networks with millions of nodes.
  • Contextual Limitations: The model performed less effectively on the YouTube dataset. The authors suggest that YouTube's community structure is less driven by local friendship circles and more by random or global interests, making the locality assumption less applicable.

Conclusion

LNMF demonstrates that "not all zeros are equal" in network adjacency matrices. By exploiting k-degree locality, the model effectively captures the latent community signals hidden in local non-neighbors. This approach not only improves the accuracy of overlapping community detection but also provides a scalable framework for analyzing large, sparse real-world networks. Future work may extend this logic to link prediction, treating local non-neighbors as the most probable candidates for future connections.

Summary updated

Abstract

Community detection is of crucial importance in understanding structures of complex networks. In many real-world networks, communities naturally overlap since a node usually has multiple community memberships. One popular technique to cope with overlapping community detection is Matrix Factorization (MF). However, existing MF-based models have ignored the fact that besides neighbors, "local non-neighbors" (e.g., my friend's friend but not my direct friend) are helpful when discovering communities. In this paper, we propose a Locality-based Non-negative Matrix Factorization (LNMF) model to refine a preference-based model by incorporating locality into learning objective. We define a subgraph called "k-degree local network" to set a boundary between local nonneighbors and other non-neighbors. By discriminately treating these two class of non-neighbors, our model is able to capture the process of community formation. We propose a fast sampling strategy within the stochastic gradient descent based learning algorithm. We compare our LNMF model with several baseline methods on various real-world networks, including large ones with ground-truth communities. Results show that our model outperforms state-of-the-art approaches.
BibTeX
@inproceedings{zhang2015exploiting,
  author = {Hongyi Zhang and Michael R. Lyu and Irwin King},
  title = {{Exploiting k-Degree Locality to Improve Overlapping Community Detection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}

Loading related content...

Figure