Towards Knowledge Discovery In Networks With Incomplete Multi--layer Structure Information

In recent years,with the breakthrough development of network science,artificial intelligence,data mining and knowledge discovery technologies,researchers began to quantitatively analyze complex problems in many natural and social sciences.In these problems,complex networks are widely used to describe complex systems and model practical problems.Among them,the complex network with multi-layer structures plays an extremely important role.Most of the existing researches on multi-layer networks are carried out on the premise of knowing the complete Information of Multi-layer Structures(IoMS).In practice,it is more common that the IoMS of the network is unknown or partially known.Therefore,it is of more general theoretical and practical significance to study multi-layer networks with incomplete IoMS.Among them,detecting Previously Undiscovered Edge Types(PUET)in networks with incomplete IoMS and quantifying the Relative Structural Differences(RSD)between the network without IoMS and the single-layer network are the two most fundamental but unsolved knowledge discovery problems.To solve these problems,this thesis completes the following results:1.Information-Defined Network Model(IDNM)is proposed to formulate the multilayer structures of networks with incomplete IoMS.This model treats networks from a new perspective:information is the fundamental unit of the network to uniformly formulate the components of the network,the relationship between components and physical phenomena.This thesis presents a model for multi-layer structures of networks with incomplete IoMS in terms of information.The fundamental theorem of this model reveals that any directed unweighted network can be treated as an Information-Defined Network(IDN)which is in a 2-Stable Phase(2-SP).2.A network topology property,called the Delta property,is proposed.It is discovered that a 2-SP IDN must obey the Delta property.This new law reveals the relationship between the sub-layer structure of the network and its topology,based on which the two problems can be partially solved.3.A PUET detection technique is proposed based on the Delta property.Both theoretical derivation and experimental analysis show that this method can effectively detect the PUET in IDNs with incomplete IoMS.4.Three types of Relative Interactive Multiplexity(RIM)are proposed based on the Delta property.The RIM is a new family of network features that can measure the RSD between a target network and a single-layer network.In this thesis,the closed-form solution of the RIM is given.It is proved that the RIM can still work normally under the premise of unknown IoMS or no multi-layer structure detection.Additionally,this thesis proves that the RIM can induce network classification algorithms and network recognition algorithms with excellent performance,showing that the proposed RIM has a great potential for wide applications.To sum up,in this thesis,two important unsolved knowledge discovery problems in networks with incomplete IoMS are proposed;to solve these two problems,a new model,i.e.IDNM,is proposed,and a new law,i.e.any 2-SP IDN must obey the Delta property,is discovered;based on the new law,two new technologies are developed to solve the two proposed problems.Additionally,the IDNM provides a new perspective and theoretical basis for the research of many other problems in network science and data analysis,such as link prediction,important node detection,information diffusion patterns,etc.