Information flow modeling based on diffusion rate for prediction and ranking

ABSTRACT

Information flows in a network where individuals influence each other. The diffusion rate captures how efficiently the information can diffuse among the users in the network. We propose an information flow model that leverages diffusion rates for: (1) prediction . identify where information should flow to, and (2) ranking . identify who will most quickly receive the information. For prediction, we measure how likely information will propagate from a specific sender to a specific receiver during a certain time period. Accordingly a rate-based recommendation algorithm is proposed that predicts who will most likely receive the information during a limited time period. For ranking, we estimate the expected time for information diffusion to reach a specific user in a network. Subsequently, a DiffusionRank algorithm is proposed that ranks users based on how quickly information will flow to them. Experiments on two datasets demonstrate the effectiveness of the proposed algorithms to both improve the recommendation performance and rank users by the efficiency of information flow.

REFERENCES

• 1: R. B. Cialdini, Influence: Science and Practice, Apr 2003.
• 2: Upendra Shardanand , Pattie Maes, Social information filtering: algorithms for automating “word of mouth”, Proceedings of the SIGCHI conference on Human factors in computing systems, p.210-217, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223931]
• 3: Gediminas Adomavicius , Alexander Tuzhilin, Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.734-749, June 2005 [doi>10.1109/TKDE.2005.99]
• 4: Paul Resnick , Neophytos Iacovou , Mitesh Suchak , Peter Bergstrom , John Riedl, GroupLens: an open architecture for collaborative filtering of netnews, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.175-186, October 22-26, 1994, Chapel Hill, North Carolina, United States [doi>10.1145/192844.192905]
• 5: Xiaodan Song , Belle L. Tseng , Ching-Yung Lin , Ming-Ting Sun, Personalized recommendation driven by information flow, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148258]
• 6: E. M. Rogers, Diffusion of Innovations, The Free Press: New York, 1995.
• 7: V. Mahajan, E. Muller, F. Bass. New Product Diffusion Models in Marketing: A Review and Directions for Research. Journal of Marketing 54:1, pp. 1--26, 1990.
• 8: A. Pucci and M. Gori, Random-Walk Based Scoring Algorithm with Application to Recommender Systems for Large-Scale E-Commerce, WEBKDD 2006.
• 9: 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
• 10: A. N. Langville and C. D. Meyer. Deeper inside PageRank. Internet Mathematics, 1(3):335--400, 2004.
• 11: 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]
• 12: K. Berberich, M. Vazirgiannis, and G. Weikum, T-Rank: Time-aware Authority Ranking, 3rd Workshop on Algorithms and Models for the Web-Graph, October 2004.
• 13: Scott White , Padhraic Smyth, Algorithms for estimating relative importance in 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.956782]
• 14: E. Adar, L. Zhang, L. A. Adamic, R. M. Lukose, Implicit Structure and the Dynamics of Blogspace, Workshop on the Weblogging Ecosystem, May 18th, 2004.
• 15: F. Bass, A new product growth for model consumer durables, Management Science 15 (5): p215--227, 1969.
• 16: S. Hill, F. Provost, and C. Volinsky, Network-Based Marketing: Identifying Likely Adopters via Consumer Networks, Statist. Sci. 21, no. 2, 256--276, 2006.
• 17: Matthew Richardson , Pedro Domingos, Mining knowledge-sharing sites for viral marketing, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775057]
• 18: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 19: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, 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.956769]
• 20: Daniel Gruhl , R. Guha , David Liben-Nowell , Andrew Tomkins, Information diffusion through blogspace, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988739]
• 21: Robert E. Kraut , Ronald E. Rice , Colleen Cool , Robert S. Fish, Varieties of Social Influence: the Role of Utility and Norms in the Success of a New Communication Medium, Organization Science, v.9 n.4, p.437-453, April 1998 [doi>10.1287/orsc.9.4.437]
• 22: Z. Dezso, E. Almaas, A. Lukacs, B. Racz, I. Szakadat, A.-L. Barabasi, Dynamics of information access on the web
• 23: Christian Dewes , Arne Wichmann , Anja Feldmann, An analysis of Internet chat systems, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948214]
• 24: J. G. Oliveira and A.-L. Barabási, Human dynamics: Darwin and Einstein correspondence patterns, Nature 437, 1251 2005.
• 25: A. Vázquez, J. G. Oliveira, Z. Dezsö, K.-I. Goh, I. Kondor & A.-L. Barabasi, Modeling bursts and heavy tails in human dynamics Phys. Rev. E 73, 036127, 2006.
• 26: D. D. Yao, First-Passage time Moments of Markov processes, Journal of Applied Probability, Vol. 22, No. 4, pp. 939--945, Dec., 1985.
• 27: Peter G. Harrison , William J. Knottenbelt, Passage time distributions in large Markov chains, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 28: J. R. Norris, Markov Chains, Cambridge University Press, 1997.
• 29: Sheldon M. Ross, Introduction to Probability Models, Ninth Edition, Academic Press, Inc., Orlando, FL, 2006
• 30: I. G. Kemeny and J. L. Snell, Finite Markov Chains, Springer-Verlag. New York, 1976.

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Experimentation

Keywords:
collaborative filtering, continuous-time Markov chain, diffusion of innovation, information flow, recommendation, social influence, web ranking