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. keywords: community detection, directed networks, triangles, reciprocity, 3-cycles Many different systems can be viewed as complex networks made up of objects (nodes) and connections between them (links or edges). Over the past several decades the study of such networks has become important in many disciplines [5, 6, 9, 23] , and a recurrent research theme is finding the communities or modules within these networks. These communities reveal important structures hidden within the network data. Thus far, the majority of work in community detection has focused on undirected networks (see the survey [10]), although, recently, more research has focused on directed networks (see the survey [20] ). In the most common setting, a community is a group of nodes that are more closely connected to each other than to the rest of the network. Community assignment methods use only topological features of the network unless additional information about the components of the network is known; and thus the connectivity between nodes is often used alone to define metrics measuring the "quality" of the assigned groups. Common quality metrics measure (i) the density of links within a group (modularity) [21] , (ii) the number of cut edges relative to the group size (conductance), (iii) the stationary distribution of a random walk within the network (LinkRank) [17] , (iv) and the probability of a (directed) link between two nodes [33] . Most of these quality measures have natural extensions to weighted networks, in which case expressions such as "number of edges" are replaced with "total edge weight" instead. In our paper, we propose a simple weighting scheme that converts a directed graph into a weighted undirected graph. This model enables us to utilize the richness and complexity of existing methods to find communities in undirected graphs. In particular, various schemes have been developed to optimize those four types of connectivity metrics, see [4, 12, 13, 22, 24, 32] among others. Our specific weighting scheme is based on extending the idea that, within "good" communities, information can be shared within a community more easily than between communities. As information can flow along edges, short (directed) paths and (directed) cycles can be seen as important in the function of communities within networks. For instance, a short path between two nodes indicates that information can travel between them quickly-or can travel quickly
For example, Klymko et al. REF applies triangles information to detect community in directed networks.
Using Triangles to Improve Community Detection in Directed Networks
ArXiv
ArXiv
Computer Science Physics