Search

Abstract Hypergraph Neural Networks (HGNNs) have been significantly successful in higher-order tasks. However, recent study have shown that they are also vulnerable to adversarial attacks like Graph Neural Networks. Attackers fool HGNNs by modifying node links in hypergraphs. Existing adversarial attacks on HGNNs only consider feasibility in the targeted attack, and there is no discussion on the untargeted attack with higher practicality. To close this gap, we propose a derivative graph-based hypergraph attack, namely DGHSA, which focuses on reducing the global performance of HGNNs. Specifically, DGHSA consists of two models: candidate set generation and evaluation. The gradients of the incidence matrix are obtained by training HGNNs, and then the candidate set is obtained by modifying the hypergraph structure with the gradient rules. In the candidate set evaluation module, DGHSA uses the derivative graph metric to assess the impact of attacks on the similarity of candidate hypergraphs, and finally selects the candidate hypergraph with the worst node similarity as the optimal perturbation hypergraph. We have conducted extensive experiments on four commonly used datasets, and the results show that DGHSA can significantly degrade the performance of HGNNs on node classification tasks.

Abstract Graph neural networks (GNNs) have shown powerful capabilities in modeling and representing graph structural data across various graph learning tasks as an emerging deep learning approach. However, most existing GNNs focus on single-relational graphs and fail to fully utilize the rich and diverse relational information present in real-world graph data. In addition, deeper GNNs tend to suffer from overfitting and oversmoothing issues, leading to degraded model performance. To deeply excavate the multi-relational features in graph data and strengthen the modeling and representation abilities of GNNs, this paper proposes a multi-channel deep graph convolutional neural network method called DeepMCGCN. It constructs multiple relational subgraphs and adopts multiple GCN channels to learn the characteristics of different relational subgraphs separately. Cross-channel connections are utilized to obtain interactions between different relational subgraphs, which can learn node embeddings richer and more discriminative than single-channel GNNs. Meanwhile, it alleviates overfitting issues of deep models by optimizing convolution functions and adding residual connections between and within channels. The DeepMCGCN method is evaluated on three real-world datasets, and the experimental results show that its node classification performance outperforms that of single-channel GCN and other benchmark models, which improves the modeling and representation capabilities of the model.

It is well known that networks are dynamic graphs, and the topology of a network can be described by a graph. Thus, the reliability of a network under edge failure is defined as the probability that its corresponding topological graph remains connected under the condition that the edges fail with independent probabilities. In this paper, the reliability of a class of two-layer networks is considered, where each layer is a complete graph and the edges joining different layers are one-to-one correspondingly connected. The edge failure probability is uniform in the same layer and distinct in different layers and between layers. The recursive formula for the reliability (reliability polynomial) of the two-layer network is obtained, and the corresponding algorithm is also given. Furthermore, the reliability of several networks is computed by Python, which verifies the correctness of the algorithm.

Graph Neural Networks (GNNs) have demonstrated significant potential as powerful tools for handling graph data in various fields. However, traditional GNNs often encounter limitations in information capture and generalization when dealing with complex and high-order graph structures. Concurrently, the sparse labeling phenomenon in graph data poses challenges in practical applications. To address these issues, we propose a novel graph contrastive learning method, TP-GCL, based on a tensor perspective. The objective is to overcome the limitations of traditional GNNs in modeling complex structures and addressing the issue of sparse labels. Firstly, we transform ordinary graphs into hypergraphs through clique expansion and employ high-order adjacency tensors to represent hypergraphs, aiming to comprehensively capture their complex structural information. Secondly, we introduce a contrastive learning framework, using the original graph as the anchor, to further explore the differences and similarities between the anchor graph and the tensorized hypergraph. This process effectively extracts crucial structural features from graph data. Experimental results demonstrate that TP-GCL achieves significant performance improvements compared to baseline methods across multiple public datasets, particularly showcasing enhanced generalization capabilities and effectiveness in handling complex graph structures and sparse labeled data.

Abstract Link prediction is a widely adopted method for extracting valuable data insights from graphs, primarily aimed at predicting interactions between two nodes. However, there are not only pairwise interactions but also multivariate interactions in real life. For example, reactions between multiple proteins, multiple compounds, and multiple metabolites cannot be mined effectively using link prediction. A hypergraph is a higher-order network composed of nodes and hyperedges, where hyperedges can be composed of multiple nodes, and can be used to depict multivariate interactions. The interactions between multiple nodes can be predicted by hyperlink prediction methods. Since hyperlink prediction requires predicting the interactions between multiple nodes, it makes the study of hyperlink prediction much more complicated than that of other complex networks, thus resulting in relatively limited attention being devoted to this field. The existing hyperlink prediction can only predict potential hyperlinks in uniform hypergraphs, or need to predict hyperlinks based on the candidate hyperlink sets, or only study hyperlink prediction for undirected hypergraphs. Therefore, a hyperlink prediction framework for predicting multivariate interactions based on graph representation learning is proposed to solve the above problems, and then the framework is extended to directed hyperlink prediction (e.g., directed metabolic reaction networks). Furthermore, any size of hyperedges can be predicted by the proposed hyperlink prediction algorithm framework, whose performance is not affected by the number of nodes or the number of hyperedges. Finally, the proposed framework is applied to both the biological metabolic reaction network and the organic chemical reaction network, and experimental analysis has demonstrated that the hyperlinks can be predicted efficiently by the proposed hyperlink prediction framework with relatively low time complexity, and the prediction performance has been improved by up to 40% compared with the baselines.

Abstract In recent years, Graph Neural Networks (GNNs) have achieved excellent applications in classification or prediction tasks. Recent studies have demonstrated that GNNs are vulnerable to adversarial attacks. Graph Modification Attack (GMA) and Graph Injection Attack (GIA) are commonly attack strategies. Most graph adversarial attack methods are based on GMA, which has a clear drawback: the attacker needs high privileges to modify the original graph, making it difficult to execute in practice. GIA can perform attacks without modifying the original graph. However, many GIA models fail to take care of attack invisibility, i.e., fake nodes can be easily distinguished from the original nodes. To solve the above issue, we propose an imperceptible graph injection attack, named IMGIA. Specifically, IMGIA uses the normal distribution sampling and mask learning to generate fake node features and links respectively, and then uses the homophily unnoticeability constraint to improve the camouflage of the attack. Our extensive experiments on three benchmark datasets demonstrate that IMGIA performs better than the existing state-of-the-art GIA methods. As an example, IMGIA shows an improvement in performance with an average increase in effectiveness of 2%.

The dual-channel graph convolutional neural networks based on hybrid features jointly model the different features of networks, so that the features can learn each other and improve the performance of various subsequent machine learning tasks. However, current dual-channel graph convolutional neural networks are limited by the number of convolution layers, which hinders the performance improvement of the models. Graph convolutional neural networks superimpose multi-layer graph convolution operations, which would occur in smoothing phenomena, resulting in performance decreasing as the increasing number of graph convolutional layers. Inspired by the success of residual connections on convolutional neural networks, this paper applies residual connections to dual-channel graph convolutional neural networks, and increases the depth of dual-channel graph convolutional neural networks. Thus, a dual-channel deep graph convolutional neural network (D2GCN) is proposed, which can effectively avoid over-smoothing and improve model performance. D2GCN is verified on CiteSeer, DBLP, and SDBLP datasets, the results show that D2GCN performs better than the comparison algorithms used in node classification tasks.

Existing graph contrastive learning methods often rely on differences in node features within subgraphs, lacking effective capture of the global structural information of the graph. To address this issue, we propose a novel graph contrastive learning method, Line Graph Contrastive Learning (LineGCL), aimed at overcoming the deficiencies in understanding the overall characteristics and topological structures of graphs found in current methods. LineGCL utilizes the characteristics of line graphs to transform the original graph into corresponding line graphs, presenting edge information in the form of node features, effectively capturing the global structural information of the graph. Additionally, LineGCL adopts a novel multi-view contrastive learning approach, characterizing the similarity and differences between the original graph and line graph comprehensively from the perspectives of node features and spectral features, further enhancing the model's understanding and learning capabilities of the global structure of graphs. Experimental results on public datasets demonstrate that LineGCL outperforms baseline models, achieving performance improvements ranging from 0.5% to 28.5%. These results validate the effectiveness and superiority of LineGCL in capturing and understanding global structural information, surpassing the limitations of baseline methods in graph contrastive learning.

