在线社交网络分析（Online Social Network Analysis）

　　This book focuses on the interaction among three elements of online social networks， i.e. structure， group and information.The structure characteristics and its evolution mechanism， the formation and interaction of group behaviors， and the propagation models and evolution rules of information are discussed in details. This book provides an important theoretical foundation for social network analysis and research on network information dissemination.

　　现任国防科学技术大学计算机学院教授、博士生导师，教育部基础软件工程中心副主任；国家863计划信息技术领域信息安全主题专家组专家，中国网络空间安全协会副理事长，中央网信办咨询专家组专家，中国计算机学会计算机安全专业委员和数据库专业委员会会常务委员。国家社交网络及其信息服务协同创新中心平台首席科学家，国家973项目"社交网络及信息传播”首席科学家助理。主要研究方向：网络空间安全和大数据分析等，作为课题负责人承担和主持了"863计划”重点、国家自然科学基金重点等国家重要课题20余项；获国家科技进步二等奖3项（排名1，2，3），部委级科技进步一等奖7项；发表进入SCI和EI检索的论文200余篇，出版专著5部，获得30余项发明专利和40余项软件著作权授权。

Chapter 1 Introduction 1

1．1 Social Network and Its Development 1

1．1．1 The Origin of Social Network 1

1．1．2 A Glimpse of the Development Procedure of Social Networks From the

Perspective of Sociology 2

1．1．3 A Glimpse of the Development of Social Network From the

Perspective of Anthropology 4

1．2 Development of Online Social Networks 5

1．2．1 Concept of Online Social Networks 5

1．2．2 Features of Online Social Networks 7

1．2．3 Development of Online Social Networks 8

1．2．4 Influences of Online Social Networks on People’s life 9

1．3 Background and Significance of Online Social Network Analysis 11

1．4 Scientific Questions of Online Social Network Analysis 13

1．4．1 Challenges of Online Social Network Analysis 13

1．4．2 Three Scientific Questions and Associated Researches 15

1．5 Organization of This Book 29

References 32

Chapter 2 Social Network Structure Analysis and Modeling 35

2．1 Introduction 35

2．2 Examples 36

2．3 Statistical Characteristics of Social Network 37

2．3．1 Degree Distribution 38

2．3．2 Average Path Length 39

2．3．3 Density 40

2．3．4 Clustering Coefficient 41

2．3．5 Betweenness 42

2．4 Social Networking Characteristics Analysis 43

2．4．1 Small-world Phenomenon 43

2．4．2 Scale-free Characteristic 47

2．4．3 Assortativity 53

2．4．4 Reciprocity 57

2．5 Social Network Structure Modeling and Generation 58

2．5．1 WS Model 59

2．5．2 Extension of WS Model 62

2．5．3 BA Model 63

2．5．4 Extension of BA Model 67

2．5．5 Other Models 70

2．6 Summary 74

References 74

Chapter 3 Technologies and Approaches for Virtual Community Detection 78

3．1 Introduction 78

3．2 Theoretical Basis of Virtual Community Detection Technology 79

3．2．1 The Definition of Virtual Community 79

3．2．2 Development Process of Virtual Community

Detection Algorithms 81

3．2．3 The Accuracy Indexes of Evaluation for Virtual Community

Detection Algorithms 83

3．2．4 The Calculating Complexity of Algorithms for Virtual

Community Detection 88

3．2．5 Typical Data Sets Needed for Testing Virtual Community

Detection Algorithms 89

3．3 Static Calculation Detection Algorithms for Virtual Communities 94

3．3．1 Modularity Optimization Algorithms 95

3．3．2 Multi-objective Optimization Algorithms 98

3．3．3 Algorithms Based on Probability Model 103

3．3．4 Information Coding Algorithms 107

3．4 Dynamic Calculation Detection Algorithms for Virtual Communities 112

3．4．1 Clique Percolation Algorithms 112

3．4．2 Agglomerative Algorithms Based on Similarity 116

3．4．3 Label Propagation Algorithms 120

3．4．4 Local Expansion Optimization Algorithms 125

3．5 Summary 128

References 130

Chapter 4 Evolution Analysis of Virtual Communities 133

4．1 Introduction 133

4．2 Merging of Virtual Communities 134

4．2．1 Period Closure in Merging of Virtual Communities 134

4．2．2 Preference Connection in Merging of Virtual Communities 137

4．2．3 Aging factors in merging of virtual communities 142

4．3 Evolution of Virtual Communities 145

4．3．1 Accumulative Effect in Evolution of Virtual Communities 145

4．3．2 Structural Diversity in Evolution of Virtual Communities 149

4．3．3 Structural Balance in Evolution of Virtual Communities 154

4．4 Detection of Evolving Virtual Communities 156

4．4．1 Detection of Evolving Virtual Community Based on Direct

Similarity Comparison at Adjacent Moments 156

4．4．2 Detection of Evolving Virtual Community Based on Evolution

Clustering Analysis 158

4．4．3 Detection of Evolving Virtual Community Based on Laplacian

Dynamics 159

4．4．4 Detection of Evolving Virtual Community Based on Clique

Percolation Algorithm 161

4．4．5 Detection of Evolving Virtual Community Based on Trend

Analysis on Node Behavior 162

4．5 Summary 163

References 164

Chapter 5 Analysis of User Behavior 167

5．1 Introduction 167

5．2 Online Social Network User Adoption and Loyalty 168

5．2．1 Online Social Network User Adoption 168

5．2．2 Online Social Network User Loyalty 178

5．3 Individual Usage Behavior 189

5．3．1 General Usage Behavior 189

5．3．2 Behavior of Content Generation 195

5．3．3 Behavior of Content Consumption 206

5．4 Group Interaction Behavior 214

5．4．1 Relationship Selection of Group Interaction 214

5．4．2 Content Selection of Group Interaction 220

5．4．3 The Time Law of Group Interaction 222

5．5 Summary 226

References 227

Chapter 6 Social Network Sentiment Analysis 233

6．1 Introduction 233

6．1．1 History of Sentiment Analysis 234

6．1．2 Sentiment Definition and Classification 235

6．1．3 Application of Sentiment Analysis 237

6．2 Sentiment Analysis Techniques 238

6．2．1 Semantic Rule-based Sentiment Analysis 238

6．2．2 Supervised Learning-based Sentiment Analysis 243

6．2．3 Topic Model-based Sentiment Analysis 249

6．3 Social Network Sentiment Analysis Techniques 251

6．3．1 The Sentiment Analysis Technique for Short Text 251

6．3．2 Sentiment Analysis Based on Collective Intelligence 255

6．3．3 Mining Techniques on Spam Opinions in Social Network 258

6．4 Extension and Transformation of Sentiment Analysis Technique 259

6．4．1 Sentiment Summary Technique 259

6．4．2 Sentiment Analysis Technology Based on the Mechanism of

Transfer Learning 261

6．5 Summary 263

References 264

Chapter 7 Introduction Analysis and Its Technologies 267

7．1 Introduction 268

7．2 Influence Strength Calculation 270

7．2．1 Influence Strength Calculation Based on Network Structure 271

7．2．2 Behaviour-based Influence Strength Calculation 272

7．2．3 Topic-based Influence Strength Calculation 274

7．3 Identification of Influentials 277

7．3．1 Individual Influence Calculation Based Network Structure 277

7．3．2 PageRank 282

7．3．3 Individual Influence Calculation Based on Behavior 285

7．3．4 Individual Influence Calculation Based on Topics 289

7．4 Summary 291

References 292

Chapter 8 Collective Aggregation and the Influence Mechanisms 294

8．1 Introduction 295

8．2 Mechanisms Engendering Collective Intelligence 297

8．2．1 Collective Intelligence 297

8．2．2 Self-determination Theory and Collective Intelligence 299

8．2．3 Conditions Engendering Collective Intelligence 301

8．2．4 Factors Influencing Group Intelligence 302

8．2．5 Analytical Models of Collective Intelligence 306

8．2．6 Simulation of Collective Intelligence in Social Networks 313

8．3 Mechanisms Engendering Group Polarization 323

8．3．1 Group Polarization 323

8．3．2 Social Comparison Theory and Group Polarization 325

8．3．3 Conditions Engendering Group Polarization 327

8．3．4 Factors That Influence the Formation of Group Polarization 328

8．3．5 Main Models of Group Polarization Analysis 331

8．3．6 Simulation of Group Polarization in Social Network

Without the Influence of Social Network Structure 342

8．3．7 Simulation of Group Polarization in Social Networks

With the Influence of Social Network Structure 347

8．4 Summary of the Chapter 357

References 359

Chapter 9 Information Retrieval in Social Networks 364

9．1 Introduction 365

9．2 Content Search in Social Network 368

9．2．1 Classical IR and Relevance Feedback Models 369

9．2．2 Query Representation in Microblog Search 379

9．2．3 Document Representation in Microblog Search 385

9．2．4 Microblog Retrieval Models 390

9．3 Content Classification 396

9．3．1 Feature Processing in Short Text Classification 397

9．3．2 Short Text Classification Algorithm 400

9．4 Social Network Recommendation 403

9．4．1 Brief Introduction to Social Recommendation 405

9．4．2 Memory Based Social Recommendation 407

9．4．3 Model Based Social Recommendation 413

9．5 Summary of the Chapter 421

References 422

Chapter 10 Information Retrieval in Social Networks 432

10．1 Introduction 432

10．2 Influencing Factors Related to Information

Diffusion in Social Networks 434

10．2．1 Structure of Social Networks 434

10．2．2 Groups in Social Networks 435

10．2．3 Information 436

10．3 Diffusion Model Based on Network Structure 437

10．3．1 Linear Threshold Model 437

10．3．2 Independent Cascades Model 439

10．3．3 Related Extended Models 441

10．4 Diffusion Model Based on the States of Groups 442

10．4．1 Classical Epidemic Models 443

10．4．2 Infected Diffusion Models in Social Networks 445

10．4．3 Diffusion Models Based on Influence 447

10．5 Diffusion Model Based on Information Characteristics 448

10．5．1 Diffusion Analysis for Multiple Source Information 448

10．5．2 Competitive Diffusion of Information 450

10．6 Popularity Prediction Method 452

10．6．1 Prediction Models Based on Historical Popularity 453

10．6．2 Prediction Models Based on Network Structure 454

10．6．3 Prediction Models Based on User Behaviors 455

10．6．4 Prediction Models Based on Time Series 457

10．7 Information source location 467

10．7．1 Concept of Information Source Location 467

10．7．2 Source Location Methods Based on Centrality 469

10．7．3 Source Location Methods Based on Statistical 

Reasoning Framework 472

10．7．4 Multiple Information Source Location Methods 476

10．8 Summary 480

References 481

Chapter 11 Topic Discovery and Evolution 485

11．1 Introduction 485

11．2 Models and Algorithms of Topic Discovery 487

11．2．1 Topic Model Based Topic Discovery 488

11．2．2 Vector Space Model Based Topic Discovery 502

11．2．3 Term Relationship Graph Based Topic Discovery 507

11．3 Models and Algorithms of Topic Evolution 512

11．3．1 Simple Topic Evolution 513

11．3．2 Topic Model Based Topic Evolution 515

11．3．3 Adjacent Time Slice Association Based Topic Evolution 518

11．4 Summary of the Chapter 519

References 521

Appendix 523

Chapter 12 Algorithms of Influence Maximization 527

12．1 Introduction 527

12．2 Basic Concepts and Theory Basis 528

12．3 Metrics of Influence Maximization 531

12．4 Classification of Influence Maximization Algorithms 533

12．5 Greedy Algorithm of Influence Maximization 533

12．5．1 Basic Concepts of Greedy Algorithm 533

12．5．2 Basic Greedy Algorithm 534

12．5．3 CELF Algorithm 536

12．5．4 Mix Greedy Algorithm 536

12．5．5 Other Greedy Algorithms 538

12．5．6 Summary of Greedy Algorithms 540

12．6 Heuristic Algorithms of Influence Maximization 540

12．6．1 Degree Discount Heuristic 540

12．6．2 PMIA Heuristic 542

12．6．3 LDAG Heuristic 542

12．6．4 Other Heuristics 543

12．6．5 Summary of Heuristic Algorithms 544

12．7 Extension and Deformation of Influence Maximization 544

12．7．1 Extension of Influence Maximization 545

12．7．2 Deformation of Influence Maximization 547

12．8 Chapter Summary 548

References 549