Online Social Network (OSN) users generate massive amounts of information by their online interactions, by publishing profiles and posting content. Detection and analysis of the dense sub-structures of networks, called communities could facilitate a comprehensive understanding of OSNs. This presents the challenge of formulating appropriate means to evaluate and validate each detected community. Most researchers have tackled this issue by comparing results obtained from community detection algorithms with information on available social grouping as a ground-truth. However, social grouping does not guarantee formation or existence of an experienced sense of community, based on the community-oriented behavior patterns of its users. This study presents a new scoring function that targets the behavior of nodes in order to validate detected communities. Indeed, we employ this function as a Cluster Validity Index (CVI) for evaluating detected communities. Then, performance of the proposed CVI was compared with other known functions by ranking in terms of several goodness metrics, on a variety of homogeneous networks. This study also presents an enhanced version of the CVI to evaluate communities efficiently in heterogeneous networks. A number of experiments have been provided to demonstrate the effectiveness and reliability of the proposed CVI for heterogeneous networks.
AdamicL.A. and GlanceN., The political blogosphere and the 2004 US Election, in: Proceedings of the WWW-2005 Workshop on the Web Logging Ecosystem (2005).
2.
AmiriB., HossainL., CrawfordJ.W. and WigandR.T., Multi-objective enhanced firefly algorithm for community detection in complex networks, Knowledge-based Systems46 (2013), 1-11.
3.
BarbieriN., BonchiF. and MancoG., Cascade-based Community Detection, WSDM'13, Rome, Italy, 4-8 Feb 2012.
4.
BhatS.Y. and AbulaisM., OCMiner: A density-based overlapping community detection method for social networks, Intelligent Data Analysis19 (2015), 917-947.
5.
Byung-WonO., Effective email network visualization techniques by means of user behaviors, Intelligent Data Analysis17 (2013), 1041-1056.
6.
BlanchardA.L. and MarkusM.L., Sense of virtual community - maintaining the experience of belonging, Proceedings of the 35th Hawaii International Conference on System Sciences (2002).
7.
ChangJ. and BleiD.M., Relational topic models for document Networks, Proceedings of the 12th international conference on artificial intelligence and statistics (AISTATS), Clearwater Beach, Florida, USA, 2009.
8.
DangT.A. and ViennetE., Community detection based on structural and attribute similarities, The Sixth International Conference on Digital Society, ICDS, 2012.
9.
EasleyD. and KleinbergJ., Networks, crowds, and markets: reasoning about a highly connected world, Cambridge University Press, 2010.
10.
FlakeG.W., LawrenceS. and GilasC.L., Efficient identification of web communities, Boston, MA, USA, KDD, 2000.
11.
FurtunatoS., Community detection in graphs, Physics Reports486 (2010), 75-174.
12.
GopalanP.K., GerrishS., FreedmanM., BleiD.M. and MimnoD.M., Scalable inference of overlapping communities, Advances in Neural Information Processing Systems, NIPS 25 (2012).
13.
HanischD., ZienA., ZimmerR. and LengauerT., Co-clustering of biological networks and gene expression data, Bioinformatics18(1) (2002).
14.
HarenbergS., BelloG., GjeltemaL., RanshousS., HarlalkaJ., SeayR., PadmanabhanK. and SamatovaN., Community detection in large-scale networks A survey and empirical evaluation, WIREs Computational Statistics6(6) (2014), 426-439. DOI: 10.1002/wics.1319.
15.
Karimi-MajdA.-M., FathianM. and AmiriB., A hybrid artificial immune network for detecting communities in complex networks, Computing97 (2015), 483-507. DOI: 10.1007/s00607-014-0433-6.
16.
LancichinettiA., FortunatoS. and RadicchiF., Benchmark graphs for testing community detection algorithms, Physical ReviewE78 (2008), 046110.
17.
LiZ., ZhangS., WangR.-S., ZhangX.-S. and ChenL., Quantitative function for community detection, Physical ReviewE77 (2008), 036109.
18.
LiH.L. and NgV.T.Y., Discovering associations between news and contents in social network sites with the D-Miner service frame work, Journal of Network and Computer Applications36 (2013), 1651-1659.
19.
LiuY., Niculescu-MizilA. and GrycW., Topic-link lda joint models of topic and author community, Proceedings of the 26th International Conference on Machine Learning, Montreal, Canada, (2009).
20.
MalliarosF.D. and VazirgiannisM., Clustering and community detection in directed networks A survey, Physics Reports533 (2013), 95-142.
21.
NewmanM.E.J., Modularity and community structure in networks, PNAS103(23) (2004), 8577-8582.
22.
PallaG., DerényiI., FarkasI. and VicsekT., Uncovering the overlapping community structure of complex, Nature435 (2005). DOI: 10.1038/nature03607.
23.
PoolS., BonchiF. and van LeeuwenM., Description-driven community detection, ACM Transactions on Intelligent Systems and Technology (2013).
24.
RadicchiF., CastellanoC., CecconiF., LoretoV. and ParisiD., Defining and identifying communities in networks, PNAS101(9) (2004), DOI: 10.1073/pnas.0400054101.
25.
RaghavanU.N., AlbertR. and KumaraS., Near linear time algorithm to detect community structures in large-scale networks, Physical Review E76 (2007), 036106. DOI: 10.1103/PhysRevE.6.036106.
26.
RuanY., FuhryD. and ParthasarathyS., Efficient community detection in large networks using content and links, WWW 2013, Rio de Janeiro, Brazil, (13-17 May 2013).
27.
SerrourB., ArenasA. and GómezS., Detecting communities of triangles in complex networks using spectral optimization, Computer Communications34 (2011), 629-634. DOI: 10.1016/j.comcom.2010.05.006.
28.
ShangR., BaiJ., JiaoL. and JinC., Community detection based on modularity and an improved genetic algorithm, Physica, A392 (2013), 1215-1231.
29.
ShiJ. and MalikJ., Normalized cuts and image segmentation, IEEE Transactions On Pattern Analysis and Machine Intelligence22(8) (2000).
30.
SunP.G., GaoL. and YangY., Maximizing modularity intensity for community partition and evolution, Information Sciences236 (2013), 83-92.
31.
TangL., LiuH., ZhangJ. and NazariZ., Community evolution in dynamic multi-mode networks, KDD'08, Las Vegas, Nevada, USA, (Aug 2008) 24-27.
32.
TangL., WangX. and LiuH., Community detection via heterogeneous interaction analysis, Data Min Knowl Disc25 (2012), 1-33, DOI: 10.1007/s10618-011-0231-0.
33.
TangL. and LiuH., Community detection and mining in social media, Morgan and Claypool, 2010. DOI: 10.2200/S00298ED1V01Y201009DMK003.
34.
WattD.J. and StrogatzS.H., Collective dynamics of small-world networks, Nature393 (1998).
35.
WeiY.-C. and ChengC.-K., Towards efficient hierarchical designs by ratio cut partitioning, IEEE, 1989.
36.
XuG., BennettL., PapageorgiouL.G. and TsokaS., Module detection in complex networks using integer optimization, Algorithms for Molecular Biology5(36) (2010).
37.
YangJ. and LeskovecJ., Defining and evaluating network communities based on ground-truth, Konwl Inf Syst (2013). DOI: 10.1007/s10115-013-0693-z.
38.
YangJ., McAuleyJ. and LeskovecJ., Community detection in networks with node attributes, in: Proceedings of ICDM (2013), 1151-1156.
39.
YangJ. and LeskovecJ., Community-affiliation graph model for overlapping network community detection, IEEE 12th International Conference on Data Mining (2012).
40.
ZanghiH., VolantS. and AmbroiseC., Clustering based on random graph model embedding vertex features, Pattern Recognition Letters31 (2010), 830-836.
41.
ZhangX.-S., LiZ., WangR.-S. and WangY., A combinatorial model and algorithm for globally searching community structure in complex networks, J Comb Optim23 (2012), 425-442. DOI: 10.1007/s10878-010-9356-0.
42.
ZhouY., ChengH. and YuJ.X., Graph Clustering Based on Structural/Attribute Similarities, VLDB `09, Lyon, France, (Aug 24-28, 2009).
