Expanding network communities from representative examples

ABSTRACT

We present an approach to leverage a small subset of a coherent community within a social network into a much larger, more representative sample. Our problem becomes identifying a small conductance subgraph containing many (but not necessarily all) members of the given seed set. Starting with an initial seed set representing a sample of a community, we seek to discover as much of the full community as possible.

We present a general method for network community expansion, demonstrating that our methods work well in expanding communities in real world networks starting from small given seed groups (20 to 400 members). Our approach is marked by incremental expansion from the seeds with retrospective analysis to determine the ultimate boundaries of our community. We demonstrate how to increase the robustness of the general approach through bootstrapping multiple random partitions of the input set into seed and evaluation groups.

We go beyond statistical comparisons against gold standards to careful subjective evaluations of our expanded communities. This process explains the causes of most disagreement between our expanded communities and our gold-standards—arguing that our expansion methods provide more reliable communities than can be extracted from reference sources/gazetteers such as Wikipedia.

REFERENCES

• 1: Reid Andersen , Kevin J. Lang, Communities from seed sets, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135814]
• 2: Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150412]
• 3: Albert-Laszlo Barabasi, Linked, Perseus Publishing, 2002
• 4: Mikhail Bautin , Steven Skiena, Concordance-Based Entity-Oriented Search, Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, p.586-592, November 02-05, 2007 [doi>10.1109/WI.2007.37]
• 5: Cami, A., Balakrishnan, H., Deo, N., and Dutton, R. 2006. On the complexity of finding optimal global alliances. J. Comb. Math. Comb. Comput. 58, 23--31.
• 6: Cirasella, J. 2007. Google sets, google suggest, and google search history: Three more tools for the reference librarian's bag of tricks. Refer. Libr. 48.1.
• 7: Clauset, A., Moore, C., and Newman, M. E. 2008. Hierarchical structure and the prediction of missing links in networks. Nature 453, 7191, 98--101.
• 8: Favaron, O., Fricke, G., Goddard, W., Hedetniemi, S. M., Hedetniemi, S. T., Kristiansen, P., Laskar, R. C., and Skaggs, D. 2002. Offensive alliance graphs. Discussiones Mathematicae—Graph Theory.
• 9: Fernau, H. and Raible, D. 2007. Alliances in graphs: a complexity-theoretic study. In Proceedings of the Software Seminar, vol. 2, J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, F. Plasil, and M. Bielikov, Eds. Institute of Computer Science AS CR, Prague, 61--70.
• 10: Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347121]
• 11: Flake, G. W., Tarjan, R. E., and Tsioutsiouliklis, K. 2004. Graph clustering and minimum cut trees. J. Internet Math. 1, 385--408.
• 12: Ghahramani, Z. and Heller, K. A. 2005. Bayesian sets. In Proceedings of NIPS.
• 13: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 14: Girvan, M. and Newman, M. E. J. 2002. Community structure in social and biological networks. Proc. Nati. Acad. Sci. 99, 7821--7826.
• 15: Godbole, N., Srinivasaiah, M., and Skiena, S. 2007. Large-scale sentiment analysis for news and blogs. In Proceedings of the International Conference on Weblogs and Social Media (ICWSM'07).
• 16: John Hopcroft , Omar Khan , Brian Kulis , Bart Selman, Natural communities in large linked networks, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956816]
• 17: Hopcroft, J., Khan, O., Kulis, B., and Selman, B. 2004. Tracking evolving communities in large linked networks. Proc. Natl. Acad. Sci. 101 Suppl 1, 5249--5253.
• 18: Jamieson, L. H, Hedetniemi, S. T., and McRa, A. A. 2002. The algorithmic complexity of alliances in graphs. J. Combin. Math. Combin. Comput.
• 19: Kernighan, B. W. and Lin, S. 1970. An efficient heuristic procedure for partitioning graphs. The Bell Syst. Tech. J. 49, 1, 291--307.
• 20: Kil, J., Lloyd, L., and Skiena, S. 2005. Question answering with Lydia. In Proceedings of 14th Text Retrieval Conference (TREC'05).
• 21: 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]
• 22: Kossinets, G. and Watts, D. J. 2005. Empirical analysis of an evolving social network. Science 311, 88--90.
• 23: Jure Leskovec , Kevin J. Lang , Anirban Dasgupta , Michael W. Mahoney, Statistical properties of community structure in large social and information networks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367591]
• 24: Lloyd, L., Kaulgud, P., and Skiena, S. 2006. Newspapers vs. blogs: Who gets the scoop? In Proceedings of the Conference on Computational Approaches to Analyzing Weblogs (AAAI-CAAW'06). AAAI Press, 117--124.
• 25: Lloyd, L., Kechagias, D., and Skiena, S. 2005. Lydia: A system for large-scale news analysis. In Proceedings of the Conference on String Processing and Information Retrieval (SPIRE'05). Lecture Notes in Computer Science, Vol. 3772. 161--166.
• 26: Lloyd, L., Mehler, A., and Skiena, S. 2006. Identifying co-referential names across large corpora. In Proceedings of the Conference on Combinatorial Pattern Matching (CPM'06).
• 27: Andrew Mehler , Yunfan Bao , Xin Li , Yue Wang , Steven Skiena, Spatial Analysis of News Sources, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.765-772, September 2006 [doi>10.1109/TVCG.2006.179]
• 28: Newman, M. E. J. 2004. Detecting community structure in networks. Europ. Phys. J. B 38, 321--330.
• 29: Newman, M. E. J. and Girvan, M. 2004. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113.
• 30: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
• 31: Purnamrita Sarkar , Andrew W. Moore, Dynamic social network analysis using latent space models, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.31-40, December 2005 [doi>10.1145/1117454.1117459]
• 32: Luis Sarmento , Valentin Jijkuon , Maarten de Rijke , Eugenio Oliveira, "More like these": growing entity classes from seeds, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321585]
• 33: Scott, J. 2000. Social Network Analysis: A Handbook. Sage Publications.
• 34: Shafique, K. H. 2001. Partitioning a graph in alliances and its application to data clustering. Ph.D. thesis, School of Computer Science, University of Central Florida Orlando.
• 35: Michael Thelen , Ellen Riloff, A bootstrapping method for learning semantic lexicons using extraction pattern contexts, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.214-221, July 06, 2002 [doi>10.3115/1118693.1118721]
• 36: Joshua R. Tyler , Dennis M. Wilkinson , Bernardo A. Huberman, Email as spectroscopy: automated discovery of community structure within organizations, Communities and technologies, Kluwer, B.V., Deventer, The Netherlands, 2003
• 37: Ward, C., Bautin, M., and Skiena, S. 2009. Identifying differences in news coverage between cultural/ethnic groups.
• 38: Wu, F. and Huberman, B. A. 2004. Finding communities in linear time: a physics approach. Eur. Phys. J. B 38, 331--338.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms

Keywords:
Discrete mathematics, artificial intelligence, community discovery, graph theory, news analysis, social networks