# Partitioning a graph into subgraphs with overlapping nodes

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.

• Are you looking for a partition that optimises some quantity, e.g. that minimises the number of edges between vertices in different parts of the partition? If so, please say what it is -- without this, any arbitrary partition is a valid answer. Please also be clear about how overlapping vertices/edges should be treated. – j_random_hacker Jan 1 at 21:10
• @j_random_hacker Could you please check my edit? – Natasha Jan 2 at 6:06
• Thanks for updating, but it's still not clear to me what your criteria are. 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? – j_random_hacker Jan 2 at 8:33
• I think you need to formalize your problem a bit more. Usually the overlap is upper bounded, not lower bounded like here: hal.archives-ouvertes.fr/hal-01399184 You mentioned Kernighan-Lin, so I guess you are interested in mincut and a fixed number of clusters such that each node is in at least one cluster? There are some generalizations of min-k-cut with overlap: link.springer.com/chapter/10.1007/3-540-58338-6_99 – maxdan94 Jan 2 at 11:11
• Can you perhaps share the story behind the problem to make it clearer for us that we're not solving an XY-problem? – Pål GD Jan 3 at 20:05

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 :)

• Thanks a lot for the detailed suggestions. Could you please check my edit? – Natasha Jan 2 at 14:11
• Thanks for adding some details. However, I do not think there is any off-the-shelf method for your problem, that is quite original, imho. This is why I suggested working on a dendrogram. It still needs some work to give the results you want, but I do not see any simpler option right now. – Matthieu Latapy Jan 2 at 17:27

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

• Could you please check my edit? – Natasha Jan 2 at 14:12