iLink: search and routing in social networks

ABSTRACT

The growth of Web 2.0 and fundamental theoretical breakthroughs have led to an avalanche of interest in social networks. This paper focuses on the problem of modeling how social networks accomplish tasks through peer production style collaboration. We propose a general interaction model for the underlying social networks and then a specific model (iLink for social search and message routing. A key contribution here is the development of a general learning framework for making such online peer production systems work at scale. The iLink model has been used to develop a system for FAQ generation in a social network (FAQtory), and experience with its application in the context of a full-scale learning-driven workflow application (CALO) is reported. We also discuss methods of adapting iLink technology for use in military knowledge sharing portals and other message routing systems. Finally, the paper shows the connection of iLink to SQM, a theoretical model for social search that is a generalization of Markov Decision Processes and the popular Pagerank model.

REFERENCES

• 1: L. A. Adamic and E. Adar. How to search a social network. Social Networks, 27(3):187--203, July 2005.
• 2: A. Banerjee and S. Basu. A social query model for decentralized search. Technical report, University of Minnesota, 2007.
• 3: A. Banerjee and S. Basu. Topic models over text streams: A study of batch and online unsupervised learning. In Proc. of the 7th SIAM Intl. Conf. on Data Mining, 2007.
• 4: A. Banerjee, S. Basu, and S. Merugu. Multiway clustering on relation graphs. In Proc. of the 7th SIAM Intl. Conf. on Data Mining, 2007.
• 5: Sugato Basu , Mikhail Bilenko , Raymond J. Mooney, A probabilistic framework for semi-supervised clustering, 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.1014062]
• 6: G. W. Beck and V. Wieland. Learning and control in a changing economic environment. Journal of Economic Dynamics and Control, 26(9-10):1359--1377, August 2002.
• 7: R. Bellman. A Markovian decision process. Journal of Mathematics and Mechanics 6, pages 679--684, 1957.
• 8: Y. Benkler. Coase's penguin, or Linux and the nature of the firm. Yale Law Journal, 112, 2002.
• 9: Y. Benkler. The Wealth of Networks. Yale University Press, 2006.
• 10: L. Y.-K. Blanc, A. and A. Vahdat. Designing incentives for peer-to-peer routing. In 2nd wokshop on Economics of peer-to-peer Systems, 2004.
• 11: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 12: R. Cross, A. Parker, L. Prusak, and S. Borgatti. Knowing what we know: Supporting knowledge creation and sharing in social networks. Organizational Dynamics, 302(2):100--120, 2001.
• 13: Prasanna Desikan , Nishith Pathak , Jaideep Srivastava , Vipin Kumar, Incremental page rank computation on evolving graphs, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062885]
• 14: Inderjit S. Dhillon , Subramanyam Mallela , Rahul Kumar, A divisive information theoretic feature clustering algorithm for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 15: R. A. Ghosh. Cooking pot markets: An economic model for the trade in free goods and services on the internet. First Monday, 3(3), 1998.
• 16: Tad Hogg , Lada Adamic, Enhancing reputation mechanisms via online social networks, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988811]
• 17: S. M. Kakade, M. Kearns, L. E. Ortiz, R. Pemantle, and S. Suri. Economic properties of social networks. In Advances in Neural Info. Processing Systems 17, 2005.
• 18: Henry Kautz , Bart Selman , Mehul Shah, Referral Web: combining social networks and collaborative filtering, Communications of the ACM, v.40 n.3, p.63-65, March 1997 [doi>10.1145/245108.245123]
• 19: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 20: Jon Kleinberg , Prabhakar Raghavan, Query Incentive Networks, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.132-141, October 23-25, 2005 [doi>10.1109/SFCS.2005.63]
• 21: J. Lerner and J. Tirole. Some simple economics of open source. Journal of Industrial Economics, 50(2):197--234, 2002.
• 22: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 23: D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic routing in social networks. Proc. National Academy of Sciences, 102(33), 2005.
• 24: A. McCallum, A. Corrada-Emmanuel, and X. Wang. Topic and role discovery in social networks. In Proc. of Intl. Joint Conf. on AI, 2005.
• 25: Srujana Merugu , Joydeep Ghosh, A privacy-sensitive approach to distributed clustering, Pattern Recognition Letters, v.26 n.4, p.399-410, March 2005 [doi>10.1016/j.patrec.2004.08.003]
• 26: M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.
• 27: R. Pemantle and B. Skyrms. A dynamic model of social network formation. Proc. of the National Academy of Sciences, 2000.
• 28: Eric S. Raymond , Tim O'Reilly, The Cathedral and the Bazaar, O'Reilly & Associates, Inc., Sebastopol, CA, 1999
• 29: 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]
• 30: Don Tapscott , Anthony D. Williams, Wikinomics: How Mass Collaboration Changes Everything, Portfolio Hardcover, 2006
• 31: Christoph Tempich , Steffen Staab , Adrian Wranik, Remindin': semantic query routing in peer-to-peer networks based on social metaphors, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988759]
• 32: Dimitrios Tsoumakos , Nick Roussopoulos, Adaptive Probabilistic Search for Peer-to-Peer Networks, Proceedings of the 3rd International Conference on Peer-to-Peer Computing, p.102, September 01-03, 2003
• 33: D. Watts and S. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393(6684):440--442, 1998.
• 34: D. J. Watts, P. S. Dodds, and M. E. J. Newman. Identity and search in social networks. Science, 296:1302--1305, 2002.
• 35: F. Wu, B. A. Huberman, L. A. Adamic, and J. R. Tyler. Information flow in social groups. Physica A, 337:327--335,2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

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

General Terms:
Algorithms, Experimentation

Keywords:
expert identification, learning, message routing, peer production, smart RSS, social FAQ generation, social search