Listening to the Flock - Towards opinion mining through data-parallel, semi-supervised learning on social graphs.

Christophe Van Gysel
Digitale computers zijn in staat om informatie sneller en op grotere schaal te verwerken dan mensen. Tijdens de Amerikaanse verkiezingen in 2012 speelde de analyse van persoonsinformatie een belangrijke rol voor het modelleren van kiezersgedrag. Dankzij deze modellen waren partijen in staat om zwevende kiezers te identificeren. Dit werk richt zich op een vergelijkbaar doel waarbij we publieke informatie van het sociale netwerk Twitter verzamelden over gebruikers in Vlaanderen.

Listening to the Flock - Towards opinion mining through data-parallel, semi-supervised learning on social graphs.

Digitale computers zijn in staat om informatie sneller en op grotere schaal te verwerken dan mensen. Tijdens de Amerikaanse verkiezingen in 2012 speelde de analyse van persoonsinformatie een belangrijke rol voor het modelleren van kiezersgedrag. Dankzij deze modellen waren partijen in staat om zwevende kiezers te identificeren. Dit werk richt zich op een vergelijkbaar doel waarbij we publieke informatie van het sociale netwerk Twitter verzamelden over gebruikers in Vlaanderen. Vervolgens gebruiken we deze informatie om de verschillende politieke invloeden in hun sociale netwerken te achterhalen. Het doel van het werk ligt op het verwerken van gegevens op een grote schaal en hoge snelheid zonder menselijke tussenkomst. Hoewel een persoon in sommige gevallen betere verbanden kan ontdekken in informatie, is het moeilijk om dit te verwezenlijken op gelijkaardige schaal. In december 2013 hebben we gegevens van Twitter verzameld van ongeveer 12 000 gebruikers. Van elk van deze gebruikers verkregen we hun volgers en tweehonderd meest recentste tweets via openbare Twitter informatiebronnen. Op basis van deze gegevens induceerden we een graafstructuur gebaseerd op de interacties tussen gebruikers, met name keken we naar gebruikers die een andere gebruiker volgen en gebruikers die tweets van een andere gebruiker retweeten. Vervolgens identificeerden we de Twitter accounts van Vlaamse politieke partijen en naarmate hun locatie in de social graph wisten we de overige gebruikers een kansdistributie over deze partijen toe te wijzen. Meer bepaald keken we naar de kans dat een random walk over de social graph terecht kwam bij een politieke partij, telkens beginnende bij een willekeurige gebruiker. Voor alle gebruikers opgenomen in het onderzoek verkregen we dus een verdeling over de voornaamste Vlaamse politieke partijen. Het is belangrijk om op te merken dat de enige voorkennis van het systeem, specifiek tot het Vlaamse politieke landschap, de Twitteraccounts waren van acht politieke partijen. Alle informatie en voorspellingen over Vlaamse kiezers werd dus afgeleid van deze minimale domeinkennis. Om onze resultaten te beoordelen verkregen we lijsten van Twitter accounts van politiek geëngageerden. Deze lijsten werden gepubliceerd door de Vlaamse politieke partijen op Twitter. We veronderstellen dat gebruikers die deel uitmaken van deze lijsten gelinkt zijn met de partij die ze beschikbaar stelde. In totaal verkregen we een validatie set van 700 gebruikers. Na uitvoering van de random walk vergeleken we voor elke gebruiker in de validatie set de sterkste partij in hun individuele verdelingen met de partij waarmee ze gelinkt werden. Onze voorspelling is correct voor gemiddeld 85% van de politiek geëngageerden. Bijkomend merkten we op dat als een voorspelling verkeerd was, ze nog steeds relatief dichtbij viel in het politiek spectrum tegenover de gelinkte partij. Bijvoorbeeld werden gebruikers geassocieerd met een extreemlinkse partij voorspeld te behoren tot een meer gematigde linkse strekking. Onze resultaten kunnen echter niet gebruikt worden als een voorspelling van de verkiezingsuitslag. De Twitterpopulatie is nu eenmaal geen representatieve voorstelling van de Vlaamse kiezers. Bijkomend merken we ook op dat de politieke instelling van politiek geëngageerden nu eenmaal eenvoudiger te achterhalen is dan die van overige gebruikers. Vanwege het stemgeheim is het moeilijk om een validatie set te bekomen waarvan eveneens niet-politiek geëngageerde gebruikers deel uitmaken. In mei 2014, een week voor de Vlaamse verkiezingen, publiceerde de Universiteit Antwerpen in samenwerking met de onderzoeksgroep ADReM een persbericht over het onderzoek verricht in dit werk. Gelijktijdig met het persbericht werd ook een website (twitterbrengtraad.be) gelanceerd waarop individuele gebruikers hun resultaten konden opvragen. Het bericht werd verspreid door de meeste grote Vlaamse nieuwswebsites, verscheen in een aantal Vlaamse kranten (Metro, Het Laatste Nieuws en De Standaard) en werd besproken op de Vlaamse publieke omroep (Radio 1).

Bibliografie

S. Asmussen. Applied Probability and Queues. Wiley, 1987. Arik Azran. The rendezvous algorithm: Multiclass semi-supervised learning with markov random walks. In Proceedings of the 24th International Conference on Machine Learning, 2007. Shumeet Baluja, Rohan Seth, D. Sivakumar, Yushi Jing, Jay Yagnik, Shankar Kumar, Deepak Ravichandran, and Mohamed Aly. Video suggestion and discovery for youtube: Taking random walks through the view graph. In Proceedings of the 17th International Conference on World Wide Web, WWW ’08, pages 895–904, New York, NY, USA, 2008. ACM. ISBN 978-1-60558-085-2. doi: 10.1145/1367497.1367618. URL http://doi.acm.org/10.1145/ 1367497.1367618. Adam Bermingham and Alan F. Smeaton. Classifying sentiment in microblogs: Is brevity an advantage? In Proceedings of the 19th ACM International Conference on Information and Knowledge Management, CIKM ’10, pages 1833–1836, New York, NY, USA, 2010. ACM. ISBN 978-1-4503-0099-5. doi: 10.1145/1871437.1871741. URL http://doi.acm.org/10.1145/1871437. 1871741. Smriti Bhagat, Graham Cormode, and S. Muthukrishnan. Node classification in social networks. CoRR, abs/1101.3291, 2011. Danah Boyd, Scott Golder, and Gilad Lotan. Tweet, tweet, retweet: Conversational aspects of retweeting on twitter. In Proceedings of the 2010 43rd Hawaii International Conference on System Sciences, HICSS ’10, pages 1–10, Washington, DC, USA, 2010. IEEE Computer Society. ISBN 978-0-7695-3869- 3. doi: 10.1109/HICSS.2010.412. URL http://dx.doi.org/10.1109/HICSS. 2010.412. David Recordon Brad Fitzpatrick. Thoughts on the social graph, 2007. URL http://bradfitz.com/social-graph-problem/. Visited on 18/05/2014. Doug Braun. The evils of reciprocal following on twitter. URL http://thedustpan.com/2010/03/evils-of-reciprocal-following/. Visited on 05/01/14. Olivier Chapelle, Bernhard Schlkopf, and Alexander Zien. Semi-Supervised Learning. The MIT Press, 1st edition, 2010. ISBN 0262514125, 9780262514125. CLiPS. Belgian elections, june 13, 2010 - twitter opinion mining. http://www.clips.ua.ac.be/pages/pattern-examples-elections. Accessed: 2014-01-26. Frances Perry Stephen Adams Robert R. Henry Robert Bradshaw Nathan Weizenbaum Craig Chambers, Ashish Raniwala. Flume-java: Easy, efcient data-parallel pipelines. http://faculty.neu.edu. cn/cc/zhangyf/cloud-bigdata/papers/big%20data%20programming/ FlumeJava-pldi-2010.pdf, 2010. Jef Dean and Sanjay Ghemawat. Mapreduce: Simplied data processing on large clusters. http://static.usenix.org/event/osdi04/tech/full_papers/ dean/dean.pdf, 2004. K. Deschouwer. De stemmen van het volk: een analyse van het kiesgedrag in Vlaanderen en Wallonië op 7 juni 2009. VUBPress, 2010. ISBN 9789054877356. URL http://books.google.co.uk/books?id=tQj2afpZOfwC. Reinhard Diestel. Graph Theory {Graduate Texts in Mathematics; 173}. Springer-Verlag Berlin and Heidelberg GmbH & Company KG, 2000. Jim Dougherty. Why reciprocal following on twitter does not matter. URL http://leaderswest.com/2012/01/05/you-dont-need-to-follow-me-but-i-appr…. Visited on 05/01/14. Charles Duhigg. Campaigns mine personal lives to get out vote. URL http://www.nytimes.com/2012/10/14/us/politics/ campaigns-mine-personal-lives-to-get-out-vote.html. Visited on 05/04/14. William Feller. An Introduction to Probability Theory and Its Applications, volume 1. Wiley, January 1968. ISBN 0471257087. URL http: //www.amazon.ca/exec/obidos/redirect?tag=citeulike04-20{&}path= ASIN/0471257087. The Apache Software Foundation. Apache crunch: Simple and efficient mapreduce pipelines. http://crunch.apache.org/, 2013. M.S. Granovetter. The Strength of Weak Ties. The American Journal of Sociology, 78(6):1360–1380, 1973.Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference and prediction. Springer, 2 edition, 2008. URL http://scholar.google.com/scholar.bib?q=info:roqIsr0iT4UJ: scholar.google.com/&output=citation&hl=en&ct=citation&cd=0.Gaby Hinsliff. Web 2.0: the new election superweapon. URL http://www.theguardian.com/politics/2010/apr/11/ new-media-election-campaign. Visited on 04/01/14. Philip N. Howard. The arab springs cascading effects. URL http://www.psmag.com/navigation/politics-and-law/the-cascading-effects-…. Visited on 04/01/14. Shunsuke Ihara. Information theory for continuous systems. World Scientific, 1993. ISBN 978-981-02-0985-8. Frederic Jacobs. Do you want to know more about belgium? http://www. youtube.com/watch?v=Ceg6NQKHd70. Accessed: 2014-01-18. R. Junco, G. Heiberger, and E. Loken. The effect of twitter on college student engagement and grades. Journal of Computer Assisted Learning, 27(2):119– 132, 2011. ISSN 1365-2729. doi: 10.1111/j.1365-2729.2010.00387.x. URL http://dx.doi.org/10.1111/j.1365-2729.2010.00387.x. Andreas M Kaplan and Michael Haenlein. Users of the world, unite! the challenges and opportunities of social media. Business horizons, 53(1):59–68, 2010. Andreas M. Kaplan and Michael Haenlein. The early bird catches the news: Nine things you should know about micro-blogging. Business Horizons, 54 (2):105–113, March 2011. URL http://ideas.repec.org/a/eee/bushor/v54yi2p105-113.html. Jemima Kiss. Facebook’s 10th birthday: from college dorm to 1.23 billion users. 2014. URL http://www.theguardian.com/technology/2014/feb/ 04/facebook-10-years-mark-zuckerberg. Visited on 29/04/14. Gueorgi Kossinets. Effects of missing data in social networks. Social Networks, 28:247–268, 2003. Efthymios Kouloumpis, Theresa Wilson, and Johanna Moore. Twitter sentiment analysis: The good the bad and the omg! In Lada A. Adamic, Ri- cardo A. Baeza-Yates, and Scott Counts, editors, ICWSM. The AAAI Press, 2011. URL http://dblp.uni-trier.de/db/conf/icwsm/icwsm2011.html# KouloumpisWM11. Raffi Krikorian. Introducing twitter data grants, 2014. URL https://blog.twitter.com/2014/introducing-twitter-data-grants. P. F. Lazarsfeld and R. K. Merton. Friendship as a social process: a substantive and methodological analysis. In M. Berger, editor, Freedom and Control in Modern Society, pages 18–66. New York: Van Nostrand, 1954. Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’06, pages 631–636, New York, NY, USA, 2006. ACM. ISBN 1-59593-339-5. doi: 10.1145/1150402.1150479. URL http://doi.acm.org/10.1145/1150402.1150479. Qing Lu and Lise Getoor. Link-based classification using labeled and unlabeled data. In ICML Workshop on ’The Continuum from Labeled to Unlabeled Data in Machine Learning and Data Mining’, 2003. Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. Introduction to Information Retrieval. Cambridge University Press, New York, NY, USA, 2008. ISBN 0521865719, 9780521865715. Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual Review of Sociology, 27(1):415– 444, 2001. doi: 10.1146/annurev.soc.27.1.415. URL http://arjournals. annualreviews.org/doi/abs/10.1146/annurev.soc.27.1.415. Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi, Peter Druschel, and Bobby Bhattacharjee. Measurement and analysis of online social networks. In In Proceedings of the 5th ACM/USENIX Internet Measurement Conference (IMC07, 2007. Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2012. ISBN 026201825X, 9780262018258. Jennifer Neville and David Jensen. Iterative classification of relational data. In Papers of the AAAI-2000 Workshop on Learning Statistical Models From Relational Data. AAAI Press, 2000. Puteri N.E. Nohuddin, Rob Christley, Frans Coenen, Yogesh Patel, Christian Setzkorn, and Shane Williams. Social network trend analysis using frequent pattern mining and self organizing maps. In Max Bramer, Miltos Petridis, and Adrian Hopgood, editors, Research and Development in Intelligent Systems XXVII, pages 311–324. Springer London, 2011. ISBN 978-0-85729-129- 5. doi: 10.1007/978-0-85729-130-1 24. URL http://dx.doi.org/10.1007/ 978-0-85729-130-1_24. Larry Page, Sergey Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web, 1998. Alexander Pak and Patrick Paroubek. Twitter as a corpus for sentiment analysis and opinion mining. In Nicoletta Calzolari (Conference Chair), Khalid Choukri, Bente Maegaard, Joseph Mariani, Jan Odijk, Stelios Piperidis, Mike Rosner, and Daniel Tapias, editors, Proceedings of the Seventh International Conference on Language Resources and Evaluation (LREC’10), Valletta, Malta, may 2010. European Language Resources Association (ELRA). ISBN 2-9517408-6-7. Bo Pang and Lillian Lee. Opinion mining and sentiment analysis, January 2008. ISSN 1554-0669. URL http://dx.doi.org/10.1561/1500000011. Alexandrin Popescul, Lyle H. Ungar, Steve Lawrence, and David M. Pennock. Towards structural logistic regression: Combining relational and statistical learning, 2002. Paul Resnick and Hal R. Varian. Recommender systems. Commun. ACM, 40 (3):56–58, March 1997. ISSN 0001-0782. doi: 10.1145/245108.245121. URL http://doi.acm.org/10.1145/245108.245121. Jeff J. Roberts. Typical twitter user is a young woman with an iphone & 208 followers. URL http://gigaom.com/2012/10/10/the-typical-twitter-user-is-a-young-woman-…. Visited on 05/01/14. Jari Saramäki and JP Onnela. Structure and tie strengths in mobile communication networks. Proc. Natl. Acad. Sci. (USA), page 7332, 2007. Kurt Scholle. Follow you follow me increase twitter followers with reciprocal follows. URL http://website-roi-guy.com/76/twitter/. Visited on 05/01/14. Kyle Siegrist. Virtual Laboratories in Probability and Statistics. University of Alabama in Huntsville, 2001. URL http://www.math.uah.edu/stat/. Visited on 04/01/14. Martin Szummer and Tommi Jaakkola. Partially labeled classification with markov random walks. In Advances in Neural Information Processing Systems, pages 945–952. MIT Press, 2002. The Apache Software Foundation. Apache hadoop. http://hadoop.apache. org/, 2005. The Apache Software Foundation. Apache spark: Lightning-fast cluster computing. http://spark.apache.org/, 2013. A. M. Turing. Computing machinery and intelligence. 59(236):433–460, October 1950. ISSN 0026-4423. URL http://turing.ecs.soton.ac.uk/browse. php/B/19;http://turing.ecs.soton.ac.uk/browse.php/B/9. Twitter. Twitter api, a. URL https://dev.twitter.com. Visited on 11/01/14. Twitter. Twitter api, b. URL https://dev.twitter.com/docs/entities. Visited on 11/01/14. Twitter. Twitter api, c. URL https://dev.twitter.com/docs/platform-objects/tweets. Visited on 11/01/14. S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994. Eric W. Weisstein. Markov chain, a. URL http://mathworld.wolfram.com/MarkovChain.html. Visited on 02/01/14. Eric W. Weisstein. Matrix power, b. URL http://mathworld.wolfram.com/MatrixPower.html. Visited on 03/01/14. Eric W. Weisstein. Random walk, c. URL http://mathworld.wolfram.com/RandomWalk.html. Visited on 04/01/14. Eric W. Weisstein. Stochastic matrix, d. URL http://mathworld.wolfram.com/StochasticMatrix.html. Visited on 02/01/14. Theresa Wilson, Janyce Wiebe, and Paul Hoffmann. Recognizing contextual polarity in phrase-level sentiment analysis. In Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing, HLT ’05, pages 347–354, Stroudsburg, PA, USA, 2005. Association for Computational Linguistics. doi: 10.3115/1220575.1220619. URL http: //dx.doi.org/10.3115/1220575.1220619. Yiming Yang, Sean Slattery, and Rayid Ghani. A study of approaches to hyper-text categorization. Journal of Intelligent Information Systems, 18:219–241, 2002. Shaozhi Ye, Juan Lang, and Felix Wu. Crawling online social graphs. In Proceedings of the 2010 12th International Asia-Pacific Web Conference, APWEB ’10, pages 236–242, Washington, DC, USA, 2010. IEEE Computer Society. ISBN 978-0-7695-4012-2. doi: 10.1109/APWeb.2010.10. URL http://dx.doi.org/10.1109/APWeb.2010.10. Emma Young. Crisis puts a new face on social networking. URL http://www.smh.com.au/federal-politics/crisis-puts-a-new-face-on-social…. Visited on 04/01/14. Xiaojin Zhu. Semi-supervised learning literature survey. Technical Report 1530, Computer Sciences, University of Wisconsin-Madison, 2005. URL http:// pages.cs.wisc.edu/~jerryzhu/pub/ssl_survey.pdf. Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Semi-supervised learning using gaussian fields and harmonic functions, 2003.

Universiteit of Hogeschool
Master in de informatica: databases
Publicatiejaar
2014
Kernwoorden
https://twitter.com/iamchrizzle
Share this on: