Table of Contents
East China Normal University Scientific Reports v
Preface vii
About the Authors xi
Acknowledgments xv
1 Introduction 1
1.1 Background 1
1.2 Challenges and Basic Ideas 3
1.2.1 Acquisition of social media data from OBGs 3
1.2.2 Incremental learning of probabilistic graphical models 3
1.2.3 Discovering user similarities in social behavioral interactions 5
1.2.4 Associative categorization of frequent patterns in social media 6
1.2.5 Latent link analysis and community detection from social media 6
1.2.6 Probabilistic inferences of latent entity associations 7
1.2.7 Containment of influence spread on social networks 8
1.3 Organization 9
2 Adaptive and Parallel Acquisition of Social Media Data from Online Big Graphs 11
2.1 Motivation and Basic Idea 11
2.2 Related Work 14
2.3 Adaptive Data Collection Based on QMC Sampling 16
2.3.1 Basic idea and algorithm 16
2.3.2 Analysis 19
2.4 Updating Sampling Results by Incremental Maintenance 23
2.4.1 Overview of incremental maintenance 23
2.4.2 Entropy-based data updating 24
2.5 Experimental Results 26
2.5.1 Experiment setup 26
2.5.2 Effectiveness 27
2.5.3 Efficiency 30
2.6 Summary 34
References 36
3 A Bayesian Network-Based Approach for Incremental Learning of Uncertain Knowledge 39
3.1 Motivation and Basic Idea 39
3.1.1 Motivation 39
3.1.2 Ideas and contributions 41
3.2 Related Work 43
3.3 Influence Degree of BN Nodes 46
3.4 Incremental Learning of BNs 50
3.4.1 Markov equivalence and its properties 50
3.4.2 A scoring-based algorithm for BN's incremental learning 54
3.5 Experimental Results 59
3.5.1 Correctness of influence degree 59
3.5.2 Effectiveness of revised BNs 62
3.5.3 Efficiency of incremental learning 63
3.6 Summary 67
References 67
4 Discovering User Similarities in Social Behavioral Interactions Based on Bayesian Network 71
4.1 Motivation and Basic Idea 71
4.2 Related Work 75
4.3 Bayesian Network Based Measurement of User Similarities 78
4.3.1 Definitions and problem statement 78
4.3.2 Constructing user Bayesian network based on MapReduce 80
4.4 Deriving Indirect Similarity by Probabilistic Inferences 84
4.4.1 Graphical structure-based indirect similarities 85
4.4.2 Probabilistic inference-based indirect similarities 87
4.4.3 Combining structure-based and inference-based indirect similarities 89
4.5 Experimental Results 92
4.5.1 Experiment setup 92
4.5.2 Efficiency of UBN construction and inferences 93
4.5.3 Effectiveness of UBN and its inferences 100
4.5.4 Effectiveness of UBN-based user similarity 101
4.6 Summary 104
References 105
5 Associative Categorization of Frequent Patterns in Social Media Based on Markov Network 109
5.1 Motivation and Basic Idea 109
5.2 Constructing Item-Association Markov Network from Behavioral Interactions in Social Media 114
5.3 IAMN-Based Hierarchical Categorization 122
5.4 Experimental Results 127
5.4.1 Experiment setup 127
5.4.2 Efficiency of IAMN construction 128
5.4.3 Effectiveness of IAMN 131
5.4.4 Effectiveness of associative categorization 132
5.5 Empirical Study on Hierarchical Categorization of Microblog Users 135
5.5.1 Basic idea 135
5.5.2 Graph model of microblog users 137
5.5.3 Hierarchical categorization of microblog users 141
5.5.4 Performance studies 144
5.6 Summary 148
References 149
6 Markov Network Based Latent Link Discovery and Community Detection in Social Behavioral Interactions 153
6.1 Motivation and Basic Idea 153
6.2 Related Work 157
6.3 Community Detection from IAMN-based Latent Links 160
6.3.1 Definitions 160
6.3.2 Algorithm for community detection 162
6.3.3 Community combination 165
6.4 Experimental Results 168
6.4.1 Experiment setup 168
6.4.2 Effectiveness 168
6.4.3 Efficiency 175
6.5 Summary 176
References 176
7 Probabilistic Inferences of Latent Entity Associations in Textual Web Contents 179
7.1 Motivation and Basic Idea 179
7.2 Related Work 182
7.3 Definitions and Problem Formalization 183
7.4 Generating Samples of EABN Nodes 184
7.5 Learning an EABN and Ranking EAs 186
7.5.1 BIC metric and division of TWC dataset 186
7.5.2 Scoring-based construction of EABN 190
7.5.3 Ranking EAs by probabilistic inferences of EABN 193
7.6 Experimental Results 195
7.6.1 Experiment setup 195
7.6.2 Effectiveness 196
7.6.3 Efficiency 199
7.7 Summary 201
References 202
8 Containment of Competitive Influence Spread on Social Networks 205
8.1 Motivation and Basic Idea 205
8.2 Related Work 208
8.3 Diffusion-Containment Model 211
8.3.1 Graph model 211
8.3.2 Interaction strategy 212
8.3.3 D-State probability and C-State probability 213
8.3.4 Influence propagation rules 215
8.4 Propagation of Vertex Activation Probabilities 216
8.5 Finding C-Seeds for D-Influence Minimization 219
8.6 Experimental Results 224
8.6.1 Experiment setup 224
8.6.2 Feasibility 225
8.6.3 Functionality and relationship of relevant parameters 230
8.7 Summary 231
References 232
9 Locating Sources in Online Social Networks via Random Walk 235
9.1 Motivation and Basic Idea 235
9.2 Related Work 238
9.3 Influence Propagation Model and Source Location Problem 239
9.3.1 Influence propagation model 239
9.3.2 Source location problem 240
9.4 Bayes Backtracking Model 241
9.5 Random Walk Based Sources Location 244
9.6 Experimental Results 247
9.6.1 Experiment setup 247
9.6.2 Performance studies 248
9.7 Summary 255
References 255
10 Conclusion 259
Index 263
