Study And Applications Of Community Detection Algorithms In Complex Networks

As a ubiquitous feature of complex networks,community characteristic is not very uncommon to be found in real world networks such as social networks,computer networks,and transportation networks.Nodes in a network with community structure are scattered in separated groups,inside which there are relatively dense connections while very few links existing between different groups.It is vital to detect community structure in complex networks and to take advantage of those extracted information.Community detection is a key subject in study of complex networks,it focuses on uncovering the affiliation of each node through topology analysis.Such topic has long been the hotspot in research field,and it is also the core interest of this dissertation.This subject mainly covers the following contents.(1)Inherent topology information in networks with community characteristics is utilized to optimize the evolutionary algorithm based community detection process.Among quite a few intelligent algorithms,evolutionary algorithms,inspired by evolution in biological world,are simply and intuitively global optimization methods.In this work,we propose a differential evolution based community detection algorithm with a specific local aggregation operator that uses the inherent topology information as priori knowledge to adjust the evolutionary process.(2)A modified diffusion kernel based distance is employed herein to optimize the community detection process using support vector machines.As a famous machine learning algorithm,support vector machine is very good at solving nonlinear pattern recognition problems.We define a distance based on the diffusion kernel herein,which leads to the transformation of the target problem,from community detection to a combination of a quadratic problem and a community assignment.Furthermore,the proximity graph and the stable equilibrium point have been deployed to simplify the community assignment process.(3)In this work,we put the cascaded stacked auto-encoders and the unsupervised extreme learning machine together in a two level embedding process and propose a novel community detection algorithm.A low dimensional embedded representation of input data is a byproduct from the hidden layer of an auto encoder trained for data reconstruction.The proposed method benefits from the integration of sparsity restrictions and the circumvention of the time consuming eigenvalue decomposition procedure.As the second level embedding preprocessor,unsupervised extreme learning machine embeds the inherent topology information into the low dimensional representation by means of the manifold regularization,which promotes a more rational low dimensional embedded representation.(4)Routing protocol of wireless sensor networks and recommendation algorithms in recommendation systems are redesigned in combined with community structures.Community detection is possible to play a role in many places of real world applications,we demonstrate this in two scenarios.By establishing a hierarchical routing protocol based on community structure,each node only has to communicate with neighbours in the same group instead of broadcasting messages to everyone in the network,which reduces energy dissipation.In a recommendation system,community detection gives another way to analyze the relevance between users or items.Experiments have demonstrated that the collaborative filtering algorithm based on community structure could result in better recommendations.