Dynamics On and Of Complex Networks III (eBook)

Preface 6
List of Reviewers (Alphabetically Ordered by Last Names) 9
Contents 10
Part I Network Structure 12
An Empirical Study of the Effect of Noise Modelson Centrality Metrics 13
1 Introduction 14
2 Experimental Setup 15
2.1 Test Suite of Networks 15
2.2 Centrality Metrics 15
2.3 Methodology 16
3 Empirical Results 17
3.1 Edge Addition 17
3.2 Edge Deletion 19
3.3 Edge Swap 21
3.4 Edge XOR 23
3.5 Summary of the Results 25
4 Related Research 29
5 Conclusion and Future Work 30
References 30
Emergence and Evolution of Hierarchical Structurein Complex Systems 32
1 Introduction 33
2 Lexis Background 35
2.1 Lexis-DAG 35
2.2 The Lexis Optimization Problem 37
2.3 Path Centrality and the Core of a Lexis-DAG 38
2.4 Hourglass Score 40
3 Evo-Lexis Framework and Metrics 41
3.1 Incremental Design Algorithm 42
3.2 Target Generation Models 43
3.2.1 MRS Model 46
3.2.2 MS Model 48
3.2.3 M Model 48
3.2.4 RND Model 48
3.3 Key Metrics 49
3.3.1 Cost Metrics 49
3.3.2 Topological Metrics 49
3.3.3 Target Diversity Metric 51
4 Computational Results 51
4.1 Parameter Values and Evolutionary Iteration 51
4.2 Results 52
4.2.1 Emergence of Low-Cost Hierarchies Due to Tinkering/Mutation and Selection 52
4.2.2 Low-Cost Design Resulting in Deeper Hierarchies and Reuse of More Complex Modules 52
4.2.3 The Recombination Mechanism Creates Target Diversity 53
4.2.4 Reuse of Complex Modules in the Core Set by Strong Selection 53
4.2.5 Emergence of Hourglass Architecture Due to the Heavy Reuse of Complex Intermediate Modules in Models with Strong Selection 55
4.2.6 Stability of the Core Set Due to Selection 55
4.2.7 Fragility Caused by Stronger Selection 57
5 Evolvability and the Space of Possible Targets 58
6 Major Transitions 60
7 Overhead of Incremental Design 63
8 Discussion and Prior Work 65
8.1 Modularity and Hierarchy 65
8.2 Hourglass Architecture 66
8.3 Interplay of Design Adaptation and Evolution 67
8.4 From Abstract Modeling to Specific Evolving Systems 68
9 Conclusion 69
References 70
Evaluation of Cascading Infrastructure Failures and Optimal Recovery from a Network Science Perspective 72
1 Introduction 72
2 Risk and Resiliency 73
2.1 Assessing Risk 73
2.2 Gaps in the Risk Literature 74
2.3 Moving Towards Resilience 75
3 Network Science as a Tool 76
4 Case Studies 78
4.1 Studying Resilience Curves 78
4.2 Data 78
4.3 Limitations of the Data 79
4.4 Network Analysis of IEEE Bus Test Case 79
4.5 Network Robustness 81
4.6 Network Recovery 82
4.7 Universal Resilience Curves [15] 83
4.8 Insights and Conclusions 86
References 87
Part II Network Dynamics 89
Automatic Discovery of Families of Network Generative Processes 90
1 Introduction 91
2 Network Morphogenesis 93
2.1 Reconstructing Processes 94
2.1.1 Using Micro-Level Processes 94
2.1.2 Using Macro-Level Structure 95
2.2 Reconstructing Structure 96
2.2.1 Using Processes 96
2.2.2 Using Structure 98
2.3 Combining Both: Evolutionary Models 98
3 Symbolic Regression of Network Generators 99
4 Families of Network Generators 103
4.1 Protocol 104
4.2 A Measure of Generator Dissimilarity 104
4.3 Two-Dimensional Embedding and Families 105
5 Final Remarks 113
References 114
Modeling User Dynamics in Collaboration Websites 119
1 Introduction 120
2 Related Work 122
3 Datasets 123
4 Complex User Behavior in Collaboration Websites 124
5 Activity Decay and Peer Influence 127
6 Negative Activity in Collaboration Websites 131
7 Peer Influence in Temporal Networks 133
8 Conclusions 136
References 137
Interaction Prediction Problems in Link Streams 140
1 Introduction 140
2 Link Stream Modeling of Interactions 141
3 Prediction Problems and Evaluation 142
3.1 Predicting All Interactions 143
3.1.1 Description 143
3.1.2 Quality Evaluation 143
3.2 Predicting the Next Interaction for Each Pair of Nodes 144
3.2.1 Description 144
3.2.2 Quality Evaluation 145
3.3 Predicting the Number of Interactions for Each Pair of Nodes 147
3.3.1 Description 147
3.3.2 Quality Evaluation and Relation to the Link Prediction Problem 147
3.4 Predicting the Existence of Interaction(s) for Each Pair of Nodes 149
4 Pairwise Likeliness Functions for Prediction Tasks 149
4.1 Pairwise Likeliness Functions 150
4.1.1 Illustration 150
4.1.2 Combining Pairwise Likeliness Functions 151
4.2 Combined Pairwise Likeliness Functions for Prediction Tasks 152
4.2.1 Predicting One or Several Link Occurrences 152
4.2.2 Predicting the Number of Interactions Over a Given Period 153
5 Conclusion 154
References 155
The Network Source Location Problem in the Context of Foodborne Disease Outbreaks 156
1 Introduction 157
1.1 Large-Scale Outbreaks of Foodborne Disease 159
2 Background and Definitions 160
2.1 Network-Based Source Identification 160
2.2 Food Supply Networks and Foodborne Disease Transmission 160
3 Distinguishing Features of Foodborne Disease Transmission 161
3.1 A Transport, Not Epidemiological, Transmission Process 161
3.2 Observations are Sparse 162
3.3 Observations will Always be Spaced Far from the Source 163
3.4 Similar Path Lengths 163
3.5 Multiple Candidate Paths 163
3.6 Data on Times Through the Network are Lacking 163
4 Categorization of Literature 164
5 Summary 168
References 169
Part III Theoretical Models and Applications 171
Network Representation Learning Using Local Sharingand Distributed Matrix Factorization (LSDMF) 172
1 Introduction 173
2 Related Work 174
3 Local Sharing and Distributed Matrix Factorization 175
3.1 Execution of Local Sharing Distributed Matrix Factorization (LSDMF) 176
4 Experiments and Results 178
4.1 Simulation 179
5 Application: Link Prediction 182
6 Conclusion and Future Work 183
References 183
The Anatomy of Reddit: An Overview of Academic Research 185
1 Introduction 186
2 The Reddit Dataset 186
3 From the Perspective of Posts 189
4 From the Perspective of Users 195
5 Discussion 201
References 203
Learning Information Dynamics in Online Social Media:A Temporal Point Process Perspective 207
1 Introduction 208
2 Proposed Model 210
2.1 Large Margin Point Process (LMPP) 211
2.1.1 Overview 211
2.1.2 LMPP: Modeling Event-Process Reinforcement and Inter-Process Competitions 212
2.1.3 Popularity Distribution 213
2.1.4 Popularity Ranking in Hashtag Competition 214
2.2 Parameter Estimation 214
2.2.1 Popularity Forecasting 216
2.3 Competing Recurrent Point Process (CRPP) 216
2.3.1 CRPP: Competing Recurrent Point Process 217
2.3.2 Inference 221
3 Experiments 222
3.1 Datasets 222
3.2 Evaluation Protocol 224
3.3 Baselines 226
3.4 Performance Comparison 227
4 Conclusion 236
References 236
Index 239