Social Networks with Rich Edge Semantics

by Quan Zheng, David Skillicorn

Overview

Social Networks with Rich Edge Semantics introduces a new mechanism for representing social networks in which pairwise relationships can be drawn from a range of realistic possibilities, including different types of relationships, different strengths in the directions of a pair, positive and negative relationships, and relationships whose intensities change with time. For each possibility, the book shows how to model the social network using spectral embedding. It also shows how to compose the techniques so that multiple edge semantics can be modeled together, and the modeling techniques are then applied to a range of datasets.

Features

• Introduces the reader to difficulties with current social network analysis, and the need for richer representations of relationships among nodes, including accounting for intensity, direction, type, positive/negative, and changing intensities over time





• Presents a novel mechanism to allow social networks with qualitatively different kinds of relationships to be described and analyzed





• Includes extensions to the important technique of spectral embedding, shows that they are mathematically well motivated and proves that their results are appropriate





• Shows how to exploit embeddings to understand structures within social networks, including subgroups, positional significance, link or edge prediction, consistency of role in different contexts, and net flow of properties through a node





• Illustrates the use of the approach for real-world problems for online social networks, criminal and drug smuggling networks, and networks where the nodes are themselves groups

Suitable for researchers and students in social network research, data science, statistical learning, and related areas, this book will help to provide a deeper understanding of real-world'social networks.

Product Details

ISBN-13:	9780367573256
Publisher:	CRC Press
Publication date:	06/30/2020
Series:	Chapman & Hall/CRC Data Mining and Knowledge Discovery Series
Pages:	230
Product dimensions:	6.12(w) x 9.19(h) x (d)

About the Author

David Skillicorn is a professor in the School of Computing at Queen's University. His undergraduate degree is from the University of Sydney and his Ph.D. from the University of Manitoba. He has published extensively in the area of adversarial data analytics, including his recent books "Understanding High-Dimensional Spaces" and "Knowledge Discovery for Counterterrorism and Law Enforcement". He has also been involved in interdisciplinary research on radicalisation, terrorism, and financial fraud. He consults for the intelligence and security arms of government in several countries, and appears frequently in the media to comment on cybersecurity and terrorism.

Dr. Quan Zheng got his Ph.D. is in the School of Computing from Queen’s University in the year 2016.He has a Master’s degree in Applied Mathematics with a specialization in statistics from Indiana University of Pennsylvania, and a Master’s degree in Computer Science from the University of Ulm, and an undergraduate degree from Darmstadt University of Applied Science.

His research interests are in data mining and behavior analysis, particularly social network modeling and graph-based data analysis. He has proposed a few graph algorithms for identifying interested individuals and links, clustering and classification.

Table of Contents

Preface xi

List of Figures xiii

List of Tables xvii

Glossary xix

1 Introduction 1

1.1 What is a social network? 1

1.2 Multiple aspects of relationships 6

1.3 Formally representing social networks 7

2 The core model 9

2.1 Representing networks to understand their structures 9

2.2 Building layered models 11

2.3 Summary 16

3 Background 17

3.1 Graph theory background 17

3.2 Spectral graph theory 18

3.2.1 The unnormalized graph Laplacian 21

3.2.2 The normalized graph Laplacians 23

3.3 Spectral pipeline 24

3.4 Spectral approaches to clustering 24

3.4.1 Undirected spectral clustering algorithms 26

3.4.2 Which Laplacian clustering should be used? 27

3.5 Summary 28

4 Modelling relationships of different types 31

4.1 Typed edge model approach 32

4.2 Typed edge spectral embedding 32

4.3 Applications of typed networks 34

4.4 Summary 37

5 Modelling asymmetric relationships 41

5.1 Conventional directed spectral graph embedding 41

5.2 Directed edge layered approach 44

5.2.1 Validation of the new directed embedding 46

5.2.2 SVD computation for the directed edge model approach 47

5.3 Applications of directed networks 48

5.4 Summary 67

6 Modelling asymmetric relationships with multiple types 69

6.1 Combining directed and typed embeddings 69

6.2 Layered approach and compositions 70

6.3 Applying directed typed embeddings 72

6.3.1 Florentine families 72

6.3.2 Criminal groups 74

6.4 Summary 78

7 Modelling relationships that change over time 81

7.1 Temporal networks 81

7.2 Applications of temporal networks 85

7.2.1 The undirected network over time 85

7.2.2 The directed network over time 89

7.3 Summary 94

8 Modelling positive and negative relationships 97

8.1 Signed Laplacian 97

8.2 Unnormalized spectral Laplacians of signed graphs 98

8.2.1 Rayleigh quotients of signed unnormalized Laplacians 99

8.2.2 Graph cuts of signed unnormalized Laplacians 100

8.3 Normalized spectral Laplacians of signed graphs 102

8.3.1 Rayleigh quotients of signed random-walk Laplacians 102

8.3.2 Graph cuts of signed random-walk Laplacians 104

8.4 Applications of signed networks 105

8.5 Summary 118

9 Signed graph-based semi-supervised learning 121

9.1 Approach 122

9.2 Problems of imbalance in graph data 127

9.3 Summary 137

10 Combining directed and signed embeddings 139

10.1 Composition of directed and signed layer models 139

10.2 Application to signed directed networks 142

10.2.1 North and West Africa conflict 143

10.3 Extensions to other compositions 152

10.4 Summary 155

11 Summary 157

Appendices 161

A RatioCut consistency with two versions of each node 163

B NCut consistency with multiple versions of each node 167

C Signed unnormalized clustering 175

D Signed normalized Laplacian L_sns clustering 177

E Signed normalized Laplacian L_bns clustering 181

F Example MATLAB functions 183

Bibliography 199

Index 209