POLYPHONET: an advanced social network extraction system from the web

ABSTRACT

Social networks play important roles in the Semantic Web: knowledge management, information retrieval, ubiquitous computing, and so on. We propose a social network extraction system called POLYPHONET, which employs several advanced techniques to extract relations of persons, detect groups of persons, and obtain keywords for a person. Search engines, especially Google, are used to measure co-occurrence of information and obtain Web documents.Several studies have used search engines to extract social networks from the Web, but our research advances the following points: First, we reduce the related methods into simple pseudocodes using Google so that we can build up integrated systems. Second, we develop several new algorithms for social networking mining such as those to classify relations into categories, to make extraction scalable, and to obtain and utilize person-to-word relations. Third, every module is implemented in POLYPHONET, which has been used at four academic conferences, each with more than 500 participants. We overview that system. Finally, a novel architecture called Super Social Network Mining is proposed; it utilizes simple modules using Google and is characterized by scalability and Relate-Identify processes: Identification of each entity and extraction of relations are repeated to obtain a more precise social network.

REFERENCES

• 1: L. A. Adamic and E. Adar. Friends and neighbors on the web. Social Networks, 25(3):211--230, 2003.
• 2: Aris Anagnostopoulos , Andrei Z. Broder , David Carmel, Sampling search-engine results, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060784]
• 3: Ron Bekkerman , Andrew McCallum, Disambiguating Web appearances of people in a social network, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060813]
• 4: D. Bollegara, Y. Matsuo, and M. Ishizuka. Extracting key phrases to disambiguate personal names on the web. In Proc. CICLing 2006, 2006.
• 5: R. S. Burt. Structural Holes: The Social Structure of Competition. Harvard University Press, Cambridge, MA, 1992.
• 6: Michael J. Cafarella , Oren Etzioni, A search engine for natural language applications, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060811]
• 7: Tara Calishain , Rael Dornfest, Google Hacks: 100 Industrial-Strength Tips and Tools, O'Reilly & Associates, Inc., Sebastopol, CA, 2003
• 8: Soumen Chakrabarti, Mining the Web: Discovering Knowledge from HyperText Data, Science & Technology Books, 2002
• 9: Philipp Cimiano , Siegfried Handschuh , Steffen Staab, Towards the self-annotating web, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988735]
• 10: Philipp Cimiano , Günter Ladwig , Steffen Staab, Gimme' the context: context-driven automatic semantic annotation with C-PANKOW, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060796]
• 11: Philipp Cimiano , Steffen Staab, Learning by googling, ACM SIGKDD Explorations Newsletter, v.6 n.2, p.24-33, December 2004 [doi>10.1145/1046456.1046460]
• 12: A. Culotta, R. Bekkerman, and A. McCallum. Extracting social networks and contact information from email and the web. In CEAS-1, 2004.
• 13: I. Davis and E. V. Jr. RELATIONSHIP: A vocabulary for describing relationships between people. http://vocab.org/relationship/.
• 14: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014068]
• 15: Jeremy Goecks , Elizabeth D. Mynatt, Leveraging social networks for information sharing, Proceedings of the 2004 ACM conference on Computer supported cooperative work, November 06-10, 2004, Chicago, Illinois, USA [doi>10.1145/1031607.1031660]
• 16: J. Golbeck and J. Hendler. Accuracy of metrics for inferring trust and reputation in semantic web-based social networks. In Proc. EKAW 2004, 2004.
• 17: R. Guha and A. Garg. Disambiguating entities in web search. TAP project, http://tap.stanford.edu/PeopleSearch.pdf.
• 18: M. Hamasaki, H. Takeda, I. Ohmukai, and R. Ichise. Scheduling support system for academic conferences based on interpersonal networks. In Proc. ACM Hypertext 2004, 2004.
• 19: Masanori Harada , Shin-ya Sato , Kazuhiro Kazama, Finding authoritative people from the web, Proceedings of the 4th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2004, Tuscon, AZ, USA [doi>10.1145/996350.996420]
• 20: Y. Jin, Y. Matsuo, and M. Ishizuka. Extracting inter-business relationship from world wide web. In Workshop Notes, Web Community Structure and Network Analysis Workshop, 2005.
• 21: H. Kautz, B. Selman, and M. Shah. The hidden Web. AI magazine, 18(2):27--35, 1997.
• 22: P. Knees, E. Pampalk, and G. Widmer. Artist classification with web-based data. In 5th International Conf. on Music Information Retrieval(ISMIR), 2004.
• 23: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, The Web and Social Networks, Computer, v.35 n.11, p.32-36, November 2002 [doi>10.1109/MC.2002.1046971 ]
• 24: J. Leskovec, L. A. Adamic, and B. A. Huberman. The dynamics of viral marketing, 2005. http://www.hpl.hp.com/research/idl/papers/viral/viral.pdf.
• 25: Xin Li , Paul Morie , Dan Roth, Semantic integration in text: from ambiguous names to identifiable entities, AI Magazine, v.26 n.1, p.45-58, March 2005
• 26: L. Lloyd, V. Bhagwan, D. Gruhl, and A. Tomkins. Disambiguation of references to individuals. Technical Report RJ10364(A0410-011), IBM Research, 2005.
• 27: B. Malin. Unsupervised name disambiguation via social network similarity. In Workshop Notes on Link Analysis, Counterterrorism, and Security, 2005.
• 28: G. S. Mann and D. Yarowsky. Unsupervised personal name disambiguation. In Proc. CoNLL, 2003.
• 29: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 30: Y. Matsuo, H. Tomobe, K. Hasida, and M. Ishizuka. Finding social network for trust calculation. In Proc. 16th European Conference on Artificial Intelligence (ECAI2004), pp. 510--514, 2004.
• 31: Y. Matsuo, H. Tomobe, K. Hasida, and M. Ishizuka. Social network extraction from the web information. Journal of the Japanese Society for Artificial Intelligence, 20(1E):46--56, 2005. in Japanese.
• 32: P. Mika. Flink: Semantic web technology for the extraction and analysis of social networks. Journal of Web Semantics, 3(2), 2005.
• 33: P. Mika. Ontologies are us: A unified model of social networks and semantics. In Proc. ISWC2005, 2005.
• 34: Takeru Miki , Saeko Nomura , Toru Ishida, Semantic Web Link Analysis to Discover Social Relationships in Academic Communities, Proceedings of the The 2005 Symposium on Applications and the Internet (SAINT'05), p.38-45, January 31-February 04, 2005 [doi>10.1109/SAINT.2005.58]
• 35: Junichiro Mori , Tatsuhiko Sugiyama , Yutaka Matsuo, Real-world oriented information sharing using social networks, Proceedings of the 2005 international ACM SIGGROUP conference on Supporting group work, November 06-09, 2005, Sanibel Island, Florida, USA [doi>10.1145/1099203.1099215]
• 36: J. Mori, Y. Matsuo, and M. Ishizuka. Finding user semantics on the web using word co-occurrence information. In Proc. Int'l. Workshop on Personalization on the Semantic Web (PersWeb05), 2005.
• 37: H. Nakagawa, A. Maeda, and H. Kojima. Automatic term recognition system TermExtract. http://gensen.dl.itc.utokyo.ac.jp/gensenweb eng.html.
• 38: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000
• 39: Takuichi Nishimura , Yoshiyuki Nakamura , Hideo Itoh , Hideyuki Nakashima, System Design of Event Space Information Support Utilizing CoBITs, Proceedings of the 24th International Conference on Distributed Computing Systems Workshops - W7: EC (ICDCSW'04), p.384-387, March 23-24, 2004
• 40: G. Palla, I. Derenyi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435:814, 2005.
• 41: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 42: M. Sahami and T. Heilman. A web-based kernel function for matching short text snippets. In International Workshop on Learning in Web Search (LWS2005), pp. 2--9, 2005.
• 43: Steffen Staab , Pedro Domingos , Peter Mika , Jennifer Golbeck , Li Ding , Tim Finin , Anupam Joshi , Andrzej Nowak , Robin R. Vallacher, Social Networks Applied, IEEE Intelligent Systems, v.20 n.1, p.80-93, January 2005 [doi>10.1109/MIS.2005.16]
• 44: 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
• 45: Nina Wacholder , Yael Ravin , Misook Choi, Disambiguation of proper names in text, Proceedings of the fifth conference on Applied natural language processing, p.202-208, March 31-April 03, 1997, Washington, DC [doi>10.3115/974557.974587]
• 46: S. Wasserman and K. Faust. Social network analysis. Methods and Applications. Cambridge University Press, Cambridge, 1994.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms

Keywords:
search engine, social network, web mining