I am working through this course on Coursera, part of this specialization. The project ideas suggested for this capstone project included community detection in social network data, so I was trying to implement the Louvain and Leiden algorithms for community detection using the datasets provided by the Coursera course instructors. At first, I tried to implement graph aggregation using generics and wildcards, but that quickly turned out to be impractical. So I decided instead to follow this, which I had found while searching for more information on how to implement these algorithms. These instructions link to this PowerPoint. I have performed some rudimentary testing on my Louvain implementation by passing in partitions obtained from my program to Networkx’s nx.community.modularity() function, and the modularities returned are correct. Afterwards, I finished writing the functions for the Leiden algorithm and ran my program with the resolution parameter gamma set to 1. This returned the same singleton partition I had passed into the leiden() function, but page 39 here seems to suggest this is expected, so I reduced gamma to 0.5 and began debugging. At one point, my program places two nodes in a community while iterating through the outer loop of the moveNodesFast() function, but in another iteration, determines that moving one of the nodes from this community back out into its own separate community increases the value of the CPM function. If going from a singleton partition to one where these two nodes were together increased the value of the CPM function, why would moving the node back out into its own community also increase the value of the CPM function? I can’t figure out where the logic of my program is going wrong; the function calculating the change in CPM is using the correct formula as far as I can understand.
I was already provided a separate class to load the graphs and a Graph interface in the Coursera course materials, and I have 5 other classes to handle setting up the graph and running the Louvain and Leiden functions on it, so I apologize if this does not meet the guidelines for a minimal reproducible example.
The graphs are present in the data subfolder of my project folder as text files. The one I’m working with right now is present in a file named “example_graph_changed.txt”. It is shown below:
1 2
1 3
1 4
2 3
2 4
3 4
3 6
4 8
6 5
6 7
6 8
8 5
8 7
8 9
7 9
7 10
9 10
9 13
10 11
10 13
10 14
10 15
13 11
13 12
11 12
11 14
11 15
11 16
14 16
As mentioned, I have a class to load the graphs (named GraphLoader) and a Graph interface. GraphLoader is present in the util package of my project folder, while the Graph interface is present in the graph package along with all the other classes I have created.
GraphLoader:
package util;
import java.io.File;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class GraphLoader {
/**
* Loads graph with data from a file.
* The file should consist of lines with 2 integers each, corresponding
* to a "from" vertex and a "to" vertex.
*/
public static void loadGraph(graph.Graph g, String filename) {
Set<Integer> seen = new HashSet<Integer>();
Scanner sc;
try {
sc = new Scanner(new File(filename));
} catch (Exception e) {
e.printStackTrace();
return;
}
// Iterate over the lines in the file, adding new
// vertices as they are found and connecting them with edges.
while (sc.hasNextInt()) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
if (!seen.contains(v1)) {
g.addVertex(v1);
seen.add(v1);
}
if (!seen.contains(v2)) {
g.addVertex(v2);
seen.add(v2);
}
g.addEdge(v1, v2);
}
sc.close();
}
}
Graph:
package graph;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
public interface Graph {
/* Creates a vertex with the given number. */
public void addVertex(int num);
/* Creates an edge from the first vertex to the second. */
public void addEdge(int i1, int i2);
/* Finds the egonet centered at a given node. */
public Graph getEgonet(int center);
/* Returns all SCCs in a directed graph. Recall that the warm up
* assignment assumes all Graphs are directed, and we will only
* test on directed graphs. */
public List<Graph> getSCCs();
/* Return the graph's connections in a readable format.
* The keys in this HashMap are the vertices in the graph.
* The values are the nodes that are reachable via a directed
* edge from the corresponding key.
* The returned representation ignores edge weights and
* multi-edges. */
public HashMap<Integer, HashSet<Integer>> exportGraph();
}
The class implementing the Graph interface that I use to actually store the graph as an object is shown below:
package graph;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
public class ComDetGraph implements Graph {
private HashMap<Integer, ComDetNode> nodeMap;
private HashSet<ComDetEdge> edges;
private Partition partition;
public ComDetGraph () {
this.nodeMap = new HashMap<>();
this.edges = new HashSet<>();
this.partition = new Partition();
}
public int getNumVertices() {
return nodeMap.values().size();
}
public int getNumEdges() {
return edges.size();
}
public HashMap<Integer, ComDetNode> getNodeMap() {
return nodeMap;
}
public Partition getPartition() {
return partition;
}
public HashSet<ComDetEdge> getEdges() {
return edges;
}
@Override
public void addVertex(int num) {
ComDetNode n = nodeMap.get(num);
if (n == null) {
n = new ComDetNode(num);
nodeMap.put(num, n);
}
}
@Override
public void addEdge(int i1, int i2) {
ComDetNode n1 = nodeMap.get(i1);
ComDetNode n2 = nodeMap.get(i2);
if (n1 == null) {
throw new IllegalArgumentException("Node with value " + i1 +
" does not exist in graph");
}
if (n2 == null) {
throw new IllegalArgumentException("Node with value " + i2 +
" does not exist in graph");
}
ComDetEdge edge = new ComDetEdge(n1, n2, 1);
edges.add(edge);
n1.addNeighbor(n2);
n2.addNeighbor(n1);
}
@Override
public Graph getEgonet(int center) {
// TODO Auto-generated method stub
return null;
}
@Override
public List<Graph> getSCCs() {
// TODO Auto-generated method stub
return null;
}
@Override
public HashMap<Integer, HashSet<Integer>> exportGraph() {
// TODO Auto-generated method stub
return null;
}
}
I have created the classes ComDetNode and ComDetEdge for storing nodes and edges as objects.
ComDetNode:
package graph;
import java.util.HashSet;
import java.util.Objects;
public class ComDetNode {
private Integer value;
private HashSet<ComDetNode> neighbors;
public ComDetNode(Integer value) {
this.value = value;
this.neighbors = new HashSet<>();
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public HashSet<ComDetNode> getNeighbors() {
return neighbors;
}
public void addNeighbor (ComDetNode nbr) {
neighbors.add(nbr);
}
@Override
public int hashCode() {
return Objects.hash(value);
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
ComDetNode other = (ComDetNode) obj;
return Objects.equals(value, other.value);
}
@Override
public String toString() {
return "" + value + "";
}
}
ComDetEdge:
package graph;
public class ComDetEdge {
private ComDetNode start;
private ComDetNode end;
public ComDetEdge (ComDetNode start, ComDetNode end, int weight) {
this.start = start;
this.end = end;
}
public ComDetNode getEndNode() {
return end;
}
@Override
public String toString() {
return start + "->" + end;
}
}
I also have a class to store partitions of the graph, as defined in the context of the Louvain and Leiden algorithms:
package graph;
import java.util.HashMap;
import java.util.HashSet;
public class Partition {
private HashMap<ComDetNode, Integer> nodeIDMap;
private HashMap<Integer, HashSet<ComDetNode>> iDNodeSetMap;
public Partition() {
nodeIDMap = new HashMap<>();
iDNodeSetMap = new HashMap<>();
}
public HashMap<ComDetNode, Integer> getNodeIDMap() {
return nodeIDMap;
}
public HashMap<Integer, HashSet<ComDetNode>> getIDNodeSetMap() {
return iDNodeSetMap;
}
public int getComID (ComDetNode node) {
return nodeIDMap.get(node);
}
public HashSet<ComDetNode> getNodeSet (int id) {
return iDNodeSetMap.get(id);
}
}
Finally, I have a class where I’ve written the functions to use in the Louvain and Leiden algorithms, and a main function to run them.
package graph;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import util.GraphLoader;
public class ComDet {
public Partition singletonPartition (ComDetGraph g) {
Partition partition = new Partition();
for (ComDetNode node : g.getNodeMap().values()) {
partition.getNodeIDMap().put(node, node.getValue());
HashSet<ComDetNode> newNodeSet = new HashSet<>();
newNodeSet.add(node);
partition.getIDNodeSetMap().put(node.getValue(), newNodeSet);
}
return partition;
}
private Partition singletonPartitionForComm (HashSet<ComDetNode> comm) {
Partition partition = new Partition();
for (ComDetNode node : comm) {
partition.getNodeIDMap().put(node, node.getValue());
HashSet<ComDetNode> newNodeSet = new HashSet<>();
newNodeSet.add(node);
partition.getIDNodeSetMap().put(node.getValue(), newNodeSet);
}
return partition;
}
public double q (ComDetGraph g, Partition partition, int C, double gamma) {
int numEdges = g.getNumEdges();
double q_C = 0;
double int_comp = 0;
double out_comp = 0;
//technically O(|C|) * O(deg(v)) where |C| is cardinality of C
//but overall impact of |C| not significant on calculation of modularity
//since modularity is calculated for entire partition
//it eventually just involves iterating over all edges of the graph
//making it O(m) overall
//of course, it's (moment-to-moment) slower than del_Q
//which is just O(|C|) + O(deg(v))
//But del_Q is also called for every node, making its overall
//contribution also O(m)
for (ComDetNode n : partition.getIDNodeSetMap().get(C)) {
for (ComDetNode nbr : n.getNeighbors()) {
if (partition.getIDNodeSetMap().get(C).contains(nbr)) {
++int_comp;
}
++out_comp;
}
}
double nEC = (double) (2 * numEdges);
int_comp /= nEC;
out_comp *= out_comp;
out_comp /= (Math.pow((2 * numEdges), 2));
out_comp *= gamma;
q_C = int_comp - out_comp;
return q_C;
}
public double cpm (Partition partition, int C, double gamma) {
double cpm = 0;
double int_comp = 0;
double out_comp = 0;
int n_c = partition.getIDNodeSetMap().get(C).size();
double n_c_2 = (double) n_c * ((n_c - 1) / 2);
out_comp *= (gamma * n_c_2);
for (ComDetNode n : partition.getIDNodeSetMap().get(C)) {
for (ComDetNode nbr : n.getNeighbors()) {
if (partition.getIDNodeSetMap().get(C).contains(nbr)) {
++int_comp;
}
}
}
cpm = int_comp - out_comp;
return cpm;
}
public double del_Q
(ComDetGraph g, Partition partition, ComDetNode i, int C, int D, double gamma) {
int numEdges = g.getNumEdges();
double step1output = 0.0;
double step2output = 0.0;
int deg_i_orig = i.getNeighbors().size();
int deg_i_C = deg_i_orig;
int deg_i_D = deg_i_orig;
int sum_deg_C = 0;
int sum_deg_D = 0;
double del_Q = 0;
//O(deg(v))
for (ComDetNode nbr : i.getNeighbors()) {
if (!partition.getIDNodeSetMap().get(C).contains(nbr)) {
--deg_i_C;
}
}
//O(deg(v))
for (ComDetNode nbr : i.getNeighbors()) {
if (!partition.getIDNodeSetMap().get(D).contains(nbr)) {
--deg_i_D;
}
}
//O(|C|)
for (ComDetNode n : partition.getIDNodeSetMap().get(C)) {
sum_deg_C += n.getNeighbors().size();
}
//O(|C|)
for (ComDetNode n : partition.getIDNodeSetMap().get(D)) {
sum_deg_D += n.getNeighbors().size();
}
if (C != D) {
sum_deg_D += i.getNeighbors().size();
}
step1output = (((double) -1 / numEdges) * (deg_i_C)) +
((deg_i_orig / (2 * Math.pow(numEdges, 2)))
* sum_deg_C * gamma);
step2output = (((double) 1 / numEdges) * (deg_i_D)) -
((deg_i_orig / (2 * Math.pow(numEdges, 2)))
* sum_deg_D * gamma);
del_Q = step1output + step2output;
return del_Q;
}
public double del_CPM
(Partition partition, ComDetNode i, int C, int D, double gamma) {
double delta_C = 0.0;
double delta_D = 0.0;
int deg_i_orig = i.getNeighbors().size();
int deg_i_C = deg_i_orig;
int deg_i_D = deg_i_orig;
int n_c = partition.getIDNodeSetMap().get(C).size();
int n_d = partition.getIDNodeSetMap().get(D).size();
double del_CPM = 0;
for (ComDetNode nbr : i.getNeighbors()) {
if (!partition.getIDNodeSetMap().get(C).contains(nbr)) {
--deg_i_C;
}
}
for (ComDetNode nbr : i.getNeighbors()) {
if (!partition.getIDNodeSetMap().get(D).contains(nbr)) {
--deg_i_D;
}
}
delta_C = (double) -deg_i_C + (gamma * (n_c - 1));
delta_D = (double) deg_i_D - (gamma * n_d);
del_CPM = delta_C + delta_D;
return del_CPM;
}
public double del_Q_empty
(ComDetGraph g, Partition partition, ComDetNode i, int C, double gamma) {
int numEdges = g.getNumEdges();
int deg_i_orig = i.getNeighbors().size();
int deg_i_C = deg_i_orig;
int sum_deg_C = 0;
double del_Q = 0;
//O(d)
for (ComDetNode nbr : i.getNeighbors()) {
if (!partition.getIDNodeSetMap().get(C).contains(nbr)) {
--deg_i_C;
}
}
//O(|C|)
for (ComDetNode n : partition.getIDNodeSetMap().get(C)) {
sum_deg_C += n.getNeighbors().size();
}
double del_Q_1 = (((double) -1 / numEdges) * (deg_i_C)) +
((deg_i_orig / (2 * Math.pow(numEdges, 2))) *
sum_deg_C * gamma);
double del_Q_2_1 = ((double) -gamma / 2);
double del_Q_2_2 = ((double) deg_i_orig / numEdges);
double del_Q_2 = del_Q_2_1 * Math.pow(del_Q_2_2, 2);
del_Q = del_Q_1 + del_Q_2;
return del_Q;
}
public double del_CPM_empty
(Partition partition, ComDetNode i, int C, double gamma) {
int deg_i_orig = i.getNeighbors().size();
int deg_i_C = deg_i_orig;
int n_c = partition.getIDNodeSetMap().get(C).size();
double del_CPM = 0;
//O(d)
for (ComDetNode nbr : i.getNeighbors()) {
if (!partition.getIDNodeSetMap().get(C).contains(nbr)) {
--deg_i_C;
}
}
del_CPM = (double) deg_i_C - (gamma * n_c);
del_CPM += gamma;
return del_CPM;
}
public double hLvn (ComDetGraph g, Partition partition, double gamma) {
double h = 0.0;
//O(n) + O(m) approx O(m)
for (int C : partition.getIDNodeSetMap().keySet()) {
h += q(g, partition, C, gamma);//O(deg(v)) for each node v; approx O(m)
}
return h;
}
public double hLdn (Partition partition, double gamma) {
double h = 0.0;
for (int C : partition.getIDNodeSetMap().keySet()) {
h += cpm(partition, C, gamma);
}
return h;
}
public Partition moveNodes
(ComDetGraph g, Partition partition, double gamma) {
double h_old = 0.0;
do {
h_old = hLvn(g, partition, gamma);
List<ComDetNode> nodes = new ArrayList<>(g.getNodeMap().values());
Collections.shuffle(nodes, new Random(123));
for (ComDetNode node : nodes) {
double max_del_H = Double.NEGATIVE_INFINITY;
int nC = partition.getNodeIDMap().get(node);
HashMap<Integer, Double> comm_to_del_H = new HashMap<>();
//O(deg(v)) for each node v
//for a sparse graph O(deg(v) ^ 2) approx O(m)
for (ComDetNode nbr : node.getNeighbors()) {
int C = partition.getNodeIDMap().get(nbr);
if (!comm_to_del_H.containsKey(C)) {
//O(deg(v)) for each node v
double del_H = del_Q(g, partition, node, nC, C, gamma);
comm_to_del_H.put(C, del_H);
max_del_H = Math.max(del_H, max_del_H);
}
}
double del_H_empty = del_Q_empty(g, partition, node, nC, gamma);
comm_to_del_H.put(Integer.MIN_VALUE, del_H_empty);
max_del_H = Math.max(del_H_empty, max_del_H);
int newCom = Integer.MIN_VALUE;
if (max_del_H > 0) {
for (int C : comm_to_del_H.keySet()) {
if (comm_to_del_H.get(C) == max_del_H) {
newCom = C;
break;
}
}
if (newCom == Integer.MIN_VALUE) {
newCom = g.getNumVertices();
++newCom;
}
partition.getNodeIDMap().put(node, newCom);
partition.getIDNodeSetMap().get(nC).remove(node);
if (partition.getIDNodeSetMap().get(nC).isEmpty()) {
partition.getIDNodeSetMap().remove(nC);
}
if (newCom == (g.getNumVertices() + 1)) {
HashSet<ComDetNode> emptyPlOne =
new HashSet<>();
emptyPlOne.add(node);
partition.getIDNodeSetMap().
put(newCom, emptyPlOne);
} else {
partition.getIDNodeSetMap().get(newCom).add(node);
}
}
}
} while (hLvn(g, partition, gamma) > h_old); //time complexity is k
//k is generally very small
return partition;
}
public Partition moveNodesFast (ComDetGraph g, Partition partition, double gamma) {
List<ComDetNode> nodes =
new ArrayList<>(g.getNodeMap().values());
Collections.shuffle(nodes);
LinkedList<ComDetNode> nodeLinked = new LinkedList<>(nodes);
HashSet<ComDetNode> nodesNew = new HashSet<>(nodes);
do {
ComDetNode node = nodeLinked.remove();
nodesNew.remove(node);
double max_del_CPM = Double.NEGATIVE_INFINITY;
int nC = partition.getNodeIDMap().get(node);
HashMap<Integer, Double> comm_to_del_CPM = new HashMap<>();
for (ComDetNode nbr : node.getNeighbors()) {
int C = partition.getNodeIDMap().get(nbr);
if (!comm_to_del_CPM.containsKey(C)) {
double del_CPM = del_CPM(partition, node, nC, C, gamma);
comm_to_del_CPM.put(C, del_CPM);
max_del_CPM = Math.max(max_del_CPM, del_CPM);
}
}
double del_CPM_empty = del_CPM_empty(partition, node, nC, gamma);
comm_to_del_CPM.put(Integer.MIN_VALUE, del_CPM_empty);
max_del_CPM = Math.max(max_del_CPM, del_CPM_empty);
int newCom = Integer.MIN_VALUE;
if (max_del_CPM > 0) {
for (int C : comm_to_del_CPM.keySet()) {
if (comm_to_del_CPM.get(C) == max_del_CPM) {
newCom = C;
break;
}
}
if (newCom == Integer.MIN_VALUE) {
newCom = g.getNumVertices();
++newCom;
}
partition.getNodeIDMap().put(node, newCom);
partition.getIDNodeSetMap().get(nC).remove(node);
if (partition.getIDNodeSetMap().get(nC).isEmpty()) {
partition.getIDNodeSetMap().remove(nC);
}
if (newCom == (g.getNumVertices() + 1)) {
HashSet<ComDetNode> emptyPlOne =
new HashSet<>();
emptyPlOne.add(node);
partition.getIDNodeSetMap().
put(newCom, emptyPlOne);
} else {
partition.getIDNodeSetMap().get(newCom).add(node);
}
for (ComDetNode nbr : node.getNeighbors()) {
int nbrCom = partition.getNodeIDMap().get(nbr);
if (nbrCom != newCom) {
nodeLinked.add(node);
nodesNew.add(node);
}
}
}
} while (!nodeLinked.isEmpty());
return partition;
}
public Partition refinePartition
(ComDetGraph g, Partition partition, double gamma) {
Partition p_refined = singletonPartition(g);
for (HashSet<ComDetNode> comm :
partition.getIDNodeSetMap().values()) {
Partition p_comm = singletonPartitionForComm(comm);
p_refined = mergeNodeSubsets(g, p_comm, comm, gamma);
}
return p_refined;
}
public Partition mergeNodeSubsets
(ComDetGraph g, Partition p, HashSet<ComDetNode> comm, double gamma) {
HashSet<ComDetNode> R = new HashSet<>();
for (ComDetNode n : comm) {
HashSet<ComDetNode> nSingle = new HashSet<>();
nSingle.add(n);
if (checkGammaConnected(nSingle, comm, gamma)) {
R.add(n);
}
}
ArrayList<ComDetNode> R_rnd = new ArrayList<>(R);
Collections.shuffle(R_rnd);
for (ComDetNode node : R_rnd) {
int C = p.getNodeIDMap().get(node);
if (p.getIDNodeSetMap().get(C).size() == 1) {
HashMap<Integer, HashSet<ComDetNode>> T = new HashMap<>();
for (Integer Co : p.getIDNodeSetMap().keySet()) {
HashSet<ComDetNode> com = p.getIDNodeSetMap().get(Co);
if (checkGammaConnected(com, comm, gamma)) {
T.put(Co, com);
}
}
HashMap<Integer, Double> comm_to_prob = new HashMap<>();
for (Integer Co : T.keySet()) {
if (del_CPM(p, node, C, Co, gamma) >= 0) {
double exponent = 10 * del_CPM(p, node, C, Co, gamma);
double prob = Math.exp(exponent);
comm_to_prob.put(Co, prob);
} else {
comm_to_prob.put(Co, 0.0);
}
}
int com = randomWeightedSelection(comm_to_prob);
p.getNodeIDMap().put(node, com);
p.getIDNodeSetMap().get(C).remove(node);
if (p.getIDNodeSetMap().get(C).isEmpty()) {
p.getIDNodeSetMap().remove(C);
}
p.getIDNodeSetMap().get(com).add(node);
}
}
return p;
}
private int randomWeightedSelection(HashMap<Integer, Double> comm_to_prob) {
double totalWt = 0;
for (Integer Co : comm_to_prob.keySet()) {
totalWt += comm_to_prob.get(Co);
}
double rnd = Math.random() * totalWt;
double commWeight = 0;
for (Integer Co : comm_to_prob.keySet()) {
commWeight += comm_to_prob.get(Co);
if (commWeight >= rnd) {
return Co;
}
}
return 0;
}
private boolean checkGammaConnected
(HashSet<ComDetNode> T, HashSet<ComDetNode> S, double gamma) {
double S_not_T_edges = 0.0;
for (ComDetNode node : T) {
for (ComDetNode nbr : node.getNeighbors()) {
if (S.contains(nbr) && !T.contains(nbr)) {
S_not_T_edges++;
}
}
}
double secondTerm = gamma * T.size() * (S.size() - T.size());
return S_not_T_edges >= secondTerm;
}
public Partition louvain (ComDetGraph g, Partition partition, double gamma) {
double q_prev = hLvn(g, partition, gamma);
Partition p_new = moveNodes(g, partition, gamma);
if ((hLvn(g, p_new, gamma) - q_prev) >= 0.001) {
louvain(g, p_new, gamma);
}
return p_new;
}
public Partition leiden (ComDetGraph g, Partition partition, double gamma) {
double cpm_prev = hLdn(partition, gamma);
Partition p_new = moveNodesFast(g, partition, gamma);
if ((hLdn(p_new, gamma) - cpm_prev) >= 0.001) {
leiden(g, p_new, gamma);
}
return p_new;
}
public static void main(String[] args) {
ComDet cd = new ComDet();
ComDetGraph g = new ComDetGraph();
GraphLoader.loadGraph(g, "data/example_graph_changed.txt");
Partition sP = cd.singletonPartition(g);
Partition finalPart = cd.leiden(g, sP, 0.5);
System.out.println(finalPart.getIDNodeSetMap());
}
}
As explained above, I did not expect the moveNodesFast() function to move two nodes into a community and then move one out of that same community because if CPM increases for moving two nodes into a community, CPM shouldn’t increase again for moving one of the nodes out of the same community. In this case, specifically, the node numbered 10 is moved into a community with the node numbered 15, and in a later iteration is moved out of the same community. I don’t understand why this is happening.
New contributor
user25257552 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.