skip to main content
10.1145/1242572.1242599acmconferencesArticle/Chapter ViewAbstractPublication PageswwwConference Proceedingsconference-collections
Article

Information flow modeling based on diffusion rate for prediction and ranking

Published:08 May 2007Publication History

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.Google ScholarGoogle Scholar
  2. U. Shardanand, and P. Maes, Social Information Filtering: Algorithms for Automating "Word of Mouth", CHI '95. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. G. Adomavicius, and A. Tuzhilin, Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions, IEEE Trans. Knowl. Data Eng. 17(6): 734--749, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, and J. Riedl, Grouplens: An open architecture for collaborative filtering of netnews. In Proc. of the ACM Conference on Computer Supported Cooperative Work: 175--186, 1994. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. X. Song, B. L. Tseng, C.-Y. Lin, and M.-T. Sun, Personalized Recommendation Driven by Information Flow, International ACM SIGIR Conference on Research & Development on Information Retrieval, Seattle, August 6-11, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. E. M. Rogers, Diffusion of Innovations, The Free Press: New York, 1995.Google ScholarGoogle Scholar
  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.Google ScholarGoogle ScholarCross RefCross Ref
  8. A. Pucci and M. Gori, Random-Walk Based Scoring Algorithm with Application to Recommender Systems for Large-Scale E-Commerce, WEBKDD 2006.Google ScholarGoogle Scholar
  9. S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer Networks, 30(1-7):107--117, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. A. N. Langville and C. D. Meyer. Deeper inside PageRank. Internet Mathematics, 1(3):335--400, 2004.Google ScholarGoogle ScholarCross RefCross Ref
  11. J. M. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5):604--632, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.Google ScholarGoogle ScholarCross RefCross Ref
  13. S. White and P. Smyth. Algorithms for estimating relative importance in networks. In Proc. of ACM SIGKDD Conf., 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.Google ScholarGoogle Scholar
  15. F. Bass, A new product growth for model consumer durables, Management Science 15 (5): p215--227, 1969.Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.Google ScholarGoogle ScholarCross RefCross Ref
  17. M. Richardson and P. Domingos, "Mining Knowledge-Sharing Sites for Viral Marketing," KDD 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. P. Domingos and M. Richardson, "Mining the Network Value of Customers," KDD 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. Proc. 9th ACM SIGKDD Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. D. Gruhl, R. Guha, D. Liben-Nowell, A. Tomkins, Information diffusion through blogspace, WWW 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. R. E. Kraut, R. E. Rice, C. Cool, and R. S. Fish, Varieties of Social Influence: The Role of Utility and Norms in the Success of a New Communication Medium, Organization Science, Vol. 9, No. 4, pp. 437--453, Jul.-Aug 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. Z. Dezso, E. Almaas, A. Lukacs, B. Racz, I. Szakadat, A.-L. Barabasi, Dynamics of information access on the webGoogle ScholarGoogle Scholar
  23. C. Dewes, A. Wichmann, and A. Feldmann, An analysis of Internet chat systems. ACM/SIGCOMM Internet Measurement Conference, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. J. G. Oliveira and A.-L. Barabási, Human dynamics: Darwin and Einstein correspondence patterns, Nature 437, 1251 2005.Google ScholarGoogle ScholarCross RefCross Ref
  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.Google ScholarGoogle Scholar
  26. D. D. Yao, First-Passage time Moments of Markov processes, Journal of Applied Probability, Vol. 22, No. 4, pp. 939--945, Dec., 1985.Google ScholarGoogle ScholarCross RefCross Ref
  27. P. Harrison, W. Knottenbelt, Passage Time Distributions in Large Markov Chains, ACM International Conference on Measurement and Modeling of Computer Systems, pp.77--85, June, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. J. R. Norris, Markov Chains, Cambridge University Press, 1997.Google ScholarGoogle Scholar
  29. S. M. Ross. Introduction to probability models. Academic Press, New York, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. I. G. Kemeny and J. L. Snell, Finite Markov Chains, Springer-Verlag. New York, 1976.Google ScholarGoogle Scholar

Index Terms

  1. Information flow modeling based on diffusion rate for prediction and ranking

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in
        • Published in

          cover image ACM Conferences
          WWW '07: Proceedings of the 16th international conference on World Wide Web
          May 2007
          1382 pages
          ISBN:9781595936547
          DOI:10.1145/1242572

          Copyright © 2007 ACM

          Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 8 May 2007

          Permissions

          Request permissions about this article.

          Request Permissions

          Check for updates

          Qualifiers

          • Article

          Acceptance Rates

          Overall Acceptance Rate1,899of8,196submissions,23%

          Upcoming Conference

          WWW '24
          The ACM Web Conference 2024
          May 13 - 17, 2024
          Singapore , Singapore

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader