COMPETITIVE DIFFUSION IN SOCIAL NETWORKS
RUDRA MOHAN TRIPATHY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING INDIAN INSTITUTE OF TECHNOLOGY DELHI
JULY 2012
Indian Institute of Technology Delhi (IITD), New Delhi, 2012 c
All rights reserved.
COMPETITIVE DIFFUSION IN SOCIAL NETWORKS
by
RUDRA MOHAN TRIPATHY
Department of Computer Science and Engineering
Submitted
in fulfillment of the requirements of the degree of Doctor of Philosophy
to the
Indian Institute of Technology Delhi
July 2012
Certificate
This is to certify that the thesis titled Competitive Diffusion in Social Net- works being submitted by Rudra Mohan Tripathy for the award of Doctor of Philosophy in Computer Science & Engineering is a record of bona fide work carried out by him under my guidance and supervision at the Department of Com- puter Science & Engineering, Indian Institute of Technology Delhi. The work presented in this thesis has not been submitted elsewhere, either in part or full, for the award of any other degree or diploma.
Dr. Amitabha Bagchi Associate professor
Department of Computer Science & Engineering Indian Institute of Technology Delhi
New Delhi
Acknowledgments
I would like to express my deep and sincere gratitude to Dr. Amitabha Bagchi, under whose supervision and guidance, I had the privilege to do my research work.
I am deeply indebted to him for his kind help, lasting encouragement and valuable suggestions rendered to me through the entire period of my research work. I am thankful to him for his tolerance and having continued faith in my research capabilities for several years. I would also like to thank him for extending financial support to enable me to visit Canada for presenting one of my papers.
I wish to express my warm and sincere thanks to Dr. Sameep Mehta, IBM Research Lab, India with whom I had the opportunity to work. His extensive discussions around my work and interesting explorations in operations have been very helpful for my work.
I am also very fortunate and privileged to work with Dr. Aaditeshwar Seth of Department of CSE, IIT Delhi and Dr. Anirban Mahanti, Dr. Sebastien Ardon, Dr.
Sipat Triukose, of NICTA, Australia. I am thankful to them for their valuable feedback, suggestions and help in all respects.
I would like to thank my friend, Amit Ruhela with whom I have spent many sleepless nights for simulation results and meeting the deadlines. I have enjoyed a lot by working with him. Thanks Amit for all the help.
I would also like to thank my colleagues Mona Jain and Rajlakhsmi for their feed- back during our informal discussions and my other colleagues especially Arya, Smruti, Vaibhav, Chinmay, Shibashis, Yamuna, Manoj, Syamantak and Nisha for their cooper- ation and support. I would also like to thank Mr. K. Kaushik for his help.
I am very thankful to IBM Research Lab, Delhi where I had the opportunity of spending one summer as an intern. My sincere thanks to Silicon Institute of Technology, Bhubaneswar for being enablers of my work.
I am really thankful to my wife Runi and son Asu for their understanding and sacri- fices for years. My father Mr. Madan Mohan Tripathy and my mother Mrs. Kumudini Tripathy have shown immense patience and provided me great moral support during the course of my work.
Rudra Mohan Tripathy
Abstract
Today, social networking sites play a vital role in spreading information to a large number of people in quick time. People use social networking sites to spread information about new products or innovation, ideas, rumor, virus etc. Sometimes spreading such information initiates competition, which gives rise to an important area of research calledCompetitive Diffusion. In this dissertation, we have studied competitive diffusion both theoretically by developing stochastic models, and practically, by doing a large scale measurement on an online social network, Twitter.
In the first part of the thesis, we have studied a system where there is competi- tion between two processes: rumor process and anti-rumor process, using stochastic modeling. We have studied different methods for combating rumors in social networks actuated by the realization that authoritarian methods for fighting rumor have largely failed. Our major insight is that, in situations where population do not answer to the same authority, it is the trust that individuals place in their friends that must be lever- aged to fight rumor. In other words, rumor is best combated by something which acts like itself, a message which spreads from one individual to another. We call such mes- sages anti-rumors. We study three natural anti-rumor processes to counter the rumor and present mean field equations that characterize the system.
In some situations, there are more than two processes, which compete among them- selves. For example, different advertising companies spread advertisement for their products at the same time through the social networks. The spread of one product limits the spread of the others. Therefore, in the second part of the thesis, we have studied competitive diffusion where there are more than one topics spread in social networks competing among themselves. To study such systems, we have done a large scale measurement on an online social network, Twitter. For the measurement work, we have engineered a large dataset obtained from Twitter. We faced a lot of challenges to engineer such a huge dataset. One of the key challenges was the topic identification from a small text called ‘tweet’.
We have tried to use Twitter’s own notion of topics in a tweet ,i.e., hashtag, but our observation is that the usage of this feature is noisy and sparse. We therefore propose a technique for tagging tweets that have no hashtag, rationalizing existing hashtags and removing noise. Our method is based on a clustering technique that uses taxonomy
structures developed for Wiki-pedia and word frequency. Unfortunately this technique is not directly usable on large tweets data, mainly due to its complexity. Therefore, we have decided to use a well known web service, OpenCalais for topic identification.
Due to competition among the topics, some topics become popular and some topics popularity was confined to a small geographical area. We performed a rigorous temporal and spatial analysis on both popular and less popular topics. We found that there is a strong impact of the initiators of a topic to make it popular. We deduced that topics become popular when disjoint clusters of users discussing them begin to merge and form one giant component that grows to cover a significant fraction of the network.
Contents
List of Figures vii
List of Tables ix
1 Introduction 1
1.1 Competitive Diffusion. . . 2
1.2 Thesis Overview. . . 5
1.2.1 Modeling aspect of competitive diffusion . . . 5
1.2.2 Measurement aspect of competition diffusion . . . 6
1.3 Contributions of the Thesis . . . 8
2 Related Works 11 2.1 Information Diffusion . . . 11
2.2 Competitive Diffusion. . . 12
2.2.1 Modeling aspect of competitive diffusion . . . 13
2.2.2 Measurement aspect of competitive diffusion . . . 14
2.2.3 Challenges in the measurement study . . . 17
3 Towards Combating Rumors in Social Networks: Models & Metrics 21 3.1 Introduction . . . 21
3.1.1 A note on assumptions . . . 23
3.1.2 Main contributions . . . 23
3.2 Models . . . 25
3.2.1 Rumor spread model . . . 26
3.2.2 Anti-rumor spread models . . . 27
3.3 Metrics . . . 30 iii
iv CONTENTS
3.3.1 Time varying metrics . . . 30
3.3.2 Lifetime metrics . . . 31
3.4 Mean Field Characterization . . . 32
3.4.1 Notation . . . 33
3.4.2 Delayed Start Model . . . 34
3.4.3 Beacon Model . . . 35
3.4.4 Neighborhood Model . . . 35
3.5 Experiments and Analysis . . . 38
3.5.1 Data sets . . . 39
3.5.2 Delayed Start Model . . . 40
3.5.3 Beacon Model . . . 46
3.5.4 Beacon Vs Delayed Start Model . . . 50
3.5.5 Neighborhood Model . . . 52
3.5.6 Observations . . . 58
3.5.7 The Beacon Model versus the Neighborhood Model . . . 59
3.6 Conclusions . . . 60
3.7 Future Work . . . 60
4 Categorization of Hashtags in Twitter 63 4.1 Introduction . . . 63
4.2 Methods . . . 65
4.2.1 Data Representation . . . 65
4.2.2 Mathematical Formulation . . . 69
4.3 Results . . . 70
4.4 Conclusion . . . 76
5 Data Collection Methodology 77 5.1 Tweets & Social graph . . . 77
5.2 Geospatial Data . . . 80
5.3 Topic Identification . . . 82
6 Spatio-Temporal Analysis of Topic Popularity in Twitter 85 6.1 Introduction . . . 85
CONTENTS v
6.2 Topic Selection . . . 87
6.3 The Influence of Initiators . . . 89
6.4 Graph Theoretic Properties of Topics . . . 92
6.4.1 Lifetime Graphs . . . 93
6.4.2 Evolving Graphs . . . 95
6.4.3 Cumulative Evolving Graphs. . . 99
6.5 Geographical Analysis . . . 99
6.6 Concluding Remarks . . . 103
7 Conclusions and Future Work 105
Bibliography 109
