Graph data mining has been a crucial as well as inevitable area of research.Large amounts of graph data are produced in many areas,such as Bioinformatics,Cheminformatics,Social Networks,etc.Scalable graph data mining ...Graph data mining has been a crucial as well as inevitable area of research.Large amounts of graph data are produced in many areas,such as Bioinformatics,Cheminformatics,Social Networks,etc.Scalable graph data mining methods are getting increasingly popular and necessary due to increased graph complexities.Frequent subgraph mining is one such area where the task is to find overly recurring patterns/subgraphs.To tackle this problem,many main memory-based methods were proposed,which proved to be inefficient as the data size grew exponentially over time.In the past few years,several research groups have attempted to handle the Frequent Subgraph Mining(FSM)problem in multiple ways.Many authors have tried to achieve better performance using Graphic Processing Units(GPUs)which has multi-fold improvement over in-memory while dealing with large datasets.Later,Google’s MapReduce model with the Hadoop framework proved to be a major breakthrough in high performance large batch processing.Although MapReduce came with many benefits,its disk I/O and noniterative style model could not help much for FSM domain since subgraph mining process is an iterative approach.In recent years,Spark has emerged to be the De Facto industry standard with its distributed in-memory computing capability.This is a right fit solution for iterative style of programming as well.In this survey,we cover how high-performance computing has helped in improving the performance tremendously in the transactional directed and undirected aspect of graphs and performance comparisons of various FSM techniques are done based on experimental results.展开更多
With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have cho...With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have chosen different indexing methods in the filtering stage to obtain more optimized query results because currently there is no uniform and efficient indexing mechanism that achieves good query results. In the traditional algorithm, the hash table for index storage is prone to "collision" problems, which decrease the index construction efficiency. Aiming at the problem of quick index entry, based on the construction of frequent subgraph indexes, a method of serialized storage optimization based on multiple hash tables is proposed. This method mainly uses the exploration sequence to make the keywords evenly distributed; it avoids conflicts of the stored procedure and performs a quick search of the index. The proposed algorithm mainly adopts the "filterverify" mechanism; in the filtering stage, the index is first established offline, and then the frequent subgraphs are found using the "contains logic" rule to obtain the candidate set. Experimental results show that this method can reduce the time and scale of candidate set generation and improve query efficiency.展开更多
A graph is said to be K1,4-free if it does not contain an induced subgraph isomorphic to K1,4. Let κ be an integer with κ ≥ 2. We prove that if G is a K1,4-free graph of order at least llκ- 10 with minimum degree ...A graph is said to be K1,4-free if it does not contain an induced subgraph isomorphic to K1,4. Let κ be an integer with κ ≥ 2. We prove that if G is a K1,4-free graph of order at least llκ- 10 with minimum degree at least four, then G contains k vertex-disjoint copies of K1 ＋ （K1 ∪ KK2）.展开更多
For non-negative integers i,j and k,let N i,j,k be the graph obtained by identifying end vertices of three disjoint paths of lengths i,j and k to the vertices of a triangle.In this paper,we prove that every 3-connecte...For non-negative integers i,j and k,let N i,j,k be the graph obtained by identifying end vertices of three disjoint paths of lengths i,j and k to the vertices of a triangle.In this paper,we prove that every 3-connected {K1,3,N3,3,3 }-free graph is Hamiltonian.This result is sharp in the sense that for any integer i>3,there exist infinitely many 3-connected {K1,3,Ni,3,3 }-free non-Hamiltonian graphs.展开更多
The generating function for generating integer sequence of Aunu numbers of prime cardinality was reported earlier by the author in [1]. This paper assigns an operator on the function for where the op...The generating function for generating integer sequence of Aunu numbers of prime cardinality was reported earlier by the author in [1]. This paper assigns an operator on the function for where the operation induces addition or subtraction on the pairs of ai, aj elements which are consecutive pairs of elements obtained from a generating set of some finite order. The paper identifies that the set of the generated pairs of integer sequence is non-associative. The paper also presents the graph theoretic applications of the integers generated in which subgraphs are deduced from the main graph and adjacency matrices and incidence matrices constructed. It was also established that some of the subgraphs were found to be regular graphs. The findings in this paper can further be used in coding theory, Boolean algebra and circuit designs.展开更多
In this article, we are interested in solving a combinatorial optimization problem, the shortest path problem in a multi-attribute graph, by the out-ranking methods. A multi-attribute graph has simultaneously qualitat...In this article, we are interested in solving a combinatorial optimization problem, the shortest path problem in a multi-attribute graph, by the out-ranking methods. A multi-attribute graph has simultaneously qualitative and quantitative criteria. This situation gives rise to incomparable paths thus forming the Pareto front. Outranking methods in Multi-criteria Decision Making (MCDM) are the only methods that can take into account this situation (incomparability of actions). After presenting the categories of Multi-criteria Decision Making (MCDM) and the difficulties related to the problems of the shortest paths, we propose an evolutionary algorithm based on the outranking methods to solve the problem of finding “best” paths in a multi-attribute graph with non-additive criteria. Our approach is based on the exploration of induced subgraphs of the outranking graph. Properties have been established to serve as algorithmic basis. Numerical experiments have been carried out and the results presented in this article.展开更多
A graph is called traceable if it contains a Hamilton path, i.e., a path passing through all the vertices. Let G be a graph on n vertices. G is called claw-o-1-heavy if every induced claw(K_(1,3)) of G has a pair of n...A graph is called traceable if it contains a Hamilton path, i.e., a path passing through all the vertices. Let G be a graph on n vertices. G is called claw-o-1-heavy if every induced claw(K_(1,3)) of G has a pair of nonadjacent vertices with degree sum at least n-1 in G. In this paper we show that a claw-o-1-heavy graph G is traceable if we impose certain additional conditions on G involving forbidden induced subgraphs.展开更多
For non-negative integers i,j and k, we denote the generalized net as Ni,j,k, which is a triangle with disjoint paths of length i, j and k, attached to distinct vertices of the triangle. In this paper, we prove that e...For non-negative integers i,j and k, we denote the generalized net as Ni,j,k, which is a triangle with disjoint paths of length i, j and k, attached to distinct vertices of the triangle. In this paper, we prove that every 3-connected {K1,3,N8-i,i,1}-free graph is hamiltonian, where 1〈i〈4.展开更多
A graph is claw-free if it contains no induced subgraph isomorphic to a K1,3.This paper studies hamiltonicity in 3-connected claw-free graphs.Four generation of Shepherd’s result[4] are obtained.For example,we show t...A graph is claw-free if it contains no induced subgraph isomorphic to a K1,3.This paper studies hamiltonicity in 3-connected claw-free graphs.Four generation of Shepherd’s result[4] are obtained.For example,we show that if G is.3-connected claw-free graph and(1)if for each vertex V the set of venices at distance three from v doesn’tcontain and independent subset of size three,then G is hamiltonian;(2) if G contains no induced subgraph with degree sequence(1,1,1,2,2,2,3,3,3),so that ear vertel of degree is adjacent to a vertex of degree i + 1 for i=1,2,then G is hamiltonoan. Furthermore,we obtain a generalization of both(1) and(2),in which the graphs F1 and F2coatain an the known forbidded subgraphs given in[3] as indeced subgraphs.展开更多
One main challenge for simplifying node-link diagrams of large-scale social networks lies in that simplified graphs generally contain dense subgroups or cohesive subgraphs.Graph triangles quantify the solid and stable...One main challenge for simplifying node-link diagrams of large-scale social networks lies in that simplified graphs generally contain dense subgroups or cohesive subgraphs.Graph triangles quantify the solid and stable relationships that maintain cohesive subgraphs.Understanding the mechanism of triangles within cohesive subgraphs contributes to illuminating patterns of connections within social networks.However,prior works can hardly handle and visualize triangles in cohesive subgraphs.In this paper,we propose a triangle-based graph simplification approach that can filter and visualize cohesive subgraphs by leveraging a triangle-connectivity called k-truss and a force-directed algorithm.We design and implement TriGraph,a web-based visual interface that provides detailed information for exploring and analyzing social networks.Quantitative comparisons with existing methods,two case studies on real-world datasets,and feedback from domain experts demonstrate the effectiveness of TriGraph.展开更多
The traditional game of cops and robbers is played on undirected graph. Recently, the same game played on directed graph is getting attention by more and more people. We knew that if we forbid some subgraph we can bou...The traditional game of cops and robbers is played on undirected graph. Recently, the same game played on directed graph is getting attention by more and more people. We knew that if we forbid some subgraph we can bound the cop number of the corresponding class of graphs. In this paper, we analyze the game of cops and robbers on H^(-)-free digraphs. However, it is not the same as the case of undirected graph. So we give a new concept(H^(-)^(*)-free digraph) to get a similar conclusion about the case of undirected graph.展开更多
提出适用于配有三维激光雷达的自主移动机器人在室外场景进行同时定位与地图创建(simul-taneous localization and mapping, SLAM)的一种闭环检测算法,命名为SegGraph.作为SLAM的关键模块,闭环检测的任务是判断机器人当前位置是否与已...提出适用于配有三维激光雷达的自主移动机器人在室外场景进行同时定位与地图创建(simul-taneous localization and mapping, SLAM)的一种闭环检测算法,命名为SegGraph.作为SLAM的关键模块,闭环检测的任务是判断机器人当前位置是否与已到过的某一位置邻近.SegGraph包含3步:1)对在不同时刻得到的2组点云分别移除大地平面后采用区域增长方法分割为若干个点云簇;2)以点云簇为顶点,以点云簇图心间距离为边权值,分别构建带权值的完全图;3)判定所得的2个完全图是否含有足够大的公共子图.SegGraph的主要创新点是在寻找公共子图时以边权值(即点云簇间距离)为主要匹配依据.这是因为点云数据中的噪声会导致在邻近地点获得的不同点云经分割后得出差别很大的点云簇集,不同点云中相应的点云簇也便无法匹配.然而相应点云簇间距离却受分割过程影响不大.主要贡献包括研发高效的判定2个点云簇图是否有足够大的公共子图的近似算法,实现完整的SegGraph算法,及以被广泛使用的公开数据集KITTI(Karlsruhe Institute of Technology and Toyota Technological Institute)评估SegGraph的准确度及运行效率.实验结果显示SegGraph具有良好的准确度及运行效率.展开更多
文摘Graph data mining has been a crucial as well as inevitable area of research.Large amounts of graph data are produced in many areas,such as Bioinformatics,Cheminformatics,Social Networks,etc.Scalable graph data mining methods are getting increasingly popular and necessary due to increased graph complexities.Frequent subgraph mining is one such area where the task is to find overly recurring patterns/subgraphs.To tackle this problem,many main memory-based methods were proposed,which proved to be inefficient as the data size grew exponentially over time.In the past few years,several research groups have attempted to handle the Frequent Subgraph Mining(FSM)problem in multiple ways.Many authors have tried to achieve better performance using Graphic Processing Units(GPUs)which has multi-fold improvement over in-memory while dealing with large datasets.Later,Google’s MapReduce model with the Hadoop framework proved to be a major breakthrough in high performance large batch processing.Although MapReduce came with many benefits,its disk I/O and noniterative style model could not help much for FSM domain since subgraph mining process is an iterative approach.In recent years,Spark has emerged to be the De Facto industry standard with its distributed in-memory computing capability.This is a right fit solution for iterative style of programming as well.In this survey,we cover how high-performance computing has helped in improving the performance tremendously in the transactional directed and undirected aspect of graphs and performance comparisons of various FSM techniques are done based on experimental results.
基金supported by the State Grid Science and Technology Project (Title: Research on High Performance Analysis Technology of Power Grid GIS Topology Based on Graph Database, 5455HJ160005)
文摘With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have chosen different indexing methods in the filtering stage to obtain more optimized query results because currently there is no uniform and efficient indexing mechanism that achieves good query results. In the traditional algorithm, the hash table for index storage is prone to "collision" problems, which decrease the index construction efficiency. Aiming at the problem of quick index entry, based on the construction of frequent subgraph indexes, a method of serialized storage optimization based on multiple hash tables is proposed. This method mainly uses the exploration sequence to make the keywords evenly distributed; it avoids conflicts of the stored procedure and performs a quick search of the index. The proposed algorithm mainly adopts the "filterverify" mechanism; in the filtering stage, the index is first established offline, and then the frequent subgraphs are found using the "contains logic" rule to obtain the candidate set. Experimental results show that this method can reduce the time and scale of candidate set generation and improve query efficiency.
基金Supported by National Natural Science Foundation of China(Grant Nos.11161035 and 11226292)Ningxia Ziran(Grant No.NZ1153)research grant from Ningxia University(Grant No.zr1122)
文摘A graph is said to be K1,4-free if it does not contain an induced subgraph isomorphic to K1,4. Let κ be an integer with κ ≥ 2. We prove that if G is a K1,4-free graph of order at least llκ- 10 with minimum degree at least four, then G contains k vertex-disjoint copies of K1 ＋ （K1 ∪ KK2）.
基金supported by National Natural Science Foundation of China (Grant Nos.11071096 and 11271149)Hubei Provincial Department of Education (Grant No. D20111110)Jinan Science and Technology Bureau (Grant No. 20110205)
文摘For non-negative integers i,j and k,let N i,j,k be the graph obtained by identifying end vertices of three disjoint paths of lengths i,j and k to the vertices of a triangle.In this paper,we prove that every 3-connected {K1,3,N3,3,3 }-free graph is Hamiltonian.This result is sharp in the sense that for any integer i>3,there exist infinitely many 3-connected {K1,3,Ni,3,3 }-free non-Hamiltonian graphs.
文摘The generating function for generating integer sequence of Aunu numbers of prime cardinality was reported earlier by the author in [1]. This paper assigns an operator on the function for where the operation induces addition or subtraction on the pairs of ai, aj elements which are consecutive pairs of elements obtained from a generating set of some finite order. The paper identifies that the set of the generated pairs of integer sequence is non-associative. The paper also presents the graph theoretic applications of the integers generated in which subgraphs are deduced from the main graph and adjacency matrices and incidence matrices constructed. It was also established that some of the subgraphs were found to be regular graphs. The findings in this paper can further be used in coding theory, Boolean algebra and circuit designs.
文摘In this article, we are interested in solving a combinatorial optimization problem, the shortest path problem in a multi-attribute graph, by the out-ranking methods. A multi-attribute graph has simultaneously qualitative and quantitative criteria. This situation gives rise to incomparable paths thus forming the Pareto front. Outranking methods in Multi-criteria Decision Making (MCDM) are the only methods that can take into account this situation (incomparability of actions). After presenting the categories of Multi-criteria Decision Making (MCDM) and the difficulties related to the problems of the shortest paths, we propose an evolutionary algorithm based on the outranking methods to solve the problem of finding “best” paths in a multi-attribute graph with non-additive criteria. Our approach is based on the exploration of induced subgraphs of the outranking graph. Properties have been established to serve as algorithmic basis. Numerical experiments have been carried out and the results presented in this article.
基金Supported by the National Natural Science Foundation of China(No.11601429,11671320 and U1803263)the Fundamental Research Funds for the Central Universities(No.3102018zy035)
文摘A graph is called traceable if it contains a Hamilton path, i.e., a path passing through all the vertices. Let G be a graph on n vertices. G is called claw-o-1-heavy if every induced claw(K_(1,3)) of G has a pair of nonadjacent vertices with degree sum at least n-1 in G. In this paper we show that a claw-o-1-heavy graph G is traceable if we impose certain additional conditions on G involving forbidden induced subgraphs.
基金Supported by the National Natural Science Foundation of China(No.11371162 and No.11271149)A project of Shandong Province Higher Educational Science and Technology Program(No.J15LI52)Science and Technology Development Project of Shandong Province(No.2014GGX101033)
文摘For non-negative integers i,j and k, we denote the generalized net as Ni,j,k, which is a triangle with disjoint paths of length i, j and k, attached to distinct vertices of the triangle. In this paper, we prove that every 3-connected {K1,3,N8-i,i,1}-free graph is hamiltonian, where 1〈i〈4.
文摘A graph is claw-free if it contains no induced subgraph isomorphic to a K1,3.This paper studies hamiltonicity in 3-connected claw-free graphs.Four generation of Shepherd’s result[4] are obtained.For example,we show that if G is.3-connected claw-free graph and(1)if for each vertex V the set of venices at distance three from v doesn’tcontain and independent subset of size three,then G is hamiltonian;(2) if G contains no induced subgraph with degree sequence(1,1,1,2,2,2,3,3,3),so that ear vertel of degree is adjacent to a vertex of degree i + 1 for i=1,2,then G is hamiltonoan. Furthermore,we obtain a generalization of both(1) and(2),in which the graphs F1 and F2coatain an the known forbidded subgraphs given in[3] as indeced subgraphs.
基金supported by National Natural Science Foundation of China(62132017)Fundamental Research Funds for the Central Universities,China(226-2022-00235).
文摘One main challenge for simplifying node-link diagrams of large-scale social networks lies in that simplified graphs generally contain dense subgroups or cohesive subgraphs.Graph triangles quantify the solid and stable relationships that maintain cohesive subgraphs.Understanding the mechanism of triangles within cohesive subgraphs contributes to illuminating patterns of connections within social networks.However,prior works can hardly handle and visualize triangles in cohesive subgraphs.In this paper,we propose a triangle-based graph simplification approach that can filter and visualize cohesive subgraphs by leveraging a triangle-connectivity called k-truss and a force-directed algorithm.We design and implement TriGraph,a web-based visual interface that provides detailed information for exploring and analyzing social networks.Quantitative comparisons with existing methods,two case studies on real-world datasets,and feedback from domain experts demonstrate the effectiveness of TriGraph.
文摘The traditional game of cops and robbers is played on undirected graph. Recently, the same game played on directed graph is getting attention by more and more people. We knew that if we forbid some subgraph we can bound the cop number of the corresponding class of graphs. In this paper, we analyze the game of cops and robbers on H^(-)-free digraphs. However, it is not the same as the case of undirected graph. So we give a new concept(H^(-)^(*)-free digraph) to get a similar conclusion about the case of undirected graph.
文摘提出适用于配有三维激光雷达的自主移动机器人在室外场景进行同时定位与地图创建(simul-taneous localization and mapping, SLAM)的一种闭环检测算法,命名为SegGraph.作为SLAM的关键模块,闭环检测的任务是判断机器人当前位置是否与已到过的某一位置邻近.SegGraph包含3步:1)对在不同时刻得到的2组点云分别移除大地平面后采用区域增长方法分割为若干个点云簇;2)以点云簇为顶点,以点云簇图心间距离为边权值,分别构建带权值的完全图;3)判定所得的2个完全图是否含有足够大的公共子图.SegGraph的主要创新点是在寻找公共子图时以边权值(即点云簇间距离)为主要匹配依据.这是因为点云数据中的噪声会导致在邻近地点获得的不同点云经分割后得出差别很大的点云簇集,不同点云中相应的点云簇也便无法匹配.然而相应点云簇间距离却受分割过程影响不大.主要贡献包括研发高效的判定2个点云簇图是否有足够大的公共子图的近似算法,实现完整的SegGraph算法,及以被广泛使用的公开数据集KITTI(Karlsruhe Institute of Technology and Toyota Technological Institute)评估SegGraph的准确度及运行效率.实验结果显示SegGraph具有良好的准确度及运行效率.
