Structural Analytics And Behaviors Prediction In Complex Networks Based On Evolutionary Algorithms

Many real-world systems can be represented by complex networks,such as social networks,transport systems,power systems,etc.With the development of information technology,it is possible to acquire,store and analyze complex networks.Structure analytics of complex networks can help to understand the functionalities and behaviors of real-world systems.Community structure is one of the most important properties of complex networks.The analysis of community structure can help to understand relationships of communities and is useful for analyzing other properties and functionalities of networks,for example,epidemic spreading prevention and recommender systems.The analysis of structural balance can help to understand friendship and hostile relationships,and predict the dynamics of signed networks.Recommendation is a typical application of network prediction,which provides users with convenience and brings considerable benefits to businesses.This dissertation mainly focuses on structure analytics and behaviors prediction of complex networks,including deep community detection,epidemic spreading prevention,structural balance and multi-objective personalized recommendation.The main idea of this dissertation is to model issues above as optimization problems.The works of this dissertation include:Deep community detection helps to discover important communities and members of networks.Greedy deep community detection algorithms are with good performance while high computational complexity.This dissertation proposes a novel memetic algorithm for deep community detection.Genetic operators and local search are redesigned based on the network-specific knowledge.The proposed memetic algorithm combines global genetic algorithm and local search.The global algorithm finds the local optimal community detection results and the local search discovers the optimal results quickly.The proposed memetic algorithm makes a good balance between effectiveness and efficiency.Biological viruses and rumors seriously affect people’s lives and health,so that preventing the spreading of them is of great necessity.Immunization is one the commonly used strategies in preventing epidemic spreading.The goal of target immunization is to prevent epidemic spreading by immunizing the least number of nodes.In this dissertation,preventing epidemic spreading is modeled as an optimization problem and optimized by an algorithm combining memetic algorithm and community detection.First,the network is divided into several communities by community detection algorithms.Hub nodes play great roles in the epidemic spreading within communities and epidemic spreads from one community to other communities across bridge nodes.Candidate set consists of hub nodes and bridge nodes.A novel memetic algorithm is proposed to select final immunization nodes from the candidate set by optimizing epidemic spreading threshold.The proposed algorithm is with great performance and lower computational complexity.Signed network is a kind of network including edges with the property of positive or negative sign.Structural balance of signed networks focuses on computing imbalance and studying the dynamics of signed networks.This dissertation researches how an imbalanced network evolves to a balanced one with the least cost.In this dissertation,we design a novel energy function to evaluate the transformation cost in the dynamic evolutionary process,and formulate the structural balance transformation as an energy function minimization problem.A novel memetic algorithm is proposed to solve the energy function minimization problem.In the proposed memetic algorithm,two local search procedures are designed.Different transformation costs are got by tuning the transformation cost parameter in the energy function.Recommender systems have been successfully used by most social websites.Accuracyfocused recommendation algorithms tend to recommend similar items to users,while they have very little values for the users.To solve the dilemma of accuracy and diversity,this dissertation models recommendation as a multi-objective optimization problem.Two objective functions are designed to describe the abilities of recommendation algorithm to recommend accurate and diverse items,respectively.A decomposition based multi-objective evolutionary algorithm is used to solve this multi-objective optimization problem.The proposed algorithm could return multiple solutions for decision makers.Users at different locations have different preferences,so that users locations can be used for recommendation.In this dissertation,users locations are also used for generating recommendation.Two objective functions are designed to describe the abilities of recommendation algorithms to recommend similar items and improve recommendation coverage,respectively.The location-based recommendation is formulated as a multi-objective optimization problem and solved by a multi-objective evolutionary algorithm.In the proposed algorithm,all the users are divided into several clusters and recommendation is generated within each cluster based on the collaborative filtering algorithm.The proposed algorithm has superior performance in recommendation and could well alleviate data sparsity and cold start problems.