What is the difference between graph clustering and community detection methods?

Basically, the goal of graph clustering and community detection methods are to compute clusters. Is there any difference between them?

No. Quoting for example from Community detection in graphs, a recent and very good survey by Santo Fortunato, "This feature of real networks is called community structure (Girvan and New- man, 2002), or clustering". There is little point in further elaborating the point, really. I have the feeling that in early social network analysis style papers the networks tended to be simple (not weighted), but it is not something I would want to argue, nor is it important. The answer to your question is no.

In Detecting Community Structures in Networks, M.Newman defines graph clustering as a specific problem defined in the context of computer science.

Let's consider some calculation, which can be split in several simpler operations. These are represented as nodes in our network. The links correspond to dependencies between the operations, i.e. the result of one operation is needed by another one. The problem consists in distributing the operations over several processors, for parallel processing purposes. In other words, we want to assign each node (operation) to a specific class (processor), i.e. we want to partition the graph.

There are three constraints, though. The first is to obtain a predefined number of communities, because the number of processors is obviously known in advance. The second is to get a balanced load: we want each processor to roughly perform the same number of operations. In terms of graph, we want the communities to contain approximately the same number of nodes. The third is to get the lowest possible communication between processors, because it slows down the process. So, in terms of graph, we want to minimize the number of links between communities.

So, from this point of view, community detection can be considered as a more general problem than graph clustering. The third constraint is enforced in both problems, but the number and sizes of the communities is not known a priori in community detection.

• This answer is misleading. When the number and sizes of the clusters are known a priori the problem is known as graph partitioning, not graph clustering. The wiki page is not great, but a start: en.wikipedia.org/wiki/Graph_partition. May 30, 2013 at 10:24
• my bad, I thought both tasks were similar. Their differences are highlighted here: cc.gatech.edu/dimacs10 May 30, 2013 at 11:46

These two different names are given to the same thing by different communities of scientists, depending on whether one would like to emphasize the social-networks motivation or not. Perhaps somebody is defining clustering and community detection as different things, but most of the people that study one of them would not be able to tell you why they are not using the other term.

If a big network is clustered into two pieces, what guarantees you that this two part is two communities? Two clusters have low connection does not mean that each cluster have similar kind of nodes or nodes have similar kind of connections (therefore community). Think of social networks graph. There are surely lots of communities. Also by clustering algorithms you can cluster it into two pieces. In this case, would you call each pieces a community. ? My answer is no. Because, the two clusters might be people of two geographic region. And then those are surely not communities.

Clustering algorithms cares only about minimum cut, not about node similarity or connection similarity or dense connection. Plus in clustering algorithms, the number of clusters should be predefined.

Community detection algorithms, they care about density, they find the denser part of the network and those kind of algorithms (I have seen so far) does not need to predefine the number of communities.

However, clustering algorithm can be used to find communities, then, as it does not guarantee that each cluster hold a good community structure, each cluster should be carefully examined.

"one cannot trivially apply community discovery to solve clustering and vice versa. despite their similarities, there are important diﬀerences in the approaches. Community discovery assumes sparse connections, while clustering can work with dense datasets ; in clustering we usually deal with attributes with multiple types, while community discovery usually deals with a single attribute type – edges – often binary, in the case of unweighted networks" for more information read the following paper : "On the Equivalence Between Community Discovery and Clustering" by Riccardo Guidotti and Michele Coscia