A novel metric for community detection
Ke-ke Shang Michael Small Yan Wang Di Yin Shu Li







A novel metric for  community detection
    
Ke-ke Shang1Ke-ke Shang is the corresponding author,
Michael Small2,3,
Yan Wang1,
Di Yin1,
Shu Li1,


1 Computational Communication Collaboratory, Nanjing University, Nanjing, 210093, P.R. China

2 Complex Systems Group, Department of Mathematics and Statistics, The University of Western Australia, Crawley, Western Australia 6009, Australia

3 Mineral Resources, CSIRO, Kensington, WA, 6151, Australia


 kekeshang@nju.edu.cn, 
 keke.shang.1989@gmail.com

    December 30, 2023
==============================================================================================================================================================================================================================================================================================================================================================================================================================================================================



Research into detection of dense communities has recently attracted increasing attention within network science, various metrics for detection of such communities have been proposed. The most popular metric – Modularity – is based on the so-called rule that the links within communities are denser than external links among communities, has become the default.
However, this default metric suffers from ambiguity, and worse, all augmentations of modularity and based on a narrow intuition of what it means to form a “community”. We argue that in specific, but quite common systems, links within a community are not necessarily more common than links between communities. Instead we propose that the defining characteristic of a community is that links are more predictable within a community rather than between communities. In this paper, based on the effect of communities on link prediction, we propose a novel metric for the community detection based directly on this feature. We find that our metric is more robustness than traditional modularity. Consequently, we can achieve an evaluation of algorithm stability for the same detection algorithm in different networks. Our metric also can directly uncover the false community detection, and infer more statistical characteristics for detection algorithms.  





§ INTRODUCTION

Network substructures – communities – appear in many complex networks and are frequently associated with important functions of those networks <cit.>. Research into  community detection has recently attracted increasing attention <cit.>. Meanwhile, the design of metrics to evaluate community detection has also been a recent focus of investigation <cit.>. The metrics of community structure can be generally grouped within three classes: (1) based on the density of internal links (links within the community)<cit.>; (2) based on the density of external links <cit.>; and, (3) based on the the density of both internal links and external links <cit.>. However, we argue that all these metrics are based on an unnecesary assumption — that the density of internal links must be greater than that of external links. While this is true for communities in many real networks, it is not always the case. Clearly, of course, this depends on what one means by a “community”, but we argue here that the natural intuition for community does not necessarily imply increased link density. As depicted in Fig. <ref>, there are two typical communities in the natural world. Figure <ref> (a) shows a mode network for which links within communities are denser than those between groups, however, Fig.<ref> (b) shows another quit typical community. In this case, Fig. <ref> depicts a typical work unit, and the associated subordinate relationships. The community in this case, a common work association, exhibits hierarchical rather than simply dense link structure. Moreover, the nodes group within the same region of geodesic space also can be called as the community <cit.>. Hence, based on different kinds of real-world communities, we argue an intuitive generalisation of the existing definition of community structure. 



More importantly, the default metric Modularity <cit.> and its associated generalisations and extensions <cit.> are also  based on the preceding density assumption. In this paper we focus on the fact that links within a community are more predictable than external links <cit.> — due simply to the assumption that relationships within a real community are stronger (and perhaps more structured) than the external relationships. Hence, we adopt ideas from link prediction theory – where links can be predicted based on statistical characterisation of network structure <cit.> — to measure the predictability of network substructure. We propose a new metric for community detection which is based on the principle that links within a community should achieve a higher link prediction performance than external links <cit.>. Link prediction should work best within communities and worst between communities.

In this paper, we employ 5 famous network open datasets to be tested. First, we use 8 traditional community detection algorithms to uncover the communities, every algorithm has its corresponding communities for each network. Second, we analyze the link prediction performance (predictability) for the internal links and that of all links respectively. Third, we compare the performance of above two kinds of links for each network, and normalize the difference between them as the score of each detection algorithm. Meanwhile, we test the default metric Modularity for each network. We find that our metric is more stable and consistent than Modularity for each detection algorithm in all 5 networks. Our metric can also uncover more statistical rules for each detection algorithm. We suggest that our metric not only can be more widely used, but will also achieve a more stable estimate for each algorithm. Furthermore, our metric can directly expose the failure of current community detection algorithms.



