摘要：
Let G = (V, E) be a graph and Cm be the cycle graph with m vertices. In this paper, we continued Yeh’s work [1] on the distance labeling of the cycle graph Cm. An n-set distance labeling of a graph G is the labeling of the vertices (with n labels per vertex) of G under certain constraints depending on the distance between each pair of the vertices in G. Following Yeh’s notation [1], the smallest value for the largest label in an n-set distance labeling of G is denoted by λ1(n)(G). Basic results were presented in [1] for λ1(2)(Cm) for all m and λ1(n)(Cm) for some m where n ≥ 3. However, there were still gaps left unstudied due to case-by-case complexities. For these uncovered cases, we proved a lower bound for λ1(n)(Cm). Then we proposed an algorithm for finding an n-set distance labeling for n ≥ 3 based on our proof of the lower bound. We verified every single case for n = 3?up to n = 500?by this same algorithm, which indicated that the upper bound is the same as the lower bound for n ≤ 500.
摘要：
Recently,whether the channel prediction can be achieved in diverse communication scenarios by directly utilizing the environment information gained lots of attention due to the environment impacting the propagation characteristics of the wireless channel.This paper presents an environment information-based channel prediction(EICP)method for connecting the environment with the channel assisted by the graph neural networks(GNN).Firstly,the effective scatterers(ESs)producing paths and the primary scatterers(PSs)generating single propagation paths are detected by building the scatterercentered communication environment graphs(SCCEGs),which can simultaneously preserve the structure information and highlight the pending scatterer.The GNN-based classification model is implemented to distinguish ESs and PSs from other scatterers.Secondly,large-scale parameters(LSP)and small-scale parameters(SSP)are predicted by employing the GNNs with multi-target architecture and the graphs of detected ESs and PSs.Simulation results show that the average normalized mean squared error(NMSE)of LSP and SSP predictions are 0.12 and 0.008,which outperforms the methods of linear data learning.
摘要：
A distributed information network with complex network structure always has a challenge of locating fault root causes.In this paper,we propose a novel root cause analysis(RCA)method by random walk on the weighted fault propagation graph.Different from other RCA methods,it mines effective features information related to root causes from offline alarms.Combined with the information,online alarms and graph relationship of network structure are used to construct a weighted graph.Thus,this approach does not require operational experience and can be widely applied in different distributed networks.The proposed method can be used in multiple fault location cases.The experiment results show the proposed approach achieves much better performance with 6%higher precision at least for root fault location,compared with three baseline methods.Besides,we explain how the optimal parameter’s value in the random walk algorithm influences RCA results.
摘要：
SpacetimeAI and GeoAI are currently hot topics,applying the latest algorithms in computer science,such as deep learning,to spatiotemporal data.Although deep learning algorithms have been successfully applied to raster data due to their natural applicability to image processing,their applications in other spatial and space-time data types are still immature.This paper sets up the proposition of using a network(&graph)-based framework as a generic spatial structure to present space-time processes that are usually represented by the points,polylines,and polygons.We illustrate network and graph-based SpaceTimeAI,from graph-based deep learning for prediction,to space-time clustering and optimisation.These applications demonstrate the advantages of network(graph)-based SpacetimeAI in the fields of transport&mobility,crime&policing,and public health.
摘要：
Molecular dynamics is a powerful simulation tool to explore material properties.Most realistic material systems are too large to be simulated using first-principles molecular dynamics.Classical molecular dynamics has a lower computational cost but requires accurate force fields to achieve chemical accuracy.In this work,we develop a symmetry-adapted graph neural network framework called the molecular dynamics graph neural network(MDGNN)to construct force fields automatically for molecular dynamics simulations for both molecules and crystals.This architecture consistently preserves translation,rotation,and permutation invariance in the simulations.We also propose a new feature engineering method that includes high-order terms of interatomic distances and demonstrate that the MDGNN accurately reproduces the results of both classical and first-principles molecular dynamics.In addition,we demonstrate that force fields constructed by the proposed model have good transferability.The MDGNN is thus an efficient and promising option for performing molecular dynamics simulations of large-scale systems with high accuracy.
摘要：
For two graphs G and H, if G and H have the same matching polynomial, then G and H are said to be matching equivalent. We denote by δ (G), the number of the matching equivalent graphs of G. In this paper, we give δ?(sK1 ∪ t1C9 ∪ t2C15), which is a generation of the results of in [1].
摘要：
As XML data becomes more and more, graph structure join urgently requires rapid judgement algorithm of the reachability of the two vertexes in a graph. The existing graph reachability algorithm includes 2-HOP, HOPI and Dual Labeling, but they don't support graph update, and the time complexity and the space complexity of the first two algorithm are too large to use in the real applications. In the present paper, a new update-aware graph reachability algorithm GraphReach is proposed. The algorithm first computes the minimal equivalent graph of the original graph, sperates it into the spanning tree and non-tree edges. Then the algorithm codes the nodes of the spanning tree and builds index for the non-tree edges. Finally, the algorithm proposes rules to judge the reaachability of the two points in the original graph. Experimental results show that the algorithm proposed in this paper can processing graph reachability fast and the algorithm is useful for real applications.
摘要：
Testing reachability between nodes in a graph is a well-known problem with many important applications, including knowledge representation, program analysis, and more recently, ontology management as well as XML query processing. Various approaches have been proposed to encode graph reachability information using node labeling schemes, but they are all unable to effectively support the dynamic update of graph. In this paper, we propose a novel approach called FLS (Fractional Labeling Scheme) to solve this problem, and corresponding algorithms. We also prove some theorems that present analytical results. A notable feature of FLS is that it uses the idea of trichotomy and the unlimited partition nature of fraction number to support fully update of the graph.
AI畢業(yè)論文
