User Community Discovery (Human–Computer Interaction Series)

This book redefines community discovery in the new world of Online Social Networks and Web 2.0 applications, through real-world problems and applications in the context of the Web, pointing out the current and future challenges of the field. Particular emphasis is placed on the issues of community representation, efficiency and scalability, detection of communities in hypergraphs, such as multi-mode and multi-relational networks, characterization of social media communities and online privacy aspects of online communities. __User Community Discovery__ is for computer scientists, data scientists, social scientists and complex systems researchers, as well as students within these disciplines, while the connections to real-world problem settings and applications makes the book appealing for engineers and practitioners in the industry, in particular those interested in the highly attractive fields of data science and big data analytics. Preface 6 Contents 7 List of Reviewers 8 Contributors 9 1 Discovery of Complex User Communities 11 1.1 Introduction 12 1.2 Types of Web Community 13 1.3 Representation of Communities 14 1.3.1 Communities as Graphs 14 1.3.2 Community Attributes 16 1.4 Community Detection on Simple Graphs 17 1.5 Communities in the Social Web 19 1.5.1 Definitions of Communities in the Social Web 21 1.5.2 Community Detection on Social Graphs 22 1.6 Applications of Community Detection 24 1.7 Conclusions and Open Issues 26 References 28 2 Community Discovery: Simple and Scalable Approaches 33 2.1 Introduction 33 2.2 Multilevel Approach for Community Discovery 35 2.2.1 Overview 36 2.2.2 Contraction 37 2.2.3 Partitioning 38 2.2.4 Refinement 40 2.2.5 Empirical Results and Summary 42 2.3 Speeding up Community Discovery by Network Sampling 44 2.3.1 Node Sampling for Community Discovery 45 2.3.2 Edge Sampling for Community Discovery 48 2.3.3 Empirical Results and Summary 51 2.4 Exploiting Parallelism and Distributed Architectures in Community Discovery 55 2.4.1 Speeding up and Scaling up Matrix Operation-Based Algorithms 55 2.4.2 Parallelizing Objective Function Optimization-Based Algorithms 57 2.4.3 Summary 60 2.5 Conclusion 60 References 62 3 Community Discovery in Multi-Mode Networks 65 3.1 Motivation 65 3.2 Definitions 68 3.2.1 Multi-Mode Networks 68 3.2.2 Hyperedge and Hypergraph 70 3.3 Problem Formulation 71 3.3.1 Community Detection 71 3.3.2 Multi-Mode Communities 72 3.4 Methods 74 3.4.1 Evolutionary Multi-Mode Clustering 74 3.4.2 Net-Clustering 76 3.4.3 MetaGraph Factorization 78 3.4.4 Discussions 79 3.5 Extensions 82 3.5.1 Community Evolution 82 3.5.2 Link Prediction 82 3.5.3 Ranking 83 3.6 Summary 83 References 84 4 Discovering Communities in Multi-relational Networks 85 4.1 Introduction 86 4.2 Problem Formulation 87 4.3 Generalized Modularity Optimization 88 4.3.1 Laplacian Dynamics Formalism 89 4.3.2 Generalized Laplacian Dynamics 90 4.4 Co-Ranking Frameworks 91 4.4.1 Integration Methods: An Overview 92 4.4.2 MultiRank Algorithm 94 4.4.3 MutuRank Algorithm 94 4.5 Partition Integration 96 4.5.1 Frequent Itemsets Mining Based Method 96 4.5.2 Consensus Clustering Based Method 97 4.6 Experimental Networks 99 4.6.1 Constructing MRN on DBLP Data 100 4.6.2 Constructing MRN on Forum Data 100 4.7 Summary 103 References 103 5 Group Types in Social Media 106 5.1 Bridging Gaps in the Study of Communities 106 5.2 Group Characterization in the Literature 109 5.2.1 Groups in Computer Science 109 5.2.2 Groups in Social Sciences 111 5.3 The Flickr Case-Study 111 5.4 Space and Time Patterns of Groups 113 5.4.1 Spatial Features 113 5.4.2 Temporal Features 115 5.4.3 Spatial and Temporal Groups in Flickr 116 5.5 Social and Topical Groups 120 5.5.1 Common Identity and Common Bond Theory 120 5.5.2 From Theory to Metrics 121 5.5.3 Ground Truth of Social and Topical Flickr Groups 123 5.5.4 Group Type Prediction in Flickr 125 5.6 Towards a Comprehensive View on Group Types 128 5.7 Declared Versus Detected Groups 129 5.8 The Barrier of Membership Size 131 5.9 The Role of Groups in Other Social Phenomena 134 5.10 Are Groups the Missing Link Between Atomic Interactions and Emergent Social Phenomena? 137 References 140 6 Privacy Issues in Discovering Communities in Social Networks 144 6.1 Introduction 144 6.1.1 Community Detection in Social Networks 145 6.1.2 Privacy Threats in Social Communities 146 6.2 Modeling Privacy in Social Networks 149 6.2.1 Graph Representation of Social Networks 149 6.2.2 Definition of Privacy in Social Networks 150 6.3 Privacy Protection in Social Network Data Publishing 152 6.3.1 Adversary's Background Knowledge 153 6.3.2 Privacy Protection Models and Anonymization Techniques 155 6.3.3 Anonymizing Group Participation in Social Networks 158 6.4 Privacy Settings in Online Social Networks 159 6.5 Conclusion 162 References 162 Front Matter....Pages i-xii Discovery of Complex User Communities....Pages 1-22 Community Discovery: Simple and Scalable Approaches....Pages 23-54 Community Discovery in Multi-Mode Networks....Pages 55-74 Discovering Communities in Multi-relational Networks....Pages 75-95 Group Types in Social Media....Pages 97-134 Privacy Issues in Discovering Communities in Social Networks....Pages 135-155