Grouping of Nodes in Social Networks Based on Multiphase Approach

Parimala    M.    Boobalan

doi:10.2174/2213275911666181022111924

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.

« Previous Next »

Graphical Abstract

[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 & Permissions Print Cite

Article Metrics

14

1

DOI https://dx.doi.org/10.2174/2213275911666181022111924	Print ISSN 2213-2759
Publisher Name Bentham Science Publisher	Online ISSN 1874-4796

Recent Patents on Computer Science

Grouping of Nodes in Social Networks Based on Multiphase Approach

Abstract Play Pause

Graphical Abstract

Related Journals

Related Books

Abstract