Heuristic Expanding Disconnected Graph:A Rapid Path Planning Method for Mobile Robots

Existing mobile robots mostly use graph search algorithms for path planning,which suffer from relatively low planning efficiency owing to high redundancy and large computational complexity.Due to the limitations of the neighborhood search strategy,the robots could hardly obtain the most optimal global path.A global path planning algorithm,denoted as EDG*,is proposed by expanding nodes using a well-designed expanding disconnected graph operator(EDG)in this paper.Firstly,all obstacles are marked and their corners are located through the map pre-processing.Then,the EDG operator is designed to find points in non-obstruction areas to complete the rapid expansion of disconnected nodes.Finally,the EDG*heuristic iterative algorithm is proposed.It selects the candidate node through a specific valuation function and realizes the node expansion while avoiding collision with a minimum offset.Path planning experiments were conducted in a typical indoor environment and on the public dataset CSM.The result shows that the proposed EDG*reduced the planning time by more than 90%and total length of paths reduced by more than 4.6%.Compared to A*,Dijkstra and JPS,EDG*does not show an exponential explosion effect in map size.The EDG*showed better performance in terms of path smoothness,and collision avoidance.This shows that the EDG*algorithm proposed in this paper can improve the efficiency of path planning and enhance path quality.

Task Offloading and Resource Allocation in NOMA-VEC:A Multi-Agent Deep Graph Reinforcement Learning Algorithm

Vehicular edge computing(VEC)is emerging as a promising solution paradigm to meet the requirements of compute-intensive applications in internet of vehicle(IoV).Non-orthogonal multiple access(NOMA)has advantages in improving spectrum efficiency and dealing with bandwidth scarcity and cost.It is an encouraging progress combining VEC and NOMA.In this paper,we jointly optimize task offloading decision and resource allocation to maximize the service utility of the NOMA-VEC system.To solve the optimization problem,we propose a multiagent deep graph reinforcement learning algorithm.The algorithm extracts the topological features and relationship information between agents from the system state as observations,outputs task offloading decision and resource allocation simultaneously with local policy network,which is updated by a local learner.Simulation results demonstrate that the proposed method achieves a 1.52%∼5.80%improvement compared with the benchmark algorithms in system service utility.

Nonlinear Relationship and Its Evolutionary Trace between Average Degree and Average Path Length of Edge Vertices of China Aviation Network Based on Complex Network

In order to reveal the complex network characteristics and evolution principle of China aviation network,the relationship between the average degree and the average path length of edge vertices of China aviation network in 1988,1994,2001,2008 and 2015 was studied.According to the theory and method of complex network,the network system was constructed with the city where the airport was located as the network node and the airline as the edge of the network.On the basis of the statistical data,the average degree and average path length of edge vertices of China aviation network in 1988,1994,2001,2008 and 2015 were calculated.Through regression analysis,it was found that the average degree had a logarithmic relationship with the average path length of edge vertices and the two parameters of the logarithmic relationship had linear evolutionary trace.

Probability Distribution of China Aviation Network Average Degree of Edge Vertices and Its Evolutionary Trace Based on Complex Network

In order to reveal the complex network characteristics and evolution principle of China aviation network, the probability distribution and evolution trace of average degree of edge vertices of China aviation network were studied based on the statistics data of China civil aviation network in 1988, 1994, 2001, 2008 and 2015. According to the theory and method of complex network, the network system was constructed with the city where the airport was located as the network node and the route between cities as the edge of the network. Based on the statistical data, the average degrees of edge vertices in China aviation network in 1988, 1994, 2001, 2008 and 2015 were calculated. Using the probability statistical analysis method and regression analysis approach, it was found that the average degree of edge vertices had the probability distribution of normal function and the position parameters and scale parameters of the probability distribution had linear evolution trace.

Probability Distribution of Ratio of China Aviation Network Edge Vertices Degree and Its Evolutionary Trace Based on Complex Network

In order to reveal the complex network characteristics and evolution principle of China aviation network, the probability distribution and evolution trace of ratio of China aviation network edge vertices degree were studied based on the statistics data of China civil aviation network in 1988, 1994, 2001, 2008 and 2015. According to the theory and method of complex network, the network system was constructed with the city where the airport was located as the network node and the route between cities as the edge of the network. Based on the statistical data, the ratio of edge vertices degree in China aviation network in 1988, 1994, 2001, 2008 and 2015 were calculated. Using the probability statistical analysis method and regression analysis approach, it was found that the ratio of edge vertices degree had linear probability distribution and the two parameters of the probability distribution had linear evolution trace.

Probability Distribution of Arithmetic Average of China Aviation Network Edge Vertices Nearest Neighbor Average Degree Value and Its Evolutionary Trace Based on Complex Network