The existing network representation learning algorithms mainly model the relationship between network nodes based on the structural features of the network, or use text features, hierarchical features and other external attributes to realize the network joint representation learning. Capturing global features of the network allows the obtained node vectors to retain more comprehensive feature information during training, thereby enhancing the quality of embeddings. In order to preserve the global structural features of the network in the training results, we employed a multi-channel learning approach to perform high-order feature modeling on the network. We proposed a novel algorithm for multi-channel high-order network representation learning, referred to as the Multi-Channel High-Order Network Representation (MHNR) algorithm. This algorithm initially constructs high-order network features from the original network structure, thereby transforming the single-channel network representation learning process into a multi-channel high-order network representation learning process. Then, for each single-channel network representation learning process, the novel graph assimilation mechanism is introduced in the algorithm, so as to realize the high-order network structure modeling mechanism in the single-channel network representation learning. Finally, the algorithm integrates the multi-channel and single-channel mechanism of high-order network structure joint modeling, realizing the efficient use of network structure features and sufficient modeling. Experimental results show that the node classification performance of the proposed MHNR algorithm reaches a good order on Citeseer, Cora, and DBLP data, and its node classification performance is better than that of the comparison algorithm used in this paper. In addition, when the vector length is optimized, the average classification accuracy of nodes of the proposed algorithm is up to 12.24% higher than that of the DeepWalk algorithm. Therefore, the node classification performance of the proposed algorithm can reach the current optimal order only based on the structural features of the network under the condition of no external feature supplementary modeling.

This paper proposes a computational method for the reliability of 2-separable networks. Based on graph theory and probability theory, this method simplifies the calculation process by constructing a network equivalent model and designing corresponding algorithms to achieve the efficient evaluation of reliability. Considering independent random failures of edges with equal probability q, this method can accurately calculate the reliability of 2-separable networks, and its effectiveness and accuracy are verified through examples. In addition, to demonstrate the generality of our method, we have also applied it to other 2-separable networks with fractal structures and proposed linear algorithms for calculating their all-terminal reliability.

Because many existing algorithms are mainly trained based on the structural features of the networks, the results are more inclined to the structural commonality of the networks. These algorithms ignore the rich external information and node attributes (such as node text content, community and labels, etc.) that have important implications for network data analysis tasks. Existing network embedding algorithms considering text features usually regard the co-occurrence words in the node’s text, or use an induced matrix completion algorithm to factorize the text feature matrix or the network structure feature matrix. Although this kind of algorithm can greatly improve the network embedding performance, they ignore the contribution rate of different co-occurrence words in the node’s text. This article proposes a network embedding learning algorithm combining network structure and co-occurrence word features, also incorporating an attention mechanism to model the weight information of the co-occurrence words in the model. This mechanism filters out unimportant words and focuses on important words for learning and training tasks, fully considering the impact of the different co-occurrence words to the model. The proposed network representation algorithm is tested on three open datasets, and the experimental results demonstrate its strong advantages in node classification, visualization analysis, and case analysis tasks.

The emergence of deep learning has not only brought great changes in the field of image recognition, but also achieved excellent node classification performance in graph neural networks. However, the existing graph neural network framework often uses methods based on spatial domain or spectral domain to capture network structure features. This process captures the local structural characteristics of graph data, and the convolution process has a large amount of calculation. It is necessary to use multi-channel or deep neural network structure to achieve the goal of modeling the high-order structural characteristics of the network. Therefore, this paper proposes a linear graph neural network framework [Linear Graph Neural Network (LGNN)] with superior performance. The model first preprocesses the input graph, and uses symmetric normalization and feature normalization to remove deviations in the structure and features. Then, by designing a high-order adjacency matrix propagation mechanism, LGNN enables nodes to iteratively aggregate and learn the feature information of high-order neighbors. After obtaining the node representation of the network structure, LGNN uses a simple linear mapping to maintain computational efficiency and obtain the final node representation. The experimental results show that the performance of the LGNN algorithm in some tasks is slightly worse than that of the existing mainstream graph neural network algorithms, but it shows or exceeds the machine learning performance of the existing algorithms in most graph neural network performance evaluation tasks, especially on sparse networks.

