nach oben

Journal of Intelligent Information Systems

Erschienen in:

01.04.2013

Meme ranking to maximize posts virality in microblogging platforms

verfasst von: Francesco Bonchi, Carlos Castillo, Dino Ienco

Erschienen in: Journal of Intelligent Information Systems | Ausgabe 2/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Microblogging is a modern communication paradigm in which users post bits of information, or “memes” as we call them, that are brief text updates or micromedia such as photos, video or audio clips. Once a user post a meme, it become visible to the user community. When a user finds a meme of another user interesting, she can eventually repost it, thus allowing memes to propagate virally trough the social network. In this paper we introduce the meme ranking problem, as the problem of selecting which k memes (among the ones posted by their contacts) to show to users when they log into the system. The objective is to maximize the overall activity of the network, that is, the total number of reposts that occur. We deeply characterize the problem showing that not only exact solutions are unfeasible, but also approximated solutions are prohibitive to be adopted in an on-line setting. Therefore we devise a set of heuristics and we compare them trough an extensive simulation based on the real-world Yahoo! Meme social graph, using parameters learnt from real logs of meme propagations. Our experimentation demonstrates the effectiveness and feasibility of these methods.

Vorheriger Artikel Toward finding hidden communities based on user profile

Nächster Artikel Catching a viral video

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

http://meme.yahoo.com

Animations of several meme propagations are available at http://barcelona.research.yahoo.net/memerank.

This problem is in a sense the converse of the Influence Maximization problem, defined in Kempe et al. (2003) in the context of Viral Marketing. In their problem it is given a single piece of information and the problem is that of identifying k users from which to start the propagations so to maximize the expected spread. Oppositely in our problem we are given a single user and we want to select k memes to propagate.

The probability of a possible world X is given by

$$Pr[X] = \prod\limits_{e \in E_X} p(e) \prod\limits_{e \in E \setminus E_X} (1 - p(e))~,$$

where $E_X \subseteq E$ denotes the set of arcs for which the coin flip has given a positive outcome in X.

http://en.wikipedia.org/wiki/Borda_count

Yahoo! Meme slogan is CREATE-FOLLOW-REPOST.

Adar, E., & Adamic, L. A. (2005). Tracking information epidemics in blogspace. In Web Intelligence.

Agarwal, N., Liu, H., Tang, L., & Yu, P. S. (2008). Identifying the influential bloggers in a community. In Proceedings of the first international conference on Web search and Web data mining, (WSDM’08).

Backstrom, L., Huttenlocher, D. P., Kleinberg, J. M., & Lan, X. (2006). Group formation in large social networks: Membership, growth, and evolution. In Proceedings of the 12th ACM SIGKDD international conference on knowledge discovery and data mining (KDD’06).

Baeza-Yates, R., & Ribeiro-Neto, B. (1999). Modern information retrieval. Addison Wesley.

Bakshy, E., Karrer, B., & Adamic, L. A. (2009). Social influence and the diffusion of user-created content. In EC ’09: Proceedings of the tenth ACM conference on electronic commerce, pp. 325–334, New York, NY, USA, ACM.

Cha, M., Haddadi, H., Benevenuto, F., & Gummadi, K. P. (2010). Measuring user influence in Twitter: The million follower fallacy. In In Proceedings of the 4th international AAAI conference on weblogs and social media (ICWSM).

Cha, M., Mislove, A., & Gummadi, P. K. (2009). A measurement-driven analysis of information propagation in the Flickr social network. In Proceedings of the 18th international conference on World Wide Web (WWW’09).

Chen, W., Wang, C., & Wang, Y. (2010a). Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proc. of the 16th ACM SIGKDD int. conf. on knowledge discovery and data mining (KDD’10).

Chen, W., Wang, Y., & Yang, S. (2009). Efficient influence maximization in social networks. In Proc. of the 15th ACM SIGKDD int. conf. on knowledge discovery and data mining (KDD’09).

Chen, W., Yuan, Y., & Zhang, L. (2010b). Scalable influence maximization in social networks under the linear threshold model. In Proceedings of the 10th IEEE international conference on data mining (ICDM’2010).

Crandall, D. J., Cosley, D., Huttenlocher, D. P., Kleinberg, J. M., & Suri, S. (2008). Feedback effects between similarity and social influence in online communities. In Proc. of the 14th ACM SIGKDD int. conf. on knowledge discovery and data mining (KDD’08).

Domingos, P., & Richardson, M. (2001). Mining the network value of customers. In Proc. of the seventh ACM SIGKDD int. conf. on knowledge discovery and data mining (KDD’01).

Friedkin, N. E. (1998). A structural theory of social influence. Cambridge University Press.

Golbeck, J., & Hendler, J. (2006). Inferring binary trust relationships in web-based social networks. ACM Transactions on Internet Technology, 6(4), 497–529.CrossRef

