Using Triangles to Improve Community Detection in Directed Networks

Abstract

In a graph, a community may be loosely defined as a group of nodes that are more closely connected to one another than to the rest of the graph. While there are a variety of metrics that can be used to specify the quality of a given community, one common theme is that flows tend to stay within communities. Hence, we expect cycles to play an important role in community detection. For undirected graphs, the importance of triangles — an undirected 3-cycle — has been known for a long time and can be used to improve community detection. In directed graphs, the situation is more nuanced. The smallest cycle is simply two nodes with a reciprocal connection, and using information about reciprocation has proven to improve community detection. Our new idea is based on the four types of directed triangles that contain cycles. To identify communities in directed networks, then, we propose an undirected edge-weighting scheme based on the type of the directed triangles in which edges are involved. We also propose a new metric on quality of the communities that is based on the number of 3-cycles that are split across communities. To demonstrate the impact of our new weighting, we use the standard METIS graph partitioning tool to determine communities and show experimentally that the resulting communities result in fewer 3-cycles being cut. The magnitude of the effect varies between a 10 and 50% reduction, and we also find evidence that this weighting scheme improves a task where plausible ground-truth communities are known.

@inproceedings{KlGlKo14,  
author = {Christine Klymko and David F. Gleich and Tamara G. Kolda}, 
title = {Using Triangles to Improve Community Detection in Directed Networks}, 
booktitle = {The Second ASE International Conference on Big Data Science and Computing, BigDataScience},
venue = {Stanford, CA},
eventdate = {2014-05-27/2014-05-31}, 
year = {2014},
}