Mining Social-Driven Data
Abstract
The Web 2.0 revolution spreading over the Internet has dramatically changed the way data is gathered and processed by web applications. The static, authoritarian model of the Web has been abandoned in favor of dynamic, community-driven model of user-generated content. Social networks appear abundantly in all domains of human activity, presenting users with limitless volumes of data, information, and knowledge. Unfortunately, unearthing the knowledge hidden in vast repositories of social applications, such as wikis, Internet forums, or the blogosphere, is a difficult and challenging task. Structural complexity, huge volume of data to be processed, stochastic nature of social processes underlying the data, all contribute to the hardness of this task. Data mining methods developed for relational data repositories cannot be simply adapted to social-driven data. New models and algorithms are required for discovering knowledge in social-driven data. This dissertation introduces a trust-based approach for mining socialdriven data. The author examines different types of social-driven data, including blogs, Internet forums, and online auctions, and utilizes common underlying notions of trust and credibility to develop algorithms for mining social-driven data. Using the notions of trust and credibility allows to discover various important patterns in social-driven data. In the blogosphere, trust manifests itself as the ranking of blogs based on their relative influence on the blogosphere. In the domain of Internet forums, mining the social network of participants unveils true social roles attributed to particular participants. Finally, trust and credibility form the foundation of reputation models for the participants of online auctions. The dissertation presents new models and algorithms for mining socialdriven data. All algorithms have been implemented and their effectiveness has been verified by thorough experiments. The results of the experimental evaluation of models and algorithms allowed to confirm the main thesis of the dissertation, namely, that trust and credibility were the most important and crucial notions used to create relationships in social-driven data. In addition, it has been proven that trust and credibility might be discovered automatically by using data mining methods on the underlying social networks.
Streszczenie
Rewolucja Web 2.0, Której jesteśmy świadkami w ostatnich latach, dramatycznie zmieniła oblicze Internetu oraz zmodyfikowała sposób gromadzenia i przetwarzania danych pozyskiwanych przez
aplikacje internetowe. Statyczny model Internetu ustąpił miejsca koncepcji dynamicznej sieci opartej na społecznościach użytkowników.
Sieci społecznościowe pojawiają się w niemal wszystkich obszarach ludzkiej działalności, dostarczając niewyczerpanych zasobów danych, informacji i wiedzy. Niestety, odkrycie owej wiedzy ukrytej w przepastnych repozytoriach aplikacji społecznościowych, takich jak zbiory wiki, fora internetowe, czy wreszcie blogosfera, jest trudnym zadaniem. Trudność owa wynika przede wszystkim ze złożoności strukturalnej danych wykorzystywanych przez serwisy społecznościowe, z ogromnych rozmiarów danych gromadzonych przez te serwisy, a także ze stochastycznej natury procesów społecznych rządzących formowaniem się sieci społecznych. Metody eksploracji danych opracowane na potrzeby odkrywania wiedzy w tradycyjnych, relacyjnych repozytoriach danych nie mogą być w prosty sposób zaadaptowane na potrzeby eksploracji danych społecznościowych ze względu na istotne różnice w sposobie przetwarzanych danych. Konieczne jest, zatem opracowanie nowych, dedykowanych modeli i algorytmów służących odkrywaniu wiedzy w danych społecznościowych. W niniejszej rozprawie zaprezentowano nowe podejście do problemu eksploracji danych społecznościowych. Autor przeanalizował rożne rodzaje danych społecznościowych, w tym blogosferę, fora internetowe oraz aukcje internetowe, identyfikując w nich wspólny pierwiastek zaufania i wiarygodności. Odkrycie relacji zaufania i wiarygodności, w rożny sposób manifestujących się w danych społecznościowych, umożliwiło opracowanie nowych algorytmów odkrywania wzorców w danych społecznościowych. W dziedzinie eksploracji blogów przejawem zaufania jest ranking blogów oparty na względnym wpływie każdego z nich na pozostałą blogosferę. W dziedzinie forów internetowych eksploracja sieci powiązań między uczestnikami w poszukiwaniu przejawów zaufania umożliwiła odkrycie ról społecznych użytkowników w ramach społeczności forum internetowego. Wreszcie, zaufanie i wiarygodność stanowią fundamenty wszystkich modeli reputacji uczestników aukcji internetowych. W rozprawie zaprezentowano wiele nowych modeli i algorytmów eksploracji danych społecznościowych. Wszystkie przedstawione
algorytmy zostały zaimplementowane, a ich efektywność potwierdzono eksperymentalnie. Wyniki przeprowadzonych eksperymentów pozwoliły autorowi potwierdzić tezę rozprawy, sformułowaną w rozdziale 1, zgodnie, z którą zaufanie i wiarygodność są podstawowymi czynnikami sprzyjającymi tworzeniu się związków w sieciach społecznych. Ponadto przeprowadzone badania dowiodły, że relacje zaufania i wiarygodności mogą być efektywnie odkrywane za pomocą metod eksploracji danych przystosowanych do przetwarzania danych w środowisku sieci społecznych.
Abstract 7
Foreword 9
Preface 11
I. The World of the New 15
1. Web 2.0 Revolution 17
1.1 What is Web 2.0? 17
1.2 New forms of participation — push or pull? 21
1.3 New forms of expression — blogs 22
1.4 New forms of conversation — Internet forums 23
1.5 New forms of trade — online auctions 25
1.6 New forms of data — mobile objects 28
1.7 Introduction to data mining 29
1.8 Main thesis of the dissertation 32
2. Social-Driven Data 35
2.1 Introduction 35
2.2 Data from blogs 39
2.3 Data from Internet forums 44
2.4 Data from online auctions 47
2.5 Social implications of the Web 2.0 revolution 52
II. Mining of the New 57
3. Blogosphere 59
3.1 Introduction 59
3.2 Related Work 61
3.3 Basic Definitions 64
3.4 Trendoo Algorithm 67
3.5 Experiments 74
3.6 Conclusions 79
4. Internet Forums 81
4.1 Crawling Internet forums 81
4.2 Statistical analysis 83
4.2.1 Topic statistics 83
4.2.2 Post statistics 86
4.2.3 User statistics 87
4.3 Index analysis 91
4.4 Network analysis 99
4.4.1 Model of Internet forum sociogram 99
4.4.2 Topic analysis 102
4.4.3 User analysis 104
4.4.4 Role analysis 106
4.5 Conclusions 107
5. Online Auctions 109
5.1 Introduction 109
5.2 Related work 113
5.3 Credibility 115
5.3.1 Basic Definitions 116
5.3.2 CredMine Algorithm 117
5.3.3 Experiments 118
5.3.4 Conclusions 121
5.4 Density 123
5.4.1 Basic Definitions 124
5.4.2 Experiments 126
5.4.3 Conclusions 134
5.5 Implicit feedback 135
5.5.1 Existence of Implicit Feedback 135
5.5.2 Simulation 138
5.5.3 Experiments 142
5.5.4 Conclusions 144
5.6 Positive and Negative Reputation 144
5.6.1 Basic Definitions 145
5.6.2 R+ and R- Algorithms 146
5.6.3 Experiments 148
5.6.4 Conclusions 153
5.7 Summary of online auction mining 154
III. Miscellaneous 155
6. Moving Objects 157
6.1 Introduction 158
6.2 Related Work 159
6.3 Basic Definitions 160
6.4 Algorithms 163
6.4.1 AprioriTraj 163
6.4.2 Traj-PrefixSpan 167
6.5 Experiments 169
6.5.1 AprioriTraj 169
6.5.2 Traj-PrefixSpan 171
6.6 Conclusions 176
7. Negative Patterns 179
7.1 Introduction 180
7.2 Related Work 181
7.3 Basic Definitions 182
7.3.1 Frequent Itemsets and Association Rules 182
7.3.2 Dissociation Itemsets and Dissociation Rules 184
7.4 Algorithms 185
7.5 Experiments 189
7.6 Conclusions 192
8. Summary 195
IV. Appendixes 201
A. Trendoo 203
A.1 Introduction 203
A.2 Architecture 204
A.3 User Guide 207
B. Foruminer 209
B.1 Introduction 209
B.2 Architecture 210
B.3 User Guide 211
C. Presto 215
C.1 Presto Simulator 215
C.2 Presto Web 217
D. Moppy 221
D.1 Introduction 221
D.2 General Idea 223
D.3 Architecture, Features, and User Interface 224
Bibliography 227
Afterword 241
Streszczenie 243
