4

I want to evaluate and compare the result of my community detection algorithm in R. My algorithm doesn't allow overlapping, and there are some nodes that are not treated. For example, for the Zachary Karate club, I have 1 node not treated. I've found a lot of metrics (NMI, ARI, Modulaity(Q), Purity, Rank Index...), and I don't which ones are the best. Currently, I'm use the modularity, purity and the Rank Index.

Are those chosen evaluation metrics are sufficient?

For example, for the Rank Index is the RI(P,R)= (a+d)/(a+b+c+d) where a, b, c and d be the number of pairs of nodes that are respectively in a same community according to P and R, in a same community according to P but in different communities according to R, in different communities as given by P but in a same community as given by R, and in different communities according to both P and R, and P = {p1, p2, . . . , pk} be the output of a community detection algorithm applied to graph G =< V,E >, and R = {r1, r2, . . . , rn} be the real community structure.

So if I deal with a large graph, how can I calculate those values? Where can I find R(the real community structure)?

1
  • Reworded for clarity.
    – Alex K
    Commented Mar 9, 2015 at 22:49

1 Answer 1

7

You are confusing two types of measures: internal and external criteria, as defined for clustering problems (see this page).

  • Internal criterion: blindly assesses the quality of the detected community structure. This means you don't have any reference structure to which you could compare the estimated structure. Ex.: Modularity, Conductance...
  • External criterion: you compare the estimated community structure to a reference community structure (aka. ground truth, gold standard, etc.). Ex.: NMI, (A)RI, purity...

There's not a 'best' measure: they are all different, and rely on a different notion of how the performance of a community detection algorithm should be quantified. A more relevant question would be: which measures are appropriate to your situation?

Indeed, the measures you list all require a partition of the node set. You mentioned your algorithm ignores certain nodes, so this could be a problem. A basic workaround would consist in considering each ignored node constitutes its own community. Alternatively, certain measures defined for overlapping community structures are able to handle this case.

Another important point is the data you're using for testing your algorithm. Do you have the actual community structures for these data? If not, then you can't use external criteria at all.

Note that most external criteria consider a community structure is just a partition (in the mathematical sense) of the node set. Consequently, they rely on the comparison of the reference and estimated partitions. This is due to the fact they all originate from the field of cluster analysis. The problem with this is they completely fail to take the network links into account. Yet, a community structure is not just a partition of the node set: the way links are distributed over this partition is very important. For this reason, you might want to assess your community structure in a more qualitative way, for instance by comparing the topological properties of the detected communities ( see Orman'12). You can alternatively change the existing measures to make them take links into account (see Labatut'13). Not that I particularly want to cite myself, but the papers seem relevant.

Regarding the concrete processing of those measures, you might want to look at the documentation of the tool you're using to perform the community detection: some of them are bundled with performance measures. For instance, if you use igraph, there is a function just for that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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