Vital Node Identification Based On Network Motif Detection

With the continuous development of computer science,research on complex network has attracted more and more attention from researchers.As an essential problem in complex network,vital node identification is an effective method to control a pandemic outbreak like COVID-19,eliminate damage from a network attack,maintain traffic,and so on,which is significate theoretically and practically.Vital node identification problem is evaluating the importance of nodes in complex network by a certain index or algorithm,which eventually come out an importance rank of nodes.Vital node identification has attracted scientists in various fields for decades,and they have accumulated scientific research for a long time,started from microscale and macroscale,and proposed mesoscale,such as motif and community,as a brand new idea on complex network research.This study is based on network motif detection and vital node identification,and identified vital node after explaining multiple interaction in complex system from the perspective of motif.In reality,node always belongs to different network in all kinds of types,and the different networks affect each other.For a better mathematical description of the reality,researchers have not only simply framed them by single layer network,but also depicted them by multilayer network.For descripting the real complex systems in a more accurate way,this dissertation has adopted multiplex network as modeling method.Multiplex networks frame the heterogeneous nature of real systems,where the multiple roles of nodes,both functionally and structurally,are well represented.The main work is shown as follow:(1)This study divided node into multiplex node and layer node based on multiplex network framework,and discuss the roles they play when multiplex network expands into general multilayer network and degenerates to single layer network.(2)Based on the summary of previous studies,this dissertation reviewed the works of pioneers on motif and vital node identification,and started with the cycle structure motif,then introduced the inequivalence of importance between interlayer connection and intralayer connection,minimum flux criterion and Bayes inference,so as to obtain hybrid supra-cycle number and hybrid supra-cycle ratio,which is designed to quantify the importance of node.This study proposed a cycle structure detection algorithm,which can effectively search cycle structure around the network,and comparing with other algorithm related to high order structure our algorithm has ascendency on complexity.(3)Validation was performed through robustness analysis,synchronization analysis and transmission dynamics.This study made comparison between hybrid cycle number,hybrid cycle ratio and six other typical vital node identification methods,and made a conclusion about the good performance of the two indexes this dissertation proposed.Meanwhile,this dissertation proposed a network simplification method based on graph mapping,which is also compared with indexes mentioned before,and experimental result prove that it well performed on complexity and simulation.(4)Aside of Graph mapping simplification,this dissertation proposed two kinds of network reconstruction strategies.This dissertation carried out the confirmative experiment through degree centrality and betweenness centrality as representative indexes in reconstructed networks,and experimental result shows that the two kinds of strategies can effectively simplify the network framework,and verify the reasonability about the inequivalence of importance between interlayer connection,and testify the cycle structures with less girth can better perform network reconstruction task than those with large one.