I have a weighted directed graph $G=(V,E)$ with positive weights. Say these vertices represent cities and the weight $w : V_1 \rightarrow V_2$ represents number of students moving into other cities for college. Note here that a city $A$ may have a small population and it may be sending a major proportion of it's outgoing students to another city $B$. If the converse holds true for city $B$, in that, most of it's incoming students come from city $A$ as a proportion of the entire incoming population, we say the weight of the edge connecting city $A$ to city $B$ should be high. So one can think of formalizing the above as a function of $\% inflow$ and $\% outflow$ problem. Now an algorithm like Gervin-Newman algorithm will find communities in such a graph. Here the number of communities detected increases over the number of cities considered. Is there a community detection algorithm for weighted directed graphs where I can pre-specify the number of communities I will be looking to get as output.

  • $\begingroup$ Possibly related question $\endgroup$ – adrianN Jun 16 '16 at 14:50

There are lots of community detection algorithms that need the number of communities as input. For example, Bigclam [1], a matrix factorization approach, needs the number of communities as input. Another example is the seed expansion [2] method that needs the number of communities as input. I'm sure there are many algorithms that take the number of communities as input, but you need to do some research and find the one that is best suitable for you. Looking at these algorithms may be a good start.

You may also think about your own community detection algorithm specific to your problem. For example, you can use seed expansion and start with $k$ seeds (cities) and try to expand those seeds whenever appropriate (appropriate is a vague word, you need some calculations to see if an expansion is appropriate or not).

[1] Yang, Jaewon, and Jure Leskovec. "Overlapping community detection at scale: a nonnegative matrix factorization approach." Proceedings of the sixth ACM international conference on Web search and data mining. ACM, 2013.

[2] Whang, Joyce Jiyoung, David F. Gleich, and Inderjit S. Dhillon. "Overlapping community detection using seed set expansion." Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. ACM, 2013.


A very simple algorithm is as follows:

while #components < n
   delete the lightest edge in the graph

But perhaps you want to define more precisely what you want from your algorithm, e.g. which measure you want to maximize. Most community detection algorithms have some tuneable parameters.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.