Abstract Currently, most researchers only utilize the network information or node characteristics to calculate the connection probability between unconnected node pairs. Therefore, we attempt to project the problem of connection probability between unconnected pairs into the physical space calculating it. Firstly, the definition of gravitation is introduced in this paper, and the concept of gravitation is used to measure the strength of the relationship between nodes in complex networks. It is generally known that the gravitational value is related to the mass of objects and the distance between objects. In complex networks, the interrelationship between nodes is related to the characteristics, degree, betweenness, and importance of the nodes themselves, as well as the distance between nodes, which is very similar to the gravitational relationship between objects. Therefore, the importance of nodes is used to measure the mass property in the universal gravitational equation and the similarity between nodes is used to measure the distance property in the universal gravitational equation, and then a complex network model is constructed from physical space. Secondly, the direct and indirect gravitational values between nodes are considered, and a novel link prediction framework based on the gravitational field, abbreviated as LPFGF, is proposed, as well as the node similarity framework equation. Then, the framework is extended to various link prediction algorithms such as Common Neighbors (CN), Adamic-Adar (AA), Preferential Attachment (PA), and Local Random Walk (LRW), resulting in the proposed link prediction algorithms LPFGF-CN, LPFGF-AA, LPFGF-PA, LPFGF-LRW, and so on. Finally, four real datasets are used to compare prediction performance, and the results demonstrate that the proposed algorithmic framework can successfully improve the prediction performance of other link prediction algorithms, with a maximum improvement of 15%.

The scattering number of a graph G is defined as s(G)=max{ω(G−X)−|X|:X⊂V(G),ω(G−X)>1}, where X is a cut set of G, and ω(G−X) denotes the number of components in G−X, which can be used to measure the vulnerability of network G. In this paper, we generalize this parameter to a hypergraph to measure the vulnerability of uniform hypergraph networks. Firstly, some bounds on the scattering number are given. Secondly, the relations of scattering number between a complete k-uniform hypergraph and complete bipartite k-uniform hypergraph are discussed.

With the development of the Internet, there has been a significant increase in various types of textual information. However, when people engage in the composition of formal texts, they often incorporate their colloquial habits, which can diminish the professionalism and formality of the text. Existing research on Chinese texts primarily focuses on correcting misspelt characters that are visually or phonetically similar, as well as obvious grammatical errors, such as redundancy, omissions, and incorrect word order. However, there is limited research addressing the correction of text that exhibits colloquial expressions without apparent grammatical errors or misspelt characters. This article proposes a novel technique that utilizes deep learning methods to directly transform colloquial textual expressions into formal written expressions. Firstly, a parallel corpus dataset of written and spoken language is constructed using a back-translation strategy. Then, an end-to-end learning mechanism based on neural machine translation is employed, with colloquial text as the source language and written text as the target language. This allows the model to directly transform the colloquial text into text with a formal style. Finally, an evaluation of the proposed approach is conducted using the bilingual evaluation understudy (BLEU) and manual assessment techniques. The experimental results demonstrate that the technology proposed in this paper performs well in the task of de-colloquialization in Chinese texts. The contribution of this paper lies in proposing an automated method for collecting a substitute for manually annotated parallel corpora of spoken and written language, which significantly saves time and reduces the manual cost of constructing the dataset. Furthermore, the application of end-to-end learning techniques from neural machine translation to the task of de-colloquialization allows the trained model to directly generate written language flexibly based on the input of spoken language. This presents a novel solution for the task of the de-colloquialization of Chinese text.

A network structure with n vertices and m edges is practically represented by a graph with n vertices and m edges. The graph with k fixed target vertices is called a k-terminal graph. This article studies the locally most reliable simple sparse three-terminal graphs, in which each edge survives independently with probability p. For p close to 0 or 1, the locally most reliable three-terminal graphs with n vertices and m edges are determined, where n≥5 and 9≤m≤4n−10. Finally, we prove that there is no uniformly most reliable three-terminal graph for n≥5, 11

Vulnerability refers to the ability of a network to continue functioning when part of the network is either naturally damaged or targeted for attack. In this paper, the rupture degree of graphs is employed to measure the vulnerability of uniform linear hypergraphs. First, we discuss the bounds of the rupture degrees of k-uniform linear hypergraphs. Then, we give a recursive algorithm for computing the rupture degree of k-uniform hypertrees.