§ NETWORK DATA

As listed in Table <ref>, we employ 5 open traditional network datasets that have been widely applied for community detection or link prediction problems. (1) Karate club <cit.>: A node represents one club user, a link indicates that there is a relationship between a pair of nodes. Karate club network is the common used data for community detection <cit.>. (2) Adjectives and nouns (Adjnoun)<cit.>: a node represents one word (adjective or noun), a link indicates that any two words are next to each other in the book. Adjectives and nouns network is also the common used data for community detection <cit.>. (3) Polbooks <cit.>: a node represents one book about US politics which is sold by Amazon.com, a link stands for there is a pair of nodes are purchased by a same buyer. Polbooks is the common used data for both community detection and link prediction <cit.>. (4) C.Elegans network <cit.>: A node represents one neuron, a link indicates a synapse or a gap junction between a pair of nodes. C.Elegans network is the common used data for link prediction <cit.>. (5) Usair <cit.>: A node represents one airport, a link indicates there is a fight line between a pair of nodes. Usair network is also the common used data for link prediction <cit.>.
  





§ METHODS




 §.§ Metric for community detection

At the start, we use the detection algorithm to uncover the communities of network. Based on the assumption that the internal links within communities are more predictable than external or all links <cit.>, we adopt three famous link prediction algorithms to test the predictable of internal links, then get the prediction accuracy scores of internal links S_in^1, S_in^2, S_in^3, and those of all links S_all^1, S_all^2,S_all^3. Then we can achieve the detection score, 
    S_pr=∑_i=1^n S_in^i - S_all^i/S_all^i/n.(1)
 Particularly, we can adopt the link prediction algorithm for tree-like networks <cit.> if the community structure is similar to the Figure.<ref> (b).
The accuracies of link prediction algorithms for all links (S_all) will have values in [0.5,1) except for that of Preferential attachment index <cit.>. In addition, theoretically, S_in should higher than S_all. Hence, for an effective community detection algorithm, the S_pr should values in (0,1) when we do not adopt the Preferential Attachment index [The AUC of the Preferential attachment index is usually lesser than 0.5.]. Obviously, the higher value of S_pr means the better performance of community detection algorithms. In detail, the negative value of S_pr means the disadvantage role of the detected communities for link prediction. However, previous studies show that the community plays an advantageous role for  link prediction. That is, the corresponding detection algorithm is failing when S_pr≤0. Generally, the effective detection algorithm should achieve a positive S_pr value.

Moreover, we can also  extend the metric for overlapping communities. By generalising out previous arguments, we follow the principle that the scores of internal links should bigger than those of overlapping links, and the scores of overlapping links should bigger than those of external links. In this paper, we pay attention to the basic non-overlapping community problem.



 §.§ Link prediction problem


The graph G can be completely described by a vertex set V, all pair of nodes set U, and an edge set E: G=(V,E). The vertex set is stationary and does not evolve. Elements of the edge set are unordered pairs of elements of the vertex set: e=(v_i,v_j)∈ E where v_i,v_j∈ V. The pair (v_i,v_j) occurs in at most one edge e∈ E. The edge set E is divided into two parts E^T and E^P where E^T∪ E^P=E and E^T∩ E^P=∅. The division into E^P (typically including 10% of the observed links in <cit.>) and E^T (typically 90% of the observed links) is arbitrary and will be used for scoring purposes. The static[And this is all that we consider here.] link prediction problem can be stated: given the training link set E^T and the probe link set E^P (and also V), E” = U \ E, then predict a small part of unobserved links in E” and that of fake links in E^P. That is, if we know some of the links of a network — those links being partitioned into the training set E^T and the probe set E^P — which we have observed, is it possible to predict the existence (or otherwise) of unobserved or fake links. The unobserved links are members of E” and may be said to either exist or be non-existent. Generally, the link prediction scores of existence links are bigger than those of fake links or non-existence links. 



  §.§.§ Link prediction algorithms

The friend of our friend is our friend also, as is figured by a closed triangular structure. This common intuition is the basis of all local link prediction algorithms, with the except of the preferential attachment index. Newman et al. first use this rule to study the cooperation behaviors of scientists <cit.>, which then provided a foundation for link prediction problem <cit.>. Based on these studies, the well-known common neighbors index (CN) has been proposed:

    S_ij^CN=|Γ(i,j)|,(2)

