Combining link and content for community detection: a discriminative approach

ABSTRACT

In this paper, we consider the problem of combining link and content analysis for community detection from networked data, such as paper citation networks and Word Wide Web. Most existing approaches combine link and content information by a generative model that generates both links and contents via a shared set of community memberships. These generative models have some shortcomings in that they failed to consider additional factors that could affect the community memberships and isolate the contents that are irrelevant to community memberships. To explicitly address these shortcomings, we propose a discriminative model for combining the link and content analysis for community detection. First, we propose a conditional model for link analysis and in the model, we introduce hidden variables to explicitly model the popularity of nodes. Second, to alleviate the impact of irrelevant content attributes, we develop a discriminative model for content analysis. These two models are unified seamlessly via the community memberships. We present efficient algorithms to solve the related optimization problems based on bound optimization and alternating projection. Extensive experiments with benchmark data sets show that the proposed framework significantly outperforms the state-of-the-art approaches for combining link and content analysis for community detection.

REFERENCES

• 1: Lada A. Adamic , Natalie Glance, The political blogosphere and the 2004 U.S. election: divided they blog, Proceedings of the 3rd international workshop on Link discovery, p.36-43, August 21-25, 2005, Chicago, Illinois [doi>10.1145/1134271.1134277]
• 2: ]]E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing. Mixed membership stochastic block models for relational data with application to protein-protein interactions. In IBS, 2006.
• 3: ]]J. Baumes, M. Goldberg, and M. Magdon-ismail. Efficient identification of overlapping communities. In IEEE ISI, 2005.
• 4: Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: David M. Blei , Andrew Y. Ng , Michael I. Jordan, Latent dirichlet allocation, The Journal of Machine Learning Research, 3, p.993-1022, 3/1/2003
• 6: ]]A. Clauset, M. E. J. Newman, and C. Moore. Finding community structure in very large networks. Phy. Rev. E, 70, 2004.
• 7: David Cohn , Huan Chang, Learning to Probabilistically Identify Authoritative Documents, Proceedings of the Seventeenth International Conference on Machine Learning, p.167-174, June 29-July 02, 2000
• 8: ]]D. Cohn and T. Hofmann. The missing link - a probabilistic model of document content and hypertext connectivity. In NIPS, 2001.
• 9: Laura Dietz , Steffen Bickel , Tobias Scheffer, Unsupervised prediction of citation influences, Proceedings of the 24th international conference on Machine learning, p.233-240, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273526]
• 10: ]]E. Erosheva, S. Fienberg, and J. Lafferty. Mixed membership models of scientific publications. PNAS, 101, 2004.
• 11: Lisa Getoor , Nir Friedman , Daphne Koller , Benjamin Taskar, Learning probabilistic models of link structure, The Journal of Machine Learning Research, 3, 3/1/2003
• 12: Steve Gregory, An Algorithm to Find Overlapping Community Structure in Networks, Proceedings of the 11th European conference on Principles and Practice of Knowledge Discovery in Databases, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74976-9_12]
• 13: ]]A. Gruber, M. Rosen-Zvi, and Y. Weiss. Latent topic models for hypertext. In UAI, 2008.
• 14: ]]J. M. Hofman and C. H. Wiggins. A Bayesian approach to network modularity. Phy. Rev. Letters, 100, 2008.
• 15: Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
• 16: Tony Jebara , Risi Kondor , Andrew Howard, Probability Product Kernels, The Journal of Machine Learning Research, 5, p.819-844, 12/1/2004
• 17: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 18: ]]S. Lacoste-Julien, F. Sha, and M. I. Jordan. DiscLDA: Discriminative learning for dimensionality reduction and classification. In NIPS, 2008.
• 19: ]]A. McCallum and K. Nigam. A comparisoin of event models for naive bayes text classification. AAAI Workshop, 1998.
• 20: Andrew Kachites McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, Automating the Construction of Internet Portals with Machine Learning, Information Retrieval, v.3 n.2, p.127-163, July 2000 [doi>10.1023/A:1009953814988]
• 21: Ramesh M. Nallapati , Amr Ahmed , Eric P. Xing , William W. Cohen, Joint latent topic models for text and citations, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401957]
• 22: ]]M. E. J. Newman. Fast algorithm for detecting community structure in networks. Phy. Rev. E, 69, 2004.
• 23: ]]M. E. J. Newman. Modularity and community structure in networks. PNAS, 103, 2006.
• 24: ]]M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Phy. Rev. E, 69, 2003.
• 25: ]]M. E. J. E. Newman and E. A. A. Leicht. Mixture models and exploratory analysis in networks. PNAS, 104, 2007.
• 26: ]]A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, 2001.
• 27: ]]K. Nowicki and T. A. B. Snijders. Estimation and prediction for stochastic blockstructures. J. of ASA, 96, 2001.
• 28: ]]L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. In Technical report, Stanford Digital Library Technologies Project, Stanford University, Stanford, CA, USA, 1998.
• 29: ]]G. Palla, I. Derenyi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435, 2005.
• 30: ]]W. Ren, G. Yan, X. Liao, and L. Xiao. Simple probabilistic algorithm for detecting community structure. Phy. Rev. E.
• 31: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 32: ]]X. Wang, N. Mohanty, and A. McCallum. Group and topic discovery from relations and their attributes. In NIPS, 2005.
• 33: ]]K. Yu, S. Yu, and V. Tresp. Soft clustering on graphs. In NIPS, 2005.
• 34: ]]S. Yu, B. D. Moor, and Y. Moreau. Clustering by heterogeneous data fusion: framework and applications. NIPS workshop, 2009.
• 35: Shenghuo Zhu , Kai Yu , Yun Chi , Yihong Gong, Combining content and link for classification using matrix factorization, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277825]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms, Experimentation, Measurement, Theory

Keywords:
discriminative model, em algorithm, link analysis, two-stage optimization