Most network representation learning approaches only consider the pairwise relationships between the nodes in ordinary networks but do not consider the tuple relationships, namely the hyperedges, among the nodes in the hypernetworks. Therefore, to solve the above issue, a hypernetwork representation learning approach based on hyperedge modeling, abbreviated as HRHM, is proposed, which fully considers the hyperedges to obtain ideal node representation vectors that are applied to downstream machine learning tasks such as node classification, link prediction, community detection, and so on. Experimental results on the hypernetwork datasets show that with regard to the node classification task, the mean node classification accuracy of HRHM approach goes beyond other best baseline approach by about 1% on the MovieLens and wordnet, and with regard to the link prediction task, except for HPHG approach, the mean AUC value of HRHM approach surpasses that of other baseline approaches by about 17%, 18%, and 6%, respectively, on the GPS, drug, and wordnet. The mean AUC value of HRHM approach is very close to that of other best baseline approach on the MovieLens.

Network representation learning plays an important role in the field of network data mining. By embedding network structures and other features into the representation vector space of low dimensions, network representation learning algorithms can provide high-quality feature input for subsequent tasks, such as network link prediction, network vertex classification, and network visualization. The existing network representation learning algorithms can be trained based on the structural features, vertex texts, vertex tags, community information, etc. However, there exists a lack of algorithm of using the future evolution results of the networks to guide the network representation learning. Therefore, this paper aims at modeling the future network evolution results of the networks based on the link prediction algorithm, introducing the future link probabilities between vertices without edges into the network representation learning tasks. In order to make the network representation vectors contain more feature factors, the text features of the vertices are also embedded into the network representation vectors. Based on the above two optimization approaches, we propose a novel network representation learning algorithm, Network Representation learning algorithm based on the joint optimization of Three Features (TFNR). Based on Inductive Matrix Completion (IMC), TFNR algorithm introduces the future probabilities between vertices without edges and text features into the procedure of modeling network structures, which can avoid the problem of the network structure sparse. Experimental results show that the proposed TFNR algorithm performs well in network vertex classification and visualization tasks on three real citation network datasets.

Different from conventional networks with only pairwise relationships among the nodes, there are also complex tuple relationships, namely the hyperedges among the nodes in the hypernetwork. However, most of the existing network representation learning methods cannot effectively capture the complex tuple relationships. Therefore, in order to resolve the above challenge, this paper proposes a hypernetwork representation learning method with common constraints of the set and translation, abbreviated as HRST, which incorporates both the hyperedge set associated with the nodes and the hyperedge regarded as the interaction relation among the nodes through the translation mechanism into the process of hypernetwork representation learning to obtain node representation vectors rich in the hypernetwork topology structure and hyperedge information. Experimental results on four hypernetwork datasets demonstrate that, for the node classification task, our method outperforms the other best baseline methods by about 1%. As for the link prediction task, our method is almost entirely superior to other baseline methods.

Let G be a graph with n vertices, let A(G) be an adjacency matrix of G and let PA(G,λ) be the characteristic polynomial of A(G). The adjacency spectrum of G consists of eigenvalues of A(G). A graph G is said to be determined by its adjacency spectrum (DS for short) if other graphs with the same adjacency spectrum as G are isomorphic to G. In this paper, we investigate the spectral characterization of unicycle graphs with only two vertices of degree three. We use G21(s1,s2) to denote the graph obtained from Q(s1,s2) by identifying its pendant vertex and the vertex of degree two of P3, where Q(s1,s2) is the graph obtained by identifying a vertex of Cs1 and a pendant vertex of Ps2. We use G31(t1,t2) to denote the graph obtained from circle with the vertices v0v1⋯vt1+t2+1 by adding one pendant edge at vertices v0 and vt1+1, respectively. It is shown that G21(s1,s2) (s1≠4,6, s1≥3, s2≥3) and G31(t1,t2) (t1+t2≠2, t2≥t1≥1) are determined by their adjacency spectrum.

In this paper, we give a method to characterize graphs determined by their adjacency spectrum. At first, we give two parameters Π1(G) and Π2(G), which are related to coefficients of the characteristic polynomial of graph G. All connected graphs with Π1(G)∈{1,0,−1,−2,−3} and Π2(G)∈{0,−1,−2,−3} are characterized. Some interesting properties of Π1(G) and Π2(G) are also given. We then find the necessary and sufficient conditions for two classes of graphs to be determined by their adjacency spectrum.

