The Expansion Of Structural Feature Space Based On Subgraph Networks And Its Application

Real-world networks exhibit prominent hierarchies and modular structures,with various subgraphs as building blocks.Most existing researches usually extract different subgraphs as motifs,and simply use the frequency of their appearance in the network to describe the underlying network.Although these statistics can be used to describe a network model or even to design some network algorithms,they are not enough to play the key role of subgraphs.We can further explore the role of subgraphs in these applications to improve research result.This thesis makes a more in-depth study on the scalability of subgraphs in network analysis,and proposes some subgraph-based network models and the related algorithms in network analysis applications,described as follows:(1)A novel subgraph network model is proposed.Existing networks are mainly constructed using entities as nodes and specific relationships between entities as edges.The network under this basic construction rule is a basic,low-level network structure,and its corresponding network analysis tasks can only be carried out from a node-level perspective.A subgraph is a collection of some nodes and the edges between them in the network.It is also the basic building block of a complex network and can be considered as a functional module in a specific network(such as the benzene ring structure in a compound network),which is of great significance to understand and analyze the network structure.In this paper,we propose a new network mapping model,the Sub Graph Networks(SGN)model.This model focuses on the connection patterns between subgraphs in the network.As the model is gradually mapped to higher orders,we can peek at the topology of the entire network at the graph-level.These high-order SGNs make it easier to discover many hidden structural features in the original network by showing the interactions between the subgraphs explicitly.(2)Graph classification based on the subgraph network feature space expansion.Benefiting from the advantages of SGNs for structural feature space expansion of different feature extraction algorithms,we use SGNs to build graph classification models.The existing research on graph classification using subgraphs mainly reveals the structural differences between different networks from a single subgraph-level(such as simply using the frequency of different subgraphs as a feature to characterize the network)and ignore the interaction between subgraphs in the network structure.In this paper,we use the above-mentioned SGN model,which takes advantage of its ability to capture more structural information in the network at the graph-level,and applies it to graph classification tasks on multiple data sets.It is verified that the model can enhance the good performance of different graph classification algorithms.(3)Feature space expansion based on sampling subgraph network.Aiming at the disadvantages of the high computational complexity of SGNs and the easy introduction of network "noise",we propose a variant algorithm of SGNs,sampling SGNs.The algorithm uses a sampling strategy to control the scale of the SGN construction,thereby reducing network noise and algorithm complexity.Benefiting from the sampling strategy,the algorithm framework is not limited to graph classification applications,but can also be extended to more microscopic node classification tasks.In this thesis,we use the sampling SGN as feature space expansion to perform experimental verification in graph classification and node classification tasks,respectively.We find that the sampling SGN can achieve or even surpass the optimal results of the original SGN algorithm and improve the model classification stability.