This is WAPAL by Kaya Oğuz and Osman Doluca, presented at IISEC 2022, International Informatics and Software Engineering Conference.

The paper is available at https://ieeexplore.ieee.org/document/9998238. Please cite as

Oğuz K, Doluca O, (2022) "Extending APAL to Detect Overlapping Communities in Weighted Networks," 2022 3rd International Informatics and Software Engineering Conference (IISEC), 2022, pp. 1-4, doi: 10.1109/IISEC56263.2022.9998238

WAPAL is based on APAL. You can access source code at https://github.com/koguz/APAL/ and the APAL paper at https://www.sciencedirect.com/science/article/abs/pii/S0020025521008318

WAPAL uses its own implementation of the Graph ADT with weights. It is very straightforward to use this Graph class.

from Graph import *

g = Graph()
# add a vertex, the type can be anything, int, string or any other class
g.add_vertex(1) 
# or a list of vertices
g.add_vertices([1, 2, 3, 4])
# then, add an edge, say between 1 and 3 with a weight of 2.1
g.add_edge(1, 3, 2.1)

Once a graph is populated with vertices and weighted edges, you can use it in WAPAL.

To run WAPAL, create a WAPAL object, assign your graph to it. Then, run run_wapal(f) with the fitness value f, between 0 and 1. The fitness value is defined as the expected intraconnectivity times expected normalized average of weights.

from WAPAL import *

wapal = WAPAL()
wapal.graph = g # the graph we have defined above
wapal_clusters = wapal.run_wapal(0.75)

The overlapping communities found in Graph g will be in the wapal_clusters variable. This repository also includes the CompareClusters class so that you can compare the result to a ground truth, if you have one. Assuming that the real clusters are in clusters variable, use it as follows for normalised mutual information (NMI) metric that is extended for overlapping communities as detailed in

Andrea Lancichinetti et al 2009 New J. Phys. 11 033015, https://iopscience.iop.org/article/10.1088/1367-2630/11/3/033015

The result has a range of [0,1] where values closer to 1 are of communities that are more alike, therefore represent better results.

from CompareClusters import CompareClusters as CC

cc = CC(g.vertices, clusters, wapal_clusters)
wapal_result = cc.nvi_overlapping()