Description
Abstract
How do we find communities in a graph? How does this change if the graph is bipartite? The Louvain method maximizes links within communities and minimizes those between in order to determine an optimal grouping. Yet, because it may fail when bipartite restrictions are introduced, we have adjusted the null model so as to improve performance in these conditions.
Conclusion
Our Bipartite Louvain is more robust with respect to permutations of vertices than the standard Louvain. For our synthetic examples, Bipartite Louvain typically yields a higher modularity and uncovers the ground truth communities with a higher probability. In the future, we will examine real world data sets with our modified algorithm.
Included in
Partitioning Bipartite Graphs: A Modified Louvain
Abstract
How do we find communities in a graph? How does this change if the graph is bipartite? The Louvain method maximizes links within communities and minimizes those between in order to determine an optimal grouping. Yet, because it may fail when bipartite restrictions are introduced, we have adjusted the null model so as to improve performance in these conditions.
Conclusion
Our Bipartite Louvain is more robust with respect to permutations of vertices than the standard Louvain. For our synthetic examples, Bipartite Louvain typically yields a higher modularity and uncovers the ground truth communities with a higher probability. In the future, we will examine real world data sets with our modified algorithm.
Comments
This work was done during a summer internship at Lawrence Livermore National Laboratory, as part of the Directed Graphs research group.