International Science Index


Hybrid Hierarchical Clustering Approach for Community Detection in Social Network

Abstract:Social Networks generally present a hierarchy of communities. To determine these communities and the relationship between them, detection algorithms should be applied. Most of the existing algorithms, proposed for hierarchical communities identification, are based on either agglomerative clustering or divisive clustering. In this paper, we present a hybrid hierarchical clustering approach for community detection based on both bottom-up and bottom-down clustering. Obviously, our approach provides more relevant community structure than hierarchical method which considers only divisive or agglomerative clustering to identify communities. Moreover, we performed some comparative experiments to enhance the quality of the clustering results and to show the effectiveness of our algorithm.
[1] Girvan M. and Newman M. E. J. C. Community structure in social and biological networks. CDM,2011.
[2] Liaoruo W. Tiancheng L., Jie T. and John E. Detecting Community Kernels in Large Social Networks. Phys. Rev. E 69, 066133, 2004.
[3] Newman M. E. J. and Girvan M. Finding and evaluating community structure in networks. Rev. E 69, 026113, 2004.
[4] Newman M. E. J. Fast algorithm for detecting community structure in networks. Phys. Rev. E, 69:066133, Jun 2004.
[5] Newman M. E. J. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, Volume 103, pp.8577-8582, 2006.
[6] Agarwal G. and Kempe D. Modularity-maximizing graph communities via mathe matical programming. The European Physical Journal B-Condensed Matter and Complex Systems, 66(3):409-418, 2008.
[7] Leicht, E. A. and Newman, M. structure in directed networks., 5(1):9196, January 2007.
[8] Fasmer E. E. Community Detection in Social Networks Thesis University of Bergin, April 2015.
[9] Luca D. and A. M.Detecting network communities: a new systematic and efficient algorithm. Journal of Statistical Mechanics: Theory and Experiment, 2004(10): P10012, 2004.
[10] David E. and Kleinberg J. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York, 1st edition, 2010.
[11] Toujani R. and Akaichi J. Machine Learning and Metaheuristic For sentiment anal- ysis in social networks Metaheuristic Internatianal Conference MIC’15,Morrocco, 2015.
[12] Youngdo K., Seung-Wo S., and Hawoong J. Finding communities in directed networks. Phys. Rev. E, 81:016103, Jan 2010.
[13] Reuven C. and Shlomo H. Complex Networks: structure, robustness, and function. Cambridge University Press, New York, 2010.
[14] Pang B., and Lee L., Opinion Mining and sentiment analysis. In D. W. Oardand M. Sanderson (Ed.), Foundations and Trends in Information Retrieval, 2008.
[15] Wayne Xin Z., Jing J., Jianshu W., Jing H., Ee- Peng L., Hongfei Y., and Xiaoming L. Comparing twitter and traditional media using topic models. In Advances in Information Retrieval, pages 338349.Springer, 2011.
[16] Pang, B., Lee, L., and Vaithyanathan, S. Thumbs up? Sentiment classification using machine learning techniques In Proceeding of the International conference on empirical methods in natural language.Philadelphia, USA: Association for Computational Linguistics, 2002.
[17] Kang H., Yoo S. J., and Han, D., Senti-lexicon and improved Naive Bayes algorithms for sentiment analysis of restaurant reviews Expert Systems Applications. Elsevier, 2012.
[18] Matthew M. and Sofus A. M. Discovering users topics of interest on twitter: a first look. In Proceedings of the fourth workshop on Analytics for noisy unstructured text data, pages 7380. ACM, 2010.
[19] Liu B. Sentiment Analysis and Subjectivity .In N.Indurkhya and F.J. Damerau (Ed.), Handbook of Natural Language, Second Edition. Dublin, Ireland: CRC Press, 2010.
[20] Pak A., and Paroubek P. Twitter as a corpus for sentiment analysis and opinion mining. .In Proceedings of Seventh International Conference on Language Resources and Evaluation (LREC). Valletta, Malta, 2010.
[21] David L. and Jon K. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7):1019 1031, 2007.
[22] Christos G., Fragkiskos D. M., Dimitrios M. T. and Michalis V. TCORECLUSTER: A Degeneracy Based Graph Clustering Framework. Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014.
[23] Cheng, J., Ke, Y., Chu, S., and Ozsu, M. Efficient core decomposition in massive networks. In ICDE, 5162., 2011
[24] Zhang, Y., and Parthasarathy, S. Extracting analyzing and visualizing triangle k-core motifs within networks. In ICDE, 10491060., 2012.
[25] Abou-Rjeili, A., and Karypis, G. Multilevel algorithms for partitioning power-law graphs. In IPDPS, 124 124, 2006.
[26] Girvan M. and Newman M. E. J. Proc. Natl Acad. Sci., USA 99 7821, 2002.
[27] Arenas A, Daz-Guilera A and Prez-Vicente C J 2007 Physica D 224 27 , 2007.
[28], Date of access to the site: december 2015.
[29] Leskovec, J., Lang, K. J., and Mahoney, M. Empirical comparison of algorithms for network community detection. In WWW, 631640, 2010.