Robustness-driven Social Network Analysis Based On Graph Modelling

With the popularization of mobile Internet devices,the popularity of social media software and the increasingly abundant massive data processing requests,the research of social networks brings new vigor and vitality again.The scope of modern social networks is ubiquitous,ranging from interpersonal communication networks to biological protein networks and virus transmission networks,etc.As social networks are vulnerable to various device failures and hacking attacks,the investigation of network robustness is important for studying all aspects of social networks.The impact of each component on the overall network cannot be ignored,and the negative impact of partial failure may cause a complete disintegration of the network.At the same time,social networks have powerful self-resilience.In the study of robustness,nodes,communities and even the entire networks provide us with good carriers,which are reflected in two specific aspects of vulnerability and resilience.In this thesis,on the graph constructed by the social network,based on the topological information in the graph,from the micro,meso and macro levels,we undertake robust-driven network analysis and mining.Therefore,this thesis mainly focuses on the topics of node influence analysis and community discovery algorithms as well as the research on the robustness of the community,including the investigation on the vulnerability and resilience of the community.The detailed works of this thesis are as follows.Firstly,in the micro-node analysis of social networks,this thesis focuses on the scheme of influential node detection in terms of robustness.To the best of our knowledge,most of the existing schemes aim at improving the accuracy and efficiency,but ignore the characteristic of network invulnerability.Invulnerability refers to the ability to resist system vulnerability and maintain availability.Based on the node diffusion degree and node cohesion degree,we propose a new strategy for searching influential nodes according to local topology and global location.Applying the global efficiency loss and local efficiency loss,we evaluate the impact of the strategy from the perspective of node resistance to failures.Experimental results in real networks show that our method achieves a good balance between detection accuracy and network invulnerability.The detected influential nodes are the ones that have greater influence and can resist certain damage and interference of the network.Secondly,in the macro network structure mining of social networks,this thesis investigates community detection strategies using robustness.The k-hop decentralized ego network of a node is the reflection of node robustness,which contains rich topological characteristics.Based on topological features such as the k-hop decentralized ego network to find the critical core and bridge nodes,a novel local extension-based overlapping community detection scheme is proposed in this thesis.For seed initialization,instead of the traditional approaches to select the cores of communities as seeds,a new Core-Bridge triplet strategy is suggested to select seeds to generate the initial backbone and framework of the community.In the community optimization stage,a stepwise refinement approach is adopted to solve the issue of unreasonable division and unassigned node allocation.At the same time,a merge index is designed to merge communities reasonably to prevent communities with excessive overlap.Experiments on synthetic benchmark networks and real networks show that the proposed algorithm outperforms some algorithms in stability and effectiveness.Thirdly,meso-communities are prevalent aggregation structures in social networks.For the quantification of community vulnerability,recent works underline that many internal and external parameters to quantify community vulnerability necessarily improve conformity with topology,but are suffering from a shortage of comprehensiveness.In this thesis,we propose a novel metric to characterize topological information by communicability and structural dissimilarity.The number of intra-edges,average communicability,average topological heterogeneity within the community are internal factors,while the number of inter-edges and structural dissimilarity between communities are external factors,which are employed as metrics to improve the comprehensiveness of the fused information.Experiments on real networks verify that the proposed method shows superiority in effectiveness and accuracy.In addition,the SIR model and simulations of random and deliberate attack are utilized to validate rationality.Finally,this thesis suggests the metric scheme to characterize community resilience and network recovery strategies.So far not much effort has focused on the community resilience,and only the scenario of edge interruptions has been taken into account.In this thesis,in terms of both edge and node disruptions,we quantify the similarity between communities by characterizing their "distance",and propose a new method to measure community resilience.In addition,we establish some network performance metric functions,based on four different dimensions,i.e.,fragmentation,reachability,network energy,and partition similarity.We also propose a novel strategy to determine the recovery order of the disrupted elements,which facilitates the recovery of network performance.Experiments on real networks show that the proposed schemes exhibit effectiveness.