Grouping of Nodes in Social Networks Based on Multiphase Approach

Author(s): Parimala M. Boobalan*.

Journal Name: Recent Patents on Computer Science

Volume 12 , Issue 1 , 2019

Become EABM
Become Reviewer

Graphical Abstract:


Abstract:

Background: Recent advances in the field of information and social network has led to the problem of community detection that has got much attention among the researchers.

Objective: This paper focus on community discovery, a fundamental task in network analysis by balancing both attribute and structural similarity. The attribute similarity is evaluated using the Jaccard coefficient and Structural similarity is achieved through modularity.

Methods: The proposed algorithm is designed for identifying communities in social networks by fusing attribute and structural similarity. The algorithm retains the node which has high influence on the other nodes within the neighbourhood and subsequently groups the objects based on the similarity of the information among the nodes. The extensive analysis is performed on real world datasets like Facebook, DBLP, Twitter and Flickr with different sizes that demonstrates the effectiveness and efficiency of the proposed algorithm over the other algorithms.

Results: The results depicts that the generated clusters have a good balance between the structural and attribute with high intracluster similarity and less intracluster similarity. The algorithm helps to achieve faster runtime for moderately-sized datasets and better runtime for large datasets with superior clustering quality.

Keywords: Social networks, community detection, attribute similarity, structural similarity, algorithm, clusters.