where Γ(i,j) denotes the set of common neighbors of the nodes i and j. The algorithm indicates that if you have a common friend with another person, there is a possible relationship between you. That is to say the friend (common neighbors) of friend is our friend.

Leicht-Holme-Newman index (LHN1) <cit.> directly compare the number of common neighbors and the value which is proportional to the possible number of that:

    S_ij^LHN1= |Γ(i,j)|/k(i) × k(j).(3)


Hub depressed index (HDI) <cit.> is associated with the hub promoted index (HPI) <cit.>, both of them are based on the role of common neighbors. Hub promoted index aims at the improving of hub nodes effects. On the contrary, hub depressed index aims at the decreasing of hub nodes effects:

    S_ij^HDI= |Γ(i,j)|/max{k(i) + k(j)}.(4)




  §.§.§ Metric for link prediction algorithms

The Area under Receiver Operating Characteristic Curve (AUC) [With the abscissa measuring the false positive rate, and the ordinate the true positive rate,  we can then draw a Receiver Operating Characteristic Curve (ROC). Statistically, the area under the ROC should be between 0.5 and 1. If the area is greater than 0.5, we can suggest that our method is effective. If the area equals to 0.5, then our method is invalid. The case that the area is less than 0.5, is unrealistic — in this situation the method performs so poorly that it would be better to do the reverse of what is predicted.] was originally applied to evaluate communication schemes and has since been widely applied more generally to measure prediction accuracy <cit.>. We use AUC as a link prediction accuracy measure for networks. Only the information of E^T is allowed to be used to compute the performance score, we compare the prediction scores of m pairs of nodes from E^P and E” randomly, if there are m' times that the score measured from E^P is bigger than the score measured from E” and m” times that the two scores are equal, then, the prediction accuracy AUC=(m'+0.5m”)/m. In this letter, we compute the AUC of all algorithms 100 times independently.




§ RESULTS

Similar to previous studies <cit.>, we focus on correctly identifying links within communities. Assuming that links within a community are more predictable than external links, we compare the accuracy of link prediction for internal links and that of all (internal and external) links. Here, we adopt 8 traditional community detection methods to be tested. (1) Kclique algorithm is based on the relationship between nodes and subgraphs <cit.>; (2) Fast greedy (FG) adopts the greedy optimization method <cit.>;  (3) Girvan-Newman algorithm (GN) is based on the principle of edge betweenness <cit.>; (4) Label Propagation algorithm (LP) is based on the propagation process of labeled nodes <cit.>; (5) the leading eigenvector of modularity matrix is the key for Leading eigenvector algorithm (LE) <cit.>; (6) MultiLevel algorithm actually is the multi-resolution version of modularity <cit.>; (7) WalkTrap algorithm adopts the random walk method <cit.>; and (8) InfoMap algorithm is based on random walk dynamics <cit.>. These diverse algorithms make it more accurate for analyzing the predictability of community structures. 



 §.§ Internal links versus all links

As shown in Figure. <ref>, we can see that, for almost all link prediction algorithms, the prediction accuracies of internal links is higher than that of all links. That is to say, the internal links are more predictable than all links, further than external links. This result also provides the design basis for our community detection metric. We also observe that for the detection algorithms FG, LE and Multilevel, the CN accuracies of internal links are obviously lower than those of all links in the Adjnoun network and the Usair network.



Hence, to clearly distinguish the qualities of detection algorithms. As depicted in Figure. <ref>, we show the average link prediction accuracies of all three link prediction algorithms for each community detection algorithm. We can clearly see that, in general, the prediction accuracies of internal links are higher than those of all links. In detail, for the algorithms Kclique, Girvan-Newman and WalkTrap, the prediction accuracies of internal links always are higher than that of all links. On the contrary, for algorithms FG, LE and Multilevel, the prediction accuracies of internal links are lower than those of all links in the Adjnoun network and the Usair network, namely these community detection algorithms are not effective for the Adjnoun network and the Usair network.





 §.§ Predictability versus Modularity