Goyal, A., Bonchi, F., & Lakshmanan, L. (2010). Learning influence probabilities in social networks. In Proceedings of the third ACM international conference on Web search and data mining (WSDM 2010).

Gruhl, D., Guha, R. V., Liben-Nowell, D., & Tomkins, A. (2004). Information diffusion through blogspace. In Proceedings of the 13th international conference on World Wide Web, (WWW’04).

Guha, R., Kumar, R., Raghavan, P., & Tomkins, A. (2004). Propagation of trust and distrust. In Proceedings of the 13th international conference on World Wide Web (WWW’04).

Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 13–30.MathSciNetMATHCrossRef

Java, A., Song, X., Finin, T., & Tseng, B. (2007). Why we Twitter: Understanding microblogging usage and communities. In Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis.

Jianshu Weng, J. J., Lim, Ee-P., & He, Q. (2010). Twitterrank: Finding topic-sensitive influential twitterers. In WSDM, p. 10.

Kempe, D., Kleinberg, J. M., & Tardos, É. (2003). Maximizing the spread of influence through a social network. In Proc. of the ninth ACM SIGKDD int. conf. on knowledge discovery and data mining (KDD’03).

Lerman, K., & Jones, L. (2006). Social browsing on flickr. CoRR, abs/cs/0612047.

Leskovec, J., Backstrom, L., & Kleinberg, J. (2009). Meme-tracking and the dynamics of the news cycle. In Proc. of the 15th ACM SIGKDD int. conf. on knowledge discovery and data mining (KDD’09).

Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005). Graphs over time: Densification laws, shrinking diameters and possible explanations. New York, NY.

Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., & Glance, N. S. (2007). Cost-effective outbreak detection in networks. In Proc. of the 13th ACM SIGKDD int. conf. on knowledge discovery and data mining (KDD’07).

Leskovec, J., Singh, A., & Kleinberg, J. M. (2006). Patterns of influence in a recommendation network. In Proceedings of the 10th Pacific-Asia conference on knowledge discovery and data mining, (PAKDD’06).

Mislove, A., Marcon, M., Gummadi, K. P., Druschel, P., & Bhattacharjee, B. (2007). Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM conference on internet measurement (IMC’07).

Mitzenmacher, M., & Upfal, E. (2005). Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press.

Richardson, M., & Domingos, P. (2002). Mining knowledge-sharing sites for viral marketing. In Proc. of the eighth ACM SIGKDD int. conf. on knowledge discovery and data mining (KDD’02).

Samper, J. J., Castillo, P. A., Araujo, L., & Guervós, J. J. M. (2006). Nectarss, an rss feed ranking system that implicitly learns user preferences. CoRR, abs/cs/0610019.

Song, X., Chi, Y., Hino, K., & Tseng, B. L. (2007). Information flow modeling based on diffusion rate for prediction and ranking. In Proceedings of the 16th international conference on World Wide Web (WWW’07).

Song, X., Tseng, B. L., Lin, C.-Y., & Sun, M.-T. (2006). Personalized recommendation driven by information flow. In Proceedings of the 29th annual international ACM SIGIR conference on research and development in information retrieval (SIGIR’06).

Taherian, M., Amini, M., & Jalili, R. (2008). Trust inference in web-based social networks using resistive networks. In Proceedings of the 2008 third international conference on internet and web applications and services (ICIW’08).

Tang, J., Sun, J., Wang, C., & Yang, Z. (2009). Social influence analysis in large-scale networks. In Proc. of the 15th ACM SIGKDD int. conf. on knowledge discovery and data mining (KDD’09).

Valiant, L. G. (1979). The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3), 410–421.MathSciNetMATHCrossRef

Wu, F., Huberman, B. A., Adamic, L. A., & Tyler, J. R. (2004). Information flow in social groups. Physica A: Statistical and Theoretical Physics, 337(1–2), 327–335.MathSciNetCrossRef

Zaki, M. J. (2005). Efficiently mining frequent trees in a forest: Algorithms and applications. IEEE Transactions on Knowledge and Data Engineering, 17(8), 1021–1035 (special issue on Mining Biological Data).CrossRef

Ziegler, C.-N., & Lausen, G. (2005). Propagation models for trust and distrust in social networks. Information Systems Frontiers, 7(4–5), 337–358.CrossRef

Titel: Meme ranking to maximize posts virality in microblogging platforms
verfasst von: Francesco Bonchi
Carlos Castillo
Dino Ienco
Publikationsdatum: 01.04.2013
Verlag: Springer US
Erschienen in: Journal of Intelligent Information Systems / Ausgabe 2/2013
Print ISSN: 0925-9902
Elektronische ISSN: 1573-7675
DOI: https://doi.org/10.1007/s10844-011-0181-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2013

Toward finding hidden communities based on user profile

Tag recommendation by machine learning with textual and social features

UniDis: a universal discretization technique

Iterative classification for multiple target attributes

Reducing the size of databases for multirelational classification: a subgraph-based approach

Special issue on SIASP at ICDM 2010