[1]
M. Girvan, and M.E. Newman, "Community structure in social and biological networks", Proc. Natl. Acad. Sci., vol. 99, pp. 7821-7826, 2002.
[2]
"J. Yang and J. Leskovec, “Overlapping community detection at scale: A nonnegative matrix factorization approach”, In", Proceedings of the sixth ACM International Conference on Web Search and Data Mining,. pp. 587-596, 2013.
[3]
"M. Coscia, G. Rossetti, F. Giannotti and D. Pedreschi, “Demon: A local-first discovery method for overlapping communities”, In", Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,. pp. 615-623, 2012
[4]
H. Wang, Managing and mining graph data., Springer: New York, 2010.
[5]
S. Fortunato, "Community detection in graphs", Phys. Rep., vol. 486, pp. 75-174, 2010.
[6]
"M. Parimala and D. Lopez, “A Novel Graph Clustering Algorithm Based on Structural Attribute Neighborhood Similarity (SANS)”, In", Proceedings of 3rd International Conference on Advanced Computing, Networking and Informatics,. pp. 467-474, 2016.
[7]
"J. Leskovec, K. J. Lang, A. Dasgupta and M. W. Mahoney, “Statistical properties of community structure in large social and information networks”, In", Proceedings of the 17th International Conference on World Wide Web,. pp. 695-704, 2008.
[8]
M.E. Newman, and M. Girvan, "Finding and evaluating community structure in networks", Phys. Rev. E., vol. 69, p. 026113, 2004.
[9]
J. Shi, and J. Malik, "Normalized cuts and image segmentation", IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, pp. 888-905, 2000.
[10]
"X. Xu, N. Yuruk, Z. Feng and T. A. Schweiger, “Scan: a structural clustering algorithm for networks”, In", Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,. pp. 824-833, 2007.
[11]
Y.Y. Ahn, J.P. Bagrow, and S. Lehmann, "Link communities reveal multiscale complexity in networks", Nature, vol. 466, pp. 761-764, 2010.
[12]
"Y. Tian, R. A. Hankins and J. M. Patel, “Efficient aggregation for graph summarization”, In", Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data,. pp. 567-580, 2008.
[13]
"C. Y. Tsai and C. C. Chiu, “Developing a feature weight selfadjustment mechanism for a K-means clustering algorithm”,", Comput. Stat. Data Anal.,. Vol. 52, Vol. 4658-4672, 2008.
[14]
V.D. Blondel, A. Gajardo, M. Heymans, P. Senellart, and P.V. Dooren, "A measure of similarity between graph vertices: Applications to synonym extraction and web searching", SIAM Rev., vol. 46, pp. 647-666, 2004.
[15]
"R. Balasubramanyan and W. W. Cohen, “Block-LDA: Jointly modeling entity-annotated text and entity-entity links”,", In SDM. Vol. 11, pp. 450-461, 2011.
[16]
"J. McAuley and J. Leskovec, “Learning to discover social circles in ego networks”, In", Proceedings of the 25th International Conference on Neural Information Processing Systems,. pp. 539-547, 2012.
[17]
"L. Akoglu, H. Tong, B. Meder and C. Faloutsos, “PICS: Parameterfree Identification of Cohesive Subgroups in Large Attributed Graphs”, In", Proceedings of the 2012 SIAM International Conference on Data Mining,. pp. 439-450, 2012.
[18]
"F. Moser, R. Colak, A. Rafiey and M. Ester, “Mining Cohesive Patterns from Graphs with Feature Vectors”,", In SDM,. Vol. 9, pp. 593-604, 2009.
[19]
"Y. Liu, A. Niculescu-Mizil and W. Gryc, “Topic-link LDA: Joint models of topic and author community”, In", Proceedings of the 26th Annual International Conference on Machine Learning,. pp. 665- 672, 2009
[20]
"Y. Sun, C. C. Aggarwal and J. Han, “Relation strength-aware clustering of heterogeneous information networks with incomplete attributes”,", Proc. VLDB Endowment. Vol. 5, pp. 394-405, 2012.
[21]
"Z. Xu, Y. Ke, Y. Wang, H. Cheng and J. Cheng, “A model-based approach to attributed graph clustering”, In", Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data,. pp. 505-516, 2012
[22]
"J. Yang and J. Leskovec, “Structure and overlaps of communities in networks”, arXiv preprint arXiv: 1205.6228, 2012",
[23]
"Y. Zhou, H. Cheng and J. X. Yu, “Graph clustering based on structural/ attribute similarities”,", Proc. VLDB Endowment,. Vol. 2, pp. 718-729, 2009
[24]
"G. Jeh and J. Widom, “SimRank: A measure of structural-context similarity”,", In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,. pp. 538-543, 2002.
[25]
D. Gleich and C. Seshadhri, “Neighborhoods are good communities”, arXiv preprint arXiv: 1112.0031, 2011.
[26]
"M. Ester, H. P. Kriegel, J. Sander and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise”,", In Kdd,. Vol. 96, pp. 226-231, 1996.
[27]
R.D. Luce, and A.D. Perry, "A method of matrix analysis of group structure", Psychometrika, vol. 14, pp. 95-116, 1996.
[28]
T. Opsahl, and P. Panzarasa, "Clustering in weighted networks", Soc. Netw., vol. 31, pp. 155-163, 2009.
[29]
"J. Yang and J. Leskovec, “Defining and Evaluating Network Communities based on Ground-truth”,", IEEE 12th International Conference on Data Mining,. 2012.
[30]
"R. Yiye, D. Fuhry and S. Parthasarathy, “Efficient community detection in large networks using content and links”,", Proceedings of the 22nd International Conference on World Wide Web,. pp. 1089-1098, 2013.
[31]
J. Leskovec, and J.J. Mcauley, "Learning to discover social circles in ego networks", Adv. Neural Inf. Process. Syst., pp. 539-547, 2012.
[32]
H. Cheng, Y. Zhou, and J.X. Yu, "Clustering large attributed graphs: A balance between structural and attribute similarities", Trans. Knowledge Discovery Data (TKDD), vol. 5, p. 12, 2011.


Rights & PermissionsPrintExport Cite as

Article Details

VOLUME: 12
ISSUE: 1
Year: 2019
Page: [25 - 33]
Pages: 9
DOI: 10.2174/2213275911666181022111924
Price: $58

Article Metrics

PDF: 11
HTML: 1