Detecting Topic-oriented Overlapping Community Using Hybrid Hypergraph Model

Authors

  • Gui-lan Shen
  • Xiao-ping Yang Information School, Renmin University Beijng, China
  • Jie Sun Business School, Beijing Union University Beijing,China

Keywords:

information network, overlapping community detection, topic-oriented, hybrid hypergraph model

Abstract

A large number of emerging information networks brings new challenges to the overlapping community detection. The meaningful community should be topicoriented. However, the topology-based methods only reflect the strength of connection, but ignore the consistency of the topics. This paper explores a topic-oriented overlapping community detection method for information work. The method utilizes a hybrid hypergraph model to combine the node content and structure information naturally. Two connections for hyperedge pair, including real connection and virtual connection are defined. A novel hyperedge pair similarity measure is proposed by combining linearly extended common neighbors metric for real connection and incremental fitness for virtual connection. Extensive experiments on two real-world datasets validate our proposed method outperforms other baseline algorithms.

References

Cobanoglu B, Zengin A, Ekiz H, et al (2014); Implementation of DEVS Based Distributed Network Simulator for Large-Scale Networks [J]. International Journal of Simulation Modelling IJSIMM), 13(2): 147-158. http://dx.doi.org/10.2507/IJSIMM13(2)2.257

Ding Y. (2011), Community detection: topological vs. topical, Journal of Informetrics, DOI: 10.1016/j.joi.2011.02.006, 5(4): 498-514. http://dx.doi.org/10.1016/j.joi.2011.02.006

Lancichinetti, Andrea, Santo Fortunato, and János Kertész (2009);

Detecting the overlapping and hierarchical community structure in complex networks, New Journal of Physics, 11(3): 033015. http://dx.doi.org/10.1088/1367-2630/11/3/033015

Xie J., Kelley S., Szymanski B. K. (2013), Overlapping community detection in networks: The state-of-the-art and comparative study, ACM Computing Surveys (CSUR), 45(4): 43- 79. http://dx.doi.org/10.1145/2501654.2501657

Evans T. S., Lambiotte R. (2009), Line graphs, link partitions, and overlapping communities, Physical Review E, DOI:http://dx.doi.org/10.1103/PhysRevE.80.016105, 8(1): 92-105. http://dx.doi.org/10.1103/PhysRevE.80.016105

Ahn Y. Y., Bagrow J. P., Lehmann S. (2010), Link communities reveal multiscale complexity in networks, Nature, doi:10.1038/nature09182, 466: 761-764. http://dx.doi.org/10.1038/nature09182

He, C., Ma, H., Kang, S., Cui, R. (2014), An Overlapping Community Detection Algorithm Based on Link Clustering in Complex Networks, In Military Communications Conference (MILCOM) IEEE, 865-870.

Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005), Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435: 814-818. http://dx.doi.org/10.1038/nature03607

Farkas, I., Ãbel, D., Palla, G., & Vicsek, T. (2007), Weighted network modules, New Journal of Physics, 9: 80-198. http://dx.doi.org/10.1088/1367-2630/9/6/180

Girvan M., Newman M. E. J. (2002), Community structure in social and biological networks, Proc. of the National Academy of Sciences, 99: 7821-7826. http://dx.doi.org/10.1073/pnas.122653799

Gregory S. (2007), An algorithm to find overlapping community structure in networks, Knowledge discovery in databases: PKDD 2007, Springer Berlin Heidelberg, 91-102.

Gregory S. (2008), A fast algorithm to find overlapping communities in networks, Machine learning and knowledge discovery in databases, Springer Berlin Heidelberg, 408-423.

T. Yang, R. Jin, Y. Chi, S. Zhu (2009), Combining link and content for community detection: a discriminative approach, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, Paris, 927-936. http://dx.doi.org/10.1145/1557019.1557120

Hric D., Darst R. K., Fortunato S. (2014), Community detection in networks: structural clusters versus ground truth, arXiv preprint arXiv:1406.0146.

Hofmann, David Cohn Thomas (2001), The missing link-a probabilistic model of document content and hypertext connectivity, Proceedings of the 2000 Conference on Advances in Neural Information Processing Systems, Vancouver, 430-436.

D. Zhou, E. Manavoglu, J. Li, C. Giles, and H. Zha (2006), Probabilistic models for discovering e-communities, In Proceedings of the 15th international conference on World Wide Web, Banff, 173-182. http://dx.doi.org/10.1145/1135777.1135807

Yang, B., Di, J., Liu, J., Liu, D. (2013), Hierarchical community detection with applications to real-world network analysis, Data & Knowledge Engineering, 83: 20-38. http://dx.doi.org/10.1016/j.datak.2012.09.002

M. Ester, R. Ge, B. Gao, Z. Hu, and B. Ben-Moshe (2006), Joint cluster analysis of attribute data and relationship data: the connected k-center problem, Proceedings of the 2006 SIAM International Conference on Data Mining, Maryland, USA, 25-46. http://dx.doi.org/10.1137/1.9781611972764.22

Günnemann S, B. Boden, and T. Seidl (2011), Db-csc: a density-based approach forsubspace clustering in graphs with feature vectors, Machine Learning and Knowledge Discovery in Databases, Springer Berlin Heidelberg, 565-580.

Berge, Claude (1989), Hypergraphs: Combinatorics of Finite Sets, North Holland.

Zhou X. et al.(2014); Information-value-based feature selection algorithm for anomaly detection over data streams [J]. TehniÄki vjesnik, 21: 223-232.

Zhao, Z., Feng, S., Wang, Q., Huang, J. Z., Williams, G. J., Fan, J. (2012), Topic oriented community detection through social objects and link analysis in social networks, Knowledge- Based Systems, 26: 164-173. http://dx.doi.org/10.1016/j.knosys.2011.07.017

Darst R. K., Nussinov Z., Fortunato S. (2014), Improving the performance of algorithms to find communities in networks, Physical Review E, 89(3): 42-58. http://dx.doi.org/10.1103/PhysRevE.89.032809

McAuley J., Leskovec J. (2014), Discovering social circles in ego networks, ACM Transactions on Knowledge Discovery from Data (TKDD), 8(1): 10-16. http://dx.doi.org/10.1145/2556612

Lorrain F., White H. C. (1971), Structural equivalence of individuals in social networks, The Journal of mathematical sociology,1: 49-80. http://dx.doi.org/10.1080/0022250X.1971.9989788

Rayid Ghani (2014), CMU World Wide Knowledge Base (WebKB) project, Jan, 2001.[Online]. Available: http://www.cs.cmu.edu/∼webkb. [Accessed: April 9, 2014

Published

2016-07-03

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.