In order to reveal the complex network characteristics and evolution principle of China aviation network,the probability distribution and evolution trace of arithmetic average of edge vertices nearest neighbor average degree values of China aviation network were studied based on the statistics data of China civil aviation network in 1988,1994,2001,2008 and 2015.According to the theory and method of complex network,the network system was constructed with the city where the airport was located as the network node and the route between cities as the edge of the network.Based on the statistical data,the arithmetic averages of edge vertices nearest neighbor average degree values of China aviation network in 1988,1994,2001,2008 and 2015 were calculated.Using the probability statistical analysis method,it was found that the arithmetic average of edge vertices nearest neighbor average degree values had the probability distribution of normal function and the position parameters and scale parameters of the probability distribution had linear evolution trace.

Interactive multigraph visualization and exploration with a two-phase strategy

While it is very reasonable to use a multigraph consisting of multiple edges between vertices to represent various relationships, the multigraph has not drawn much attention in research. To visualize such a multigraph, a clear layout representing a global structure is of great importance, and interactive visual analysis which allows the multiple edges to be adjusted in appropriate ways for detailed presentation is also essential. A novel interactive two-phase approach to visualizing and exploring multigraph is proposed. The approach consists of two phases： the first phase improves the previous popular works on force-directed methods to produce a brief drawing for the aggregation graph of the input multigraph, while the second phase proposes two interactive strategies, the magnifier model and the thematic-oriented subgraph model. The former highlights the internal details of an aggregation edge which is selected interactively by user, and draws the details in a magnifying view by cubic Bezier curves; the latter highlights only the thematic subgraph consisting of the selected multiple edges that the user concerns. The efficiency of the proposed approach is demonstrated with a real-world multigraph dataset and how it is used effectively is discussed for various potential applications.

Bipartite Graphs with the First and Second Largest Laplacian Spectral Radius

Let Bn^k be the class of bipartite graphs with n vertices and k cut edges. The extremal graphs with the first and the second largest Laplacian spectral radius among all graphs in Bn^K are presented. The bounds of the Laplacian spectral radius of these extremal graphs are also obtained.

Edge-Computing with Graph Computation:A Novel Mechanism to Handle Network Intrusion and Address Spoofing in SDN

Software Defined Networking(SDN)being an emerging network control model is widely recognized as a control and management platform.This model provides efficient techniques to control and manage the enterprise network.Another emerging paradigm is edge computing in which data processing is performed at the edges of the network instead of a central controller.This data processing at the edge nodes reduces the latency and bandwidth requirements.In SDN,the controller is a single point of failure.Several security issues related to the traditional network can be solved by using SDN central management and control.Address Spoofing and Network Intrusion are the most common attacks.These attacks severely degrade performance and security.We propose an edge computing-based mechanism that automatically detects and mitigates those attacks.In this mechanism,an edge system gets the network topology from the controller and the Address Resolution Protocol(ARP)traffic is directed to it for further analysis.As such,the controller is saved from unnecessary processing related to addressing translation.We propose a graph computation based method to identify the location of an attacker or intruder by implementing a graph difference method.By using the correct location information,the exact attacker or intruder is blocked,while the legitimate users get access to the network resources.The proposed mechanism is evaluated in a Mininet simulator and a POX controller.The results show that it improves system performance in terms of attack mitigation time,attack detection time,and bandwidth requirements.

基于改进GraphSAGE算法的浏览器指纹追踪

当前Web追踪领域主要使用浏览器指纹对用户进行追踪。针对浏览器指纹追踪技术存在指纹随时间动态变化、不易长期追踪等问题,提出一种关注节点和边缘特征的改进图采样聚合算法(An Improved Graph SAmple and AGgregatE with Both Node and Edge Features,NE-GraphSAGE)用于浏览器指纹追踪。首先以浏览器指纹为节点、指纹之间特征相似度为边构建图数据。其次对图神经网络中的GraphSAGE算法进行改进使其不仅能关注节点特征,而且能捕获边缘信息并对边缘分类,从而识别指纹。最后将NE-GraphSAGE算法与Eckersley算法、FPStalker算法和LSTM算法进行对比,验证NE-GraphSAGE算法的识别效果。实验结果表明,NE-GraphSAGE算法在准确率和追踪时长上均有不同程度的提升,最大追踪时长可达80天,相比其他3种算法性能更优,验证了NE-GraphSAGE算法对浏览器指纹长期追踪的能力。

Maximum Number of Edges of (rK_t)-Free Graphs

With positive integers r,t and n,where n≥rt and t≥2,the maximum number of edges of a simple graph of order n is estimated,which does not contain r disjoint copies of K_r for r=2 and 3.

The acyclic chromatic index of planar graphs without 4-,6-cycles and intersecting triangles

A proper edge k-coloring is a mappingΦ:E(G)-→{1,2,...,k}such that any two adjacent edges receive different colors.A proper edge k-coloringΦof G is called acyclic if there are no bichromatic cycles in G.The acyclic chromatic index of G,denoted by Xa(G),is the smallest integer k such that G is acyclically edge k-colorable.In this paper,we show that if G is a plane graph without 4-,6-cycles and intersecting 3-cycles,△(G)≥9,then Xa(G)≤△(G)+1.

