Computational intelligence for network structure analytics

This book presents the latest research advances in complex network structure analytics based on computational intelligence (CI) approaches, particularly evolutionary optimization. Most if not all network issues are actually optimization problems, which are mostly NP-hard and challenge conventional optimization techniques. To effectively and efficiently solve these hard optimization problems, CI based network structure analytics offer significant advantages over conventional network analytics techniques. Meanwhile, using CI techniques may facilitate smart decision making by providing multiple options to choose from, while conventional methods can only offer a decision maker a single suggestion. In addition, CI based network structure analytics can greatly facilitate network modeling and analysis. And employing CI techniques to resolve network issues is likely to inspire other fields of study such as recommender systems, system biology, etc., which will in turn expand CI’s scope and applications. As a comprehensive text, the book covers a range of key topics, including network community discovery, evolutionary optimization, network structure balance analytics, network robustness analytics, community-based personalized recommendation, influence maximization, and biological network alignment. Offering a rich blend of theory and practice, the book is suitable for students, researchers and practitioners interested in network analytics and computational intelligence, both as a textbook and as a reference work. Preface 5 Contents 7 1 Introduction 12 1.1 Network Structure Analytics with Computational Intelligence 12 1.1.1 Concepts of Networks 13 1.1.2 Community Structure and Its Detection in Complex Networks 16 1.1.3 Structure Balance and Its Transformation in Complex Networks 20 1.1.4 Network Robustness and Its Optimization in Complex Networks 23 1.2 Book Structure 25 References 26 2 Network Community Discovery with Evolutionary Single-Objective Optimization 32 2.1 Review of the State of the Art 32 2.2 A Node Learning-Based Memetic Algorithm for Community Discovery in Small-Scale Networks 33 2.2.1 Memetic Algorithm with Node Learning for Community Discovery 34 2.2.2 Problem Formation 35 2.2.3 Representation and Initialization 35 2.2.4 Genetic Operators 36 2.2.5 The Local Search Procedure 37 2.2.6 Experimental Results 38 2.2.7 Conclusions 45 2.3 A Multilevel Learning-Based Memetic Algorithm for Community Discovery in Large-Scale Networks 45 2.3.1 Memetic Algorithm with Multi-level Learning for Community Discovery 46 2.3.2 Representation and Initialization 46 2.3.3 Genetic Operators 46 2.3.4 Multi-level Learning Strategies 48 2.3.5 Complexity Analysis of MLCD 54 2.3.6 Comparisons Between MLCD and Meme-Net 55 2.3.7 Experimental Results 56 2.3.8 Conclusions 63 2.4 A Swarm Learning-Based Optimization Algorithm for Community Discovery in Large-Scale Networks 65 2.4.1 Greedy Particle Swarm Optimization for Network Community Discovery 66 2.4.2 Particle Representation and Initialization 66 2.4.3 Particle-Status-Updating Rules 67 2.4.4 Particle Position Reordering 69 2.4.5 Experimental Results 70 2.4.6 Additional Discussion on GDPSO 76 2.4.7 Conclusions 82 References 82 3 Network Community Discovery with Evolutionary Multi-objective Optimization 0 3.1 Review on the State of the Art 84 3.2 A Decomposition Based Multi-objective Evolutionary Algorithm for Multi-resolution Community Discovery 85 3.2.1 Multi-objective Evolutionary Algorithm for Community Discovery 86 3.2.2 Problem Formation 87 3.2.3 Representation and Initialization 88 3.2.4 Genetic Operators 89 3.2.5 Experimental Results 89 3.2.6 Conclusions 95 3.3 A Multi-objective Immune Algorithm for Multi-resolution Community Discovery 95 3.3.1 Multi-objective Immune Optimization for Multi-resolution Communities Identification 96 3.3.2 Problem Formation 96 3.3.3 Proportional Cloning 97 3.3.4 Analysis of Computational Complexity 99 3.3.5 Experimental Results 99 3.3.6 Conclusions 107 3.4 An Efficient Multi-objective Discrete Particle Swarm Optimization for Multi-resolution Community Discovery 108 3.4.1 Multi-objective Discrete Particle Swarm Optimization for Multi-resolution Community Discovery 108 3.4.2 Problem Formation 109 3.4.3 Definition of Discrete Position and Velocity 110 3.4.4 Discrete Particle Status Updating 110 3.4.5 Particle Swarm Initialization 113 3.4.6 Selection of Leaders 113 3.4.7 Turbulence Operator 114 3.4.8 Complexity Analysis 114 3.4.9 Experimental Results 115 3.4.10 Experimental Results on Signed Networks 127 3.4.11 Conclusions 129 3.5 A Multi-objective Evolutionary Algorithm for Community Discovery in Dynamic Networks 130 3.5.1 Multi-objective Optimization for Community Discovery in Dynamic Networks 130 3.5.2 Problem Formation 131 3.5.3 Proportional Cloning 132 3.5.4 Genetic Operators 133 3.5.5 The Local Search Procedure 133 3.5.6 Solution Selection 135 3.5.7 Experimental Results 136 3.5.8 Conclusions 142 References 144 4 Network Structure Balance Analytics with Evolutionary Optimization 146 4.1 Review on The State of the Art 146 4.2 Computing Global Structural Balance Based on Memetic Algorithm 148 4.2.1 Memetic Algorithm for Computing Global Structural Balance 148 4.2.2 Representation and Initialization 149 4.2.3 Genetic Operators 149 4.2.4 The Local Search Procedure 150 4.2.5 Experimental Results 152 4.2.6 Complexity Analysis 156 4.2.7 Conclusions 157 4.3 Optimizing Dynamical Changes of Structural Balance Based on Memetic Algorithm 157 4.3.1 Problem Formation 157 4.3.2 Representation and Initialization 159 4.3.3 Genetic Operators 160 4.3.4 The Local Search Procedure 160 4.3.5 Transformation 161 4.3.6 Experimental Results 162 4.3.7 Conclusions 168 4.4 Computing and Transforming Structural Balance Based on Memetic Algorithm 169 4.4.1 Optimization Models 170 4.4.2 Memetic Algorithm for the Computation and Transformation of Structural Balance in Signed Networks 172 4.4.3 Experimental Results 180 4.4.4 Conclusions 191 4.5 Computing and Transforming Structural Balance Based on Evolutionary Multi-objective Optimization 192 4.5.1 The Two-Step Algorithm for Network Structural Balance 193 4.5.2 Model Selection 195 4.5.3 Complexity Analysis 197 4.5.4 Experimental Results 197 4.5.5 Conclusions 207 References 208 5 Network Robustness Analytics with Optimization 211 5.1 Review on The State of the Art 211 5.2 Enhancing Community Integrity Against Multilevel Targeted Attacks 212 5.2.1 Model Malicious Attack on the Network as a Two-Level Targeted One 213 5.2.2 Community Robustness of Networks 215 5.2.3 Constraints for Improving Networks 217 5.2.4 Enhancing Community Robustness of Networks 218 5.2.5 Experimental Results 219 5.2.6 Conclusions 227 5.3 Enhancing Robustness of Coupled Networks Under Targeted Recoveries 227 5.3.1 Algorithm for Enhancing Robustness of Coupled Networks Under Targeted Recoveries 228 5.3.2 Experimental Results 233 5.3.3 Conclusions 236 References 237 6 Real-World Cases of Network Structure Analytics 239 6.1 Review on the State of the Art 239 6.2 Community-Based Personalized Recommendation with Evolutionary Multiobjective Optimization 242 6.2.1 MOEA-Based Recommendation Algorithm 242 6.2.2 User Clustering 242 6.2.3 Problem Formation 243 6.2.4 Representation 243 6.2.5 Genetic Operators 244 6.2.6 Experimental Results 245 6.2.7 Conclusions 254 6.3 Influence Maximization in Social Networks with Evolutionary Optimization 254 6.3.1 Memetic Algorithm for Influence Maximization in Social Networks 255 6.3.2 Network Clustering 257 6.3.3 Candidate Selection 257 6.3.4 Seed Generation 258 6.3.5 Experimental Results 263 6.3.6 Conclusions 269 6.4 Global Biological Network Alignment with Evolutionary Optimization 269 6.4.1 Problem Formation 270 6.4.2 Optimization Model for Biological Network Alignment 270 6.4.3 Memetic Algorithm for Network Alignment 271 6.4.4 Representation and Initialization 272 6.4.5 Genetic Operators 274 6.4.6 The Local Search Procedure 274 6.4.7 Experiments Results 276 6.4.8 Conclusions 287 References 287 7 Concluding Remarks 291 7.1 Future Directions and Challenges 291 Front Matter ....Pages i-xi Introduction (Maoguo Gong, Qing Cai, Lijia Ma, Shanfeng Wang, Yu Lei)....Pages 1-20 Network Community Discovery with Evolutionary Single-Objective Optimization (Maoguo Gong, Qing Cai, Lijia Ma, Shanfeng Wang, Yu Lei)....Pages 21-72 Network Community Discovery with Evolutionary Multi-objective Optimization (Maoguo Gong, Qing Cai, Lijia Ma, Shanfeng Wang, Yu Lei)....Pages 73-134 Network Structure Balance Analytics with Evolutionary Optimization (Maoguo Gong, Qing Cai, Lijia Ma, Shanfeng Wang, Yu Lei)....Pages 135-199 Network Robustness Analytics with Optimization (Maoguo Gong, Qing Cai, Lijia Ma, Shanfeng Wang, Yu Lei)....Pages 201-228 Real-World Cases of Network Structure Analytics (Maoguo Gong, Qing Cai, Lijia Ma, Shanfeng Wang, Yu Lei)....Pages 229-280 Concluding Remarks (Maoguo Gong, Qing Cai, Lijia Ma, Shanfeng Wang, Yu Lei)....Pages 281-283