Entropy is an important index for describing the structure, function, and evolution of network. The existing research on entropy is primarily applied to undirected networks. Compared with an undirected network, a directed network involves a special asymmetric transfer. The research on the entropy of directed networks is very significant to effectively quantify the structural information of the whole network. Typical complex network models include nearest-neighbour coupling network, small-world network, scale-free network, and random network. These network models are abstracted as undirected graphs without considering the direction of node connection. For complex networks, modeling through the direction of network nodes is extremely challenging. In this paper, based on these typical models of complex network, a directed network model considering node connection in-direction is proposed, and the eigenvalue entropies of three matrices in the directed network is defined and studied, where the three matrices are adjacency matrix, in-degree Laplacian matrix and in-degree signless Laplacian matrix. The eigenvalue-based entropies of three matrices are calculated in directed nearest-neighbor coupling, directed small world, directed scale-free and directed random networks. Through the simulation experiment on the real directed network, the result shows that the eigenvalue entropy of the real directed network is between the eigenvalue entropy of directed scale-free network and directed small-world network.

For a given network, the number of spanning trees is a key parameter to measure its reliability in edge failure cases, while the number of subtrees is a key parameter to measure its reliability in both vertex and edge failures cases. Zhang et al. investigated the entropy of spanning trees, spanning forests and connected spanning subgraphs of Koch networks. In this paper, we extend Koch networks to 3–cactus networks, and study the entropy of subtrees of 3–cactus networks. We present a linear algorithm to count the number of subtrees in a 3–cactus network, determine the upper and lower bounds of the entropy of subtrees of these networks and characterize those attaining the extremal values. As an application, a linear algorithm is developed to count the number of subtrees in Koch networks, with complexity O(g), where g is the number of iterations. Finally, we determine the entropy of subtrees of Koch networks.

There are lots of situations that cannot be described by traditional networks but can be described perfectly by the hypernetwork in the real world. Different from the traditional network, the hypernetwork structure is more complex and poses a great challenge to existing network representation learning methods. Therefore, in order to overcome the challenge of the hypernetwork structure faced by network representation learning, this paper proposes a hypernetwork representation learning method with the set constraint abbreviated as HRSC, which incorporates the hyperedge set associated with the nodes into the process of hypernetwork representation learning to obtain node representation vectors including the hypernetwork topology structure and hyperedge information. Our proposed method is extensively evaluated by the machine learning tasks on four hypernetwork datasets. Experimental results demonstrate that HRSC outperforms other best baseline methods by about 1% on the MovieLens and wordnet datasets in terms of node classification, and outperforms the other best baseline methods, respectively, on average by about 29.03%, 1.94%, 26.27% and 6.24% on the GPS, MovieLens, drug, and wordnet datasets in terms of link prediction.

In this work, the local optimality of mixed reliability of networks is surveyed. A reliability comparison criterion related with subgraphs to measure the local optimality of the mixed reliability of networks is established. Using the comparison criterion, we characterize all locally optimally mixed reliable networks among all n-vertex networks with fixed sizes m=n, m=n+1 and m=n+2, respectively.

The classical graph entropy based on the vertex coloring proposed by Mowshowitz depends on a graph. In fact, a hypergraph, as a generalization of a graph, can express complex and high-order relations such that it is often used to model complex systems. Being different from the classical graph entropy, we extend this concept to a hypergraph. Then, we define the graph entropy based on the vertex strong coloring of a hypergraph. Moreover, some tightly upper and lower bounds of such graph entropies as well as the corresponding extremal hypergraphs are obtained.

In this paper, we mainly study the exact controllability of several types of extended-path molecular graph networks. Based on the construction of extended-path molecular graph networks with C3, C4, or K4, using the determinant operation of the matrix and the recursive method, the exact characteristic polynomial of these networks is deduced. According to the definition of minimum driver node number ND, the exact controllability of these networks is obtained. Moreover, we give the minimum driver node sets of partial small networks.

Representation learning aims to encode the relationships of research objects into low-dimensional, compressible, and distributed representation vectors. The purpose of network representation learning is to learn the structural relationships between network vertices. Knowledge representation learning is oriented to model the entities and relationships in knowledge bases. In this paper, we first introduce the idea of knowledge representation learning into network representation learning, namely, we propose a new approach to model the vertex triplet relationships based on DeepWalk without TransE. Consequently, we propose an optimized network representation learning algorithm using multi-relational data, MRNR, which introduces the multi-relational data between vertices into the procedures of network representation learning. Importantly, we adopted a kind of higher order transformation strategy to optimize the learnt network representation vectors. The purpose of MRNR is that multi-relational data (triplets) can effectively guide and constrain the procedures of network representation learning. The experimental results demonstrate that the proposed MRNR can learn the discriminative network representations, which show better performance on network classification, visualization, and case study tasks compared to the proposed baseline algorithms in this paper.