A CLASS OF HAMILTONIAN AND EDGE SYMMETRIC CAYLEY GRAPHS ON SYMMETRIC GROUPS

Let S\-n be the symmetric group, g\++\-i=(123i),g\+-\-i=(1i32) and M\++\-n={g\++\-i∶4≤i≤n}, then M\++\-n is a minimal generating set of S\-n ,where n ≥5.It is proved that Cayley graph Cay( S\-n,M\++\-n∪M\+-\-n) is Hamiltonian and edge symmetric.

EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH MAXIMUM DEGREE

The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with △（G）≥｜G｜ - 2≥9 has Xef（G） = △（G）.

A novel modeling approach for vertical handover based on dynamic k-partite graph in heterogeneous networks

The future network world will be embedded with different generations of wireless technologies,such as 3G,4G and 5G.At the same time,the development of new devices equipped with multiple interfaces is growing rapidly in recent years.As a consequence,the vertical handover protocol is developed in order to provide ubiquitous connectivity in the heterogeneous wireless environment.Indeed,by using this protocol,the users have opportunities to be connected to the Internet through a variety of wireless technologies at any time and anywhere.The main challenge of this protocol is how to select the best access network in terms of Quality of Service(QoS)for users.For that,many algorithms have been proposed and developed to deal with the issue in recent studies.However,all existing algorithms permit only the selection of one access network from the available networks during the vertical handover process.To cope with this problem,in this paper we propose a new approach based on k-partite graph.Firstly,we introduce k-partite graph theory to model the vertical handover problem.Secondly,the selection of the best path is performed by a robust and lightweight mechanism based on cost function and Dijkstra’s algorithm.The experimental results show that the proposed approach can achieve better performance of QoS than the existing algorithms for FTP traffic and video streaming.

Watershed-based Image Segmentation with Region Merging and Edge Detection

The clustering technique is used to examine each pixel in the image which assigned to one of the clusters depending on the minimum distance to obtain primary classified image into different intensity regions. A watershed transformation technique is then employes. This includes: gradient of the classified image, dividing the image into markers, checking the Marker Image to see if it has zero points (watershed lines). The watershed lines are then deleted in the Marker Image created by watershed algorithm. A Region Adjacency Graph (RAG) and Region Adjacency Boundary (RAB) are created between two regions from Marker Image. Finally region merging is done according to region average intensity and two edge strengths (T1, T2). The approach of the authors is tested on remote sensing and brain MR medical images. The final segmentation result is one closed boundary per actual region in the image.

Are networks with more edges easier to synchronize,or not?

In this paper, the relationship between network synchronizability and the edge-addition of its associated graph is investigated. First, it is shown that adding one edge to a cycle definitely decreases the network synchronizability. Then, since sometimes the synchronizability can be enhanced by changing the network structure, the question of whether the networks with more edges are easier to synchronize is addressed. Based on a subgraph and complementary graph method, it is shown by examples that the answer is negative even if the network structure is arbitrarily optimized. This reveals that generally there are redundant edges in a network, which not only make no contributions to synchronization but actually may reduce the synchronizability. Moreover, a simple example shows that the node betweenness centrality is not always a good indicator for the network synchronizability. Finally, some more examples are presented to illustrate how the network synchronizability varies following the addition of edges, where all the examples show that the network synchronizability globally increases but locally fluctuates as the number of added edges increases.

A Non-Conventional Coloring of the Edges of a Graph

Coloring the nodes of a graph is a commonly used technique to speed up clique search algorithms. Coloring the edges of the graph as a preconditioning method can also be used to speed up computations. In this paper we will show that an unconventional coloring scheme of the edges leads to an NP-complete problem when one intends to determine the optimal number of colors.

The Maximum Size of an Edge Cut and Graph Homomorphisms

For a graph G, let b(G)=max﹛|D|: Dis an edge cut of G﹜ . For graphs G and H, a map Ψ: V(G)→V(H) is a graph homomorphism if for each e=uv∈E(G), Ψ(u)Ψ(v)∈E(H). In 1979, Erd?s proved by probabilistic methods that for p ≥ 2 with if there is a graph homomorphism from G onto Kp then b(G)≥f(p)|E(G)| In this paper, we obtained the best possible lower bounds of b(G) for graphs G with a graph homomorphism onto a Kneser graph or a circulant graph and we characterized the graphs G reaching the lower bounds when G is an edge maximal graph with a graph homomorphism onto a complete graph, or onto an odd cycle.

Edge Colorings of Planar Graphs without 6-Cycles with Two Chords

It is proved here that if a planar graph has maximum degree at least 6 and any 6-cycle contains at most one chord, then it is of class 1.