---
title: "Exploiting k-Degree Locality to Improve Overlapping Community Detection"
authors:
  - "Hongyi Zhang"
  - "Michael R. Lyu"
  - "Irwin King"
doi: ""
url: "https://ijcai.org/proceedings/2015/339"
pdf: "https://ijcai.org/proceedings/2015/0339.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "2394-2399"
track: "Main Track"
keywords:
---

# Exploiting k-Degree Locality to Improve Overlapping Community Detection

Hongyi Zhang, Michael R. Lyu, Irwin King

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 2394-2399.

## 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 non-neighbors 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.