Network representation learning is a key research field in network data mining. In this paper, we propose a novel multi-view network representation algorithm (MVNR), which embeds multi-scale relations of network vertices into the low dimensional representation space. In contrast to existing approaches, MVNR explicitly encodes higher order information using k-step networks. In addition, we introduce the matrix forest index as a kind of network feature, which can be applied to balance the representation weights of different network views. We also research the relevance amongst MVNR and several excellent research achievements, including DeepWalk, node2vec and GraRep and so forth. We conduct our experiment on several real-world citation datasets and demonstrate that MVNR outperforms some new approaches using neural matrix factorization. Specifically, we demonstrate the efficiency of MVNR on network classification, visualization and link prediction tasks.

A hypergraph H = ( V , ε ) is a pair consisting of a vertex set V , and a set ε of subsets (the hyperedges of H ) of V . A hypergraph H is r -uniform if all the hyperedges of H have the same cardinality r . Let H be an r -uniform hypergraph, we generalize the concept of trees for r -uniform hypergraphs. We say that an r -uniform hypergraph H is a generalized hypertree ( G H T ) if H is disconnected after removing any hyperedge E , and the number of components of G H T − E is a fixed value k ( 2 ≤ k ≤ r ) . We focus on the case that G H T − E has exactly two components. An edge-minimal G H T is a G H T whose edge set is minimal with respect to inclusion. After considering these definitions, we show that an r -uniform G H T on n vertices has at least 2 n / ( r + 1 ) edges and it has at most n − r + 1 edges if r ≥ 3 and n ≥ 3 , and the lower and upper bounds on the edge number are sharp. We then discuss the case that G H T − E has exactly k ( 2 ≤ k ≤ r − 1 ) components.

Controlling complex network is an essential problem in network science and engineering. Recent advances indicate that the controllability of complex network is dependent on the network's topology. Liu and Barabási, et.al speculated that the degree distribution was one of the most important factors affecting controllability for arbitrary complex directed network with random link weights. In this paper, we analysed the effect of degree distribution to the controllability for the deterministic networks with unweighted and undirected. We introduce a class of deterministic networks with identical degree sequence, called (x,y)-flower. We analysed controllability of the two deterministic networks ((1, 3)-flower and (2, 2)-flower) by exact controllability theory in detail and give accurate results of the minimum number of driver nodes for the two networks. In simulation, we compare the controllability of (x,y)-flower networks. Our results show that the family of (x,y)-flower networks have the same degree sequence, but their controllability is totally different. So the degree distribution itself is not sufficient to characterize the controllability of deterministic networks with unweighted and undirected.

Complex networks have seen much interest from all research fields and have found many potential applications in a variety of areas including natural, social, biological, and engineering technology. The deterministic models for complex networks play an indispensable role in the field of network model. The construction of a network model in a deterministic way not only has important theoretical significance, but also has potential application value. In this paper, we present a class of 3-regular network model with small world phenomenon. We determine its relevant topological characteristics, such as diameter and clustering coefficient. We also give a calculation method of number of spanning trees in the 3-regular network and derive the number and entropy of spanning trees, respectively.

For a simple hypergraph H on n vertices, its Estrada index is defined as EE(H)=∑i=1n‍eλi, where λ1,λ2,…,λn are the eigenvalues of its adjacency matrix. In this paper, we determine the unique 3-uniform linear hypertree with the maximum Estrada index.

Subgraph centrality measure characterizes the participation of each node in all subgraphs in a network. Smaller subgraphs are given more weight than large ones, which makes this measure appropriate for characterizing network motifs. This measure is better in being able to discriminate the nodes of a network than alternate measures. In this paper, the important issue of subgraph centrality distributions is investigated through theory-guided extensive numerical simulations, for three typical complex network models, namely, the ER random-graph networks, WS small-world networks, and BA scale-free networks. It is found that these three very different types of complex networks share some common features, particularly that the subgraph centrality distributions in increasing order are all insensitive to the network connectivity characteristics, and also found that the probability distributions of subgraph centrality of the ER and of the WS models both follow the gamma distribution, and the BA scale-free networks exhibit a power-law distribution with an exponential cutoff.