CODEWITHSUNDEEP
graphgraph-theorygraph-algorithmpartitioningcomplex-networks
Saeed Hajebi
Saeed Hajebi

Reputation: 31

Need a graph partitioning technique

I have a graph G = (V,E), with V the set of nodes, and E the set of edges. I have two types of nodes: Source nodes, and Consumer nodes (the number of Source nodes are way lower than the Consumer nodes). The nodes have geographic positions.

I want to partition the graph into a collection of sub-graphs which are:

a- connected sub-graphs,

b- of a proper size (the size of the partitions must be balanced; however not necessarily equal. e.g. between 2000-3000 nodes),

c- the partitions should preferably be directly connected to a Source. So if there is no Source in a partition, the path between the partition to a Source node should not include any nodes in the other partitions. (The most important constraint)

d- The nodes in a partition should be close to each other (geographically)

The minimum cut set is preferable. The Source nodes can be isolated from the other partitions (can be in partitions of one; only themselves).

Is there any existing partitioning technique that I can use? Any kind of help is fully appreciated.

Upvotes: 3

Views: 436

Answers (1)

Vincent Labatut
Vincent Labatut

Reputation: 1808

There are some works based on the modularity measure used in community detection. For instance, in Chen et al. 2012, they extend the modularity to spatial, weighted, directed networks. The spatial distance is used to modulate the link weights.

This would fit your points a) and d). However, the (regular) modularity is not designed to find communities of similar size, so it won't fulfil your point b). Maybe you'd better use a classic minimum-cut approach, by modifying a measure such as the conductance in a way similar to that of Chen et al.

For your point c), I must say I never met this type of constraint before, and I find it very interesting. I guess you could try to perform some bi-criterion optimization, trying to minimize both conductance (or modularity) and a criterion such as the average distance to the closest source. But that would not guarantee the respect of point c). You can also force the number of detected communities so that it is less than the number of sources.

Upvotes: 1

Related Questions