Partitioning a graph into subgraphs with overlapping nodes

Question

I'd like to partition a graph into subgraphs with overlapping nodes.

To do a simple partition into two, I could use kernighan_lin_bisection algorithm available in networkx package.

import networkx as nx
from networkx.algorithms.community.kernighan_lin import kernighan_lin_bisection

if __name__ == '__main__':
     G = nx.gnm_random_graph(n=30, m=55, seed=1)
     A, B = kernighan_lin_bisection(G)
   

For creating more than two partitions, it is mentioned here, https://stackoverflow.com/questions/63357626/networkx-kernighan-lin-multipartition, that metis can be used. However, I came across an old post that mentions partitioning with overlapping nodes is not supported in metis. I would like to ask for suggestions on references to algorithms/packages that support partitioning with overlaps.

EDIT: I'd like to partition into subgraphs with >= 4 overlapping vertices. e.g. in the subgraphs presented here . i.e.

for any cluster C1 there must be a cluster C2 such that |C1∩C2|≥4

The number of overlap nodes (overlap size) is 3 and 1. But I want the overlap size to be >=4 overlap nodes.

EDIT 2:

For example, why not simply pick another pure-yellow vertex randomly and add that to the green set, so that yellow and green overlap by exactly 4? And why not pick the remaining 3 pure-yellow vertices and add them to the blue set, so that yellow and blue overlap by exactly 4?

Yes, I could do this. I'm trying the óverlapping communities algorithms available in CDLIB to do the same.

 import networkx as nx
 from cdlib import algorithms
    
if __name__ == '__main__':
 
    g = nx.karate_club_graph()

    coms = algorithms.angel(g, threshold=4, min_community_size=10)
    print(coms.method_name)
    print(coms.method_parameters)  # Clustering parameters)
    print(coms.communities)
    print(coms.overlap)
    print(coms.node_coverage)

Output:

ANGEL
{'threshold': 4, 'min_community_size': 10}
[[14, 15, 18, 20, 22, 23, 27, 29, 30, 31, 32, 8], [1, 12, 13, 17, 19, 2, 21, 3, 7, 8], [14, 15, 18, 2, 20, 22, 30, 31, 33, 8]]
True
0.6470588235294118

From the communities returned, I understand 1 and 3 have an overlap of 4 nodes but 2 and 3 or 1 and 3 don't have an overlap size of 4 nodes. It is not clear to me how the overlap threshold (4 overlaps) has to be specified here algorithms. angel(g, threshold=4, min_community_size=10). Since it is mentioned in the comment below that the "overlap is upper bounded" , I tried setting threshold=4 here. However, from the documentation available for angel

:param threshold: merging threshold in [0,1].

I am not sure how to translate the 4 overlaps to the value that has to be set between the bounds [0, 1]. Could someone please clarify? If there are suggestions on the other overlapping communities algorithms that I could try from CDLIB, I'd be happy to try. I also had a look at the percolation methods implemented in the kclique algorithm of CDLIB. Unfortunately, I am not sure how to specify the overlap threshold here.

I'm really sorry for not being clear, I'm new to this field and I am learning from here.

Answer 1

I never heard of any algorithm with the constraint of having an overlap between communities larger than a given threshold (4 here).

But I suggest the following: turn your graph into its line graph, use a classical node partitioning method that gives a hierarchy of communities, and then choose a partition that fits your requirements.

More details:

• the line graph is the graph in which the nodes are the links of your original graph, and these nodes are linked together if corresponding links have an extremity in common, see wikipedia on line graph.
• classical community detection algorithms partition nodes into disjoint sets; doing so on the line graph will produce a partition of the edge set, with some nodes in several communities (overlap).
• many classical community detection algorithms actually produce a hierarchical decomposition, often encoded as a dendrogram, i.e. a tree of communities, sub-communities, sub-sub-communities, and so on, see wikipedia on dedrograms.
• a partition into communities then is a choice of a place to cut this tree, wherever it fits your needs; for instance, one may maximize a quality function and a scale parameter, see e.g. Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View
• therefore you may choose a cut maximizing a quality function while satisfying your requirement; you may for instance start with the optimal partition regarding the quality function, and then move the cut to fit your overlap requirement.

Good luck, please keep us informed of any progress :)

Answer 2

Depends what you want to do with the "partition with overlapping nodes".

• There is this survey about overlapping community detection: https://dl.acm.org/doi/10.1145/2501654.2501657
• The Clique_percolation_method is one such method.