In what follows, we directly compare our metric and the default metric Modularity <cit.>. As shown in Figure. <ref> (a), under our metric, we can see that the same community detection algorithm performs similar in different networks. On the contrary, under the default metric Modularity, the performance of the same community detection algorithm varies greatly from network to network (Figure. <ref> (b)). Hence, as shown in Table. <ref>, we adopt the standard deviation to further measure the robustness for these two metrics. The standard deviation of our metric is much less than that of Modularity. Obviously, our metric Predictability is more stable than Modularity. Hence, we infer that the Modularity cannot consistently measure a community detection algorithm in different networks. Our metric does lead to a consistent  and stable evaluation for the same community detection algorithm between different networks. 





In addition, our metric can directly and carefully judge the failure of community detection algorithms – if a community detection algorithm achieves a negative Predictability score, we can infer the failure of community detection. For example, as depicted in Figure. <ref> (a), for the Adjnoun network and the Usair network, the Fast greedy algorithm and Multilevel algorithm both achieve the negetive scores, which means that they cannot divide the communities successfully.

More importantly, we also find that the algorithms Kclique, Girvan-Newman and WalkTrap are successful for each network (Figure. <ref> (a)). Furthermore, Modularity can indirectly measure the ( Q ≥ 0.3<cit.>) the failure of community detection. However, as shown in Figure. <ref> (b), we cannot find any successful community detection algorithm for all networks. We suggest that the weak robustness of Modularity is the key reason for that phenomenon. And our metric Predictability can capture more common statistical characteristics for the community detection algorithms. 

As shown in Figure. <ref> (b), we can find that the results of the Polbooks network are more stable than other networks, which means that Modularity also can capture the common statistical characteristic for the community detection algorithm. However, as shown in Figure. <ref> (a), we not only find the results of Polbooks network are stable and always bigger than 0, but also observe that both the results of Karate network and C.Elegans network are stable and always bigger than 0. That phenomenon further suggest that our metric can capture more common statistical rules for community detection algorithms. Our metric can find more networks that can easy be divided by the community algorithm. 



§ CONCLUSION AND DISCUSSION


Though there are many competing  metrics with which to evaluate community detection, the different statistical characteristics between internal links of communities and external links of communities is always the key principle. In this paper, we argue that the principle that the density of internal links is higher than that of external links, is not a universal characteristic of all “communities” for all real-world networks. Hence, we propose the Predictability metric which is based on the principle that internal links are more predictable than external links. We find that our metric can reliably evaluate the performance of the same community detection algorithms across a range of different networks, however, the default metric Modularity is rather unstable. We infer that the unstable performance of Modularity is due to the ill-defined of communities: the density of links within communities is higher than that of external links.

Furthermore, our metric can evaluate the performance of community detection algorithm more carefully – the failure of community detection can be uncovered and more statistical rules can be found by our metric. In detail, the negative score of Predictability directly reflects the bad or failure level of a community detection algorithm, inversely, the positive score of Predictability reflects the good level of a community detection algorithm.  We also can find more networks that can be divided by the community algorithm.
We suggest that the different predictabilities between internal links and external links provide more information than the traditional principle of community detection metrics, our metric can help researchers further discuss the precise definition of the community detection problem.





aaai





[Adamic and Glance2005]adamic2005political
Adamic, L. A., and Glance, N.
2005.
The political blogosphere and the 2004 us election: divided they
  blog.
In Proceedings of the 3rd International Workshop on Link
  Discovery,  36–43.
ACM.

[Breiger, Boorman, and
  Arabie1975]breiger1975algorithm
Breiger, R. L.; Boorman, S. A.; and Arabie, P.
1975.
An algorithm for clustering relational data with applications to
  social network analysis and comparison with multidimensional scaling.
Journal of Mathematical Psychology 12(3):328–383.

[Cannistraci, Alanis-Lobato, and
  Ravasi2013]cannistraci2013link
Cannistraci, C. V.; Alanis-Lobato, G.; and Ravasi, T.
2013.
From link-prediction in brain connectomes and protein interactomes to
  the local-community-paradigm in complex networks.
Scientific Reports 3:1613.

[Chakraborty et al2016]chakraborty2016genperm
Chakraborty, T.; Kumar, S.; Ganguly, N.; Mukherjee, A.; and Bhowmick, S.
2016.
Genperm: a unified method for detecting non-overlapping and
  overlapping communities.
IEEE Transactions on Knowledge and Data Engineering
  28(8):2101–2114.

[Chakraborty et al2017]chakraborty2017metrics
Chakraborty, T.; Dalmia, A.; Mukherjee, A.; and Ganguly, N.
2017.
Metrics for community analysis: A survey.
ACM Computing Surveys (CSUR) 50(4):54.

[Clauset, Newman, and
  Moore2004]clauset2004finding
Clauset, A.; Newman, M. E.; and Moore, C.
2004.
Finding community structure in very large networks.
Physical Review E 70(6):066111.

[Ding et al2016]ding2016prediction
Ding, J.; Jiao, L.; Wu, J.; and Liu, F.
2016.
Prediction of missing links based on community relevance and ruler
  inference.
Knowledge-Based Systems 98:200–215.

[Fortunato and
  Barthelemy2007]fortunato2007resolution
Fortunato, S., and Barthelemy, M.
2007.
Resolution limit in community detection.
Proceedings of the National Academy of Sciences 104(1):36–41.

[Fortunato and
  Hric2016]fortunato2016community
Fortunato, S., and Hric, D.
2016.
Community detection in networks: A user guide.
Physics Reports 659:1–44.

[Girvan and Newman2002]girvan2002community
Girvan, M., and Newman, M. E.
2002.
Community structure in social and biological networks.
Proceedings of the National Academy of Sciences
  99(12):7821–7826.

[Hanley and McNeil1982]hanley1982meaning
Hanley, J. A., and McNeil, B. J.
1982.
The meaning and use of the area under a receiver operating
  characteristic (roc) curve.
Radiology 143(1).

[Krause et al2003]krause2003compartments
Krause, A. E.; Frank, K. A.; Mason, D. M.; Ulanowicz, R. E.; and Taylor, W. W.
2003.
Compartments revealed in food-web structure.
Nature 426(6964):282.

[Lancichinetti, Fortunato, and
  Radicchi2008]lancichinetti2008benchmark
Lancichinetti, A.; Fortunato, S.; and Radicchi, F.
2008.
Benchmark graphs for testing community detection algorithms.
Physical Review E 78(4):046110.

[Leicht, Holme, and
  Newman2006]leicht2006vertex
Leicht, E. A.; Holme, P.; and Newman, M. E.
2006.
Vertex similarity in networks.
Physical Review E 73(2):026120.

[Li, Ng, and Ye2013]li2013multicomm
Li, X.; Ng, M. K.; and Ye, Y.
2013.
Multicomm: Finding community structure in multi-dimensional networks.
IEEE Transactions on Knowledge and Data Engineering
  26(4):929–941.

[Liben-Nowell and
  Kleinberg2007]liben2007link
Liben-Nowell, D., and Kleinberg, J.
2007.
The link-prediction problem for social networks.
Journal of the American Society for Information Science and
  Technology 58(7):1019–1031.

[Lü and Zhou2010]lu2010link
Lü, L., and Zhou, T.
2010.
Link prediction in weighted networks: The role of weak ties.
EPL 89(1):18001.

[Lü and Zhou2011]lu2011link
Lü, L., and Zhou, T.
2011.
Link prediction in complex networks: A survey.
Physica A: Statistical Mechanics and its Applications
  390(6):1150–1170.

[Lü et al2015]lu2015toward
Lü, L.; Pan, L.; Zhou, T.; Zhang, Y.-C.; and Stanley, H. E.
2015.
Toward link predictability of complex networks.
Proceedings of the National Academy of Sciences
  112(8):2325–2330.

[Mahmood and Small2015]mahmood2015subspace
Mahmood, A., and Small, M.
2015.
Subspace based network community detection using sparse linear
  coding.
IEEE Transactions on Knowledge and Data Engineering
  28(3):801–812.

[Mahmood et al2016]mahmood2016using
Mahmood, A.; Small, M.; Al-Maadeed, S. A.; and Rajpoot, N.
2016.
Using geodesic space density gradients for network community
  detection.
IEEE Transactions on Knowledge and Data Engineering
  29(4):921–935.

[Newman and Girvan2004]newman2004finding
Newman, M. E., and Girvan, M.
2004.
Finding and evaluating community structure in networks.
Physical Review E 69(2):026113.

[Newman2001]newman2001clustering
Newman, M. E.
2001.
Clustering and preferential attachment in growing networks.
Physical Review E 64(2):025102.

[Newman2006a]newman2006finding
Newman, M. E.
2006a.
Finding community structure in networks using the eigenvectors of
  matrices.
Physical Review E 74(3):036104.

[Newman2006b]newman2006modularity
Newman, M. E.
2006b.
Modularity and community structure in networks.
Proceedings of the National Academy of Sciences
  103(23):8577–8582.

[Palla et al2005]palla2005uncovering
Palla, G.; Derényi, I.; Farkas, I.; and Vicsek, T.
2005.
Uncovering the overlapping community structure of complex networks in
  nature and society.
Nature 435(7043):814.

[Pons and Latapy2005]pons2005computing
Pons, P., and Latapy, M.
2005.
Computing communities in large networks using random walks.
In International Symposium on Computer and Information
  Sciences,  284–293.
Springer.

[Radicchi et al2004]radicchi2004defining
Radicchi, F.; Castellano, C.; Cecconi, F.; Loreto, V.; and Parisi, D.
2004.
Defining and identifying communities in networks.
Proceedings of the National Academy of Sciences
  101(9):2658–2663.

[Ravasz et al2002]ravasz2002hierarchical
Ravasz, E.; Somera, A. L.; Mongru, D. A.; Oltvai, Z. N.; and Barabási,
  A.-L.
2002.
Hierarchical organization of modularity in metabolic networks.
Science 297(5586):1551–1555.

[Redner2008]redner2008networks
Redner, S.
2008.
Networks: teasing out the missing links.
Nature 453(7191):47–48.

[Rosvall and Bergstrom2008]rosvall2008maps
Rosvall, M., and Bergstrom, C. T.
2008.
Maps of random walks on complex networks reveal community structure.
Proceedings of the National Academy of Sciences
  105(4):1118–1123.

[Shang et al2019]shang2019link
Shang, K.-k.; Li, T.-c.; Small, M.; Burton, D.; and Wang, Y.
2019.
Link prediction for tree-like networks.
Chaos: An Interdisciplinary Journal of Nonlinear Science
  29(6):061103.

[Shang, Small, and
  Yan2017]shang2017fitness
Shang, K.-k.; Small, M.; and Yan, W.-s.
2017.
Fitness networks for real world systems via modified preferential
  attachment.
Physica A: Statistical Mechanics and its Applications
  474:49–60.

[Spirin and Mirny2003]spirin2003protein
Spirin, V., and Mirny, L. A.
2003.
Protein complexes and functional modules in molecular networks.
Proceedings of the National Academy of Sciences
  100(21):12123–12128.

[Xie and Szymanski2012]xie2012towards
Xie, J., and Szymanski, B. K.
2012.
Towards linear time overlapping community detection in social
  networks.
In Pacific-Asia Conference on Knowledge Discovery and Data
  Mining,  25–36.
Springer.

[Yan and Gregory2012]yan2012finding
Yan, B., and Gregory, S.
2012.
Finding missing edges in networks based on their community structure.
Physical Review E 85(5):056112.

[Zachary1977]zachary1977information
Zachary, W. W.
1977.
An information flow model for conflict and fission in small groups.
Journal of Anthropological Research 33(4):452–473.







§ ACKNOWLEDGEMENTS

Ke-ke Shang is supported by National Natural Science Foundation of China 61803047 and Tencent Research Institute. Michael Small is supported by ARC Discovery Project DP180100718.



§ AUTHOR CONTRIBUTIONS STATEMENT

Ke-ke Shang conceived the experiments,  Yan Wang conducted the experiments, Ke-ke Shang, Michael Small, Yan Wang and Di Yin analyzed the results, Ke-ke Shang, Michael Small and Shu Li wrote the manuscript. All authors reviewed the manuscript.




§ COMPETING INTERESTS
 
The authors declare no competing interests.



§ DATA AVAILABILITY

The datasets generated and/or analysed in this study are available from the corresponding author on reasonable request.











