很多频繁子图挖掘算法已被提出.然而,这些算法产生的频繁子图数量太多而不能被用户有效地利用.为此,提出了一个新的研究问题:挖掘图数据库中的频繁跳跃模式.挖掘频繁跳跃模式既可以大幅度地减少输出模式的数量,又能使有意义的图模式保...很多频繁子图挖掘算法已被提出.然而,这些算法产生的频繁子图数量太多而不能被用户有效地利用.为此,提出了一个新的研究问题:挖掘图数据库中的频繁跳跃模式.挖掘频繁跳跃模式既可以大幅度地减少输出模式的数量,又能使有意义的图模式保留在挖掘结果中.此外,跳跃模式还具有抗噪声干扰能力强等优点.然而,由于跳跃模式不具有反单调性质,挖掘它们非常具有挑战性.通过研究跳跃模式自身的特性,提出了两种新的裁剪技术:基于内扩展的裁剪和基于外扩展的裁剪.在此基础上又给出了一种高效的挖掘算法GraphJP(an algorithm for mining jump patterns from graph databases).另外,还严格证明了裁剪技术和算法GraphJP的正确性.实验结果表明,所提出的裁剪技术能够有效地裁剪图模式搜索空间,算法GraphJP是高效、可扩展的.展开更多
Let G be a finite group with order ｜G｜=p1^α1p2^α2……pk^αk, where p1 〈 p2 〈……〈 Pk are prime numbers. One of the well-known simple graphs associated with G is the prime graph （or Gruenberg- Kegel graph） den...Let G be a finite group with order ｜G｜=p1^α1p2^α2……pk^αk, where p1 〈 p2 〈……〈 Pk are prime numbers. One of the well-known simple graphs associated with G is the prime graph （or Gruenberg- Kegel graph） denoted .by г（G） （or GK（G））. This graph is constructed as follows： The vertex set of it is π（G） = {p1,p2,…,pk} and two vertices pi, pj with i≠j are adjacent by an edge （and we write pi - pj） if and only if G contains an element of order pipj. The degree deg（pi） of a vertex pj ∈π（G） is the number of edges incident on pi. We define D（G） ：= （deg（p1）, deg（p2）,..., deg（pk））, which is called the degree pattern of G. A group G is called k-fold OD-characterizable if there exist exactly k non- isomorphic groups H such that ｜H｜ = ｜G｜ and D（H） = D（G）. Moreover, a 1-fold OD-characterizable group is simply called OD-characterizable. Let L ：= U3（5） be the projective special unitary group. In this paper, we classify groups with the same order and degree pattern as an almost simple group related to L. In fact, we obtain that L and L.2 are OD-characterizable; L.3 is 3-fold OD-characterizable; L.S3 is 6-fold OD-characterizable.展开更多
Discovering regularities between entities in temporal graphs is vital for many real-world applications(e.g.,social recommendation,emergency event detection,and cyberattack event detection).This paper proposes temporal...Discovering regularities between entities in temporal graphs is vital for many real-world applications(e.g.,social recommendation,emergency event detection,and cyberattack event detection).This paper proposes temporal graph association rules(TGARs)that extend traditional graph-pattern association rules in a static graph by incorporating the unique temporal information and constraints.We introduce quality measures(e.g.,support,confidence,and diversification)to characterize meaningful TGARs that are useful and diversified.In addition,the proposed support metric is an upper bound for alternative metrics,allowing us to guarantee a superset of patterns.We extend conventional confidence measures in terms of maximal occurrences of TGARs.The diversification score strikes a balance between interestingness and diversity.Although the problem is NP-hard,we develop an effective discovery algorithm for TGARs that integrates TGARs generation and TGARs selection and shows that mining TGARs is feasible over a temporal graph.We propose pruning strategies to filter TGARs that have low support or cannot make top-k as early as possible.Moreover,we design an auxiliary data structure to prune the TGARs that do not meet the constraints during the TGARs generation process to avoid conducting repeated subgraph matching for each extension in the search space.We experimentally verify the effectiveness,efficiency,and scalability of our algorithms in discovering diversified top-k TGARs from temporal graphs in real-life applications.展开更多
Let G be a finite group and π（G） = {pl,p2,…… ,pk} be the set of the primes dividing the order of G. We define its prime graph F（G） as follows. The vertex set of this graph is 7r（G）, and two distinct vertices ...Let G be a finite group and π（G） = {pl,p2,…… ,pk} be the set of the primes dividing the order of G. We define its prime graph F（G） as follows. The vertex set of this graph is 7r（G）, and two distinct vertices p, q are joined by an edge if and only if pq ∈ πe（G）. In this case, we write p - q. For p ∈π（G）, put deg（p） ：= ｜{q ∈ π（G）｜p - q}｜, which is called the degree of p. We also define D（G） ：= （deg（p1）, deg（p2）,..., deg（pk））, where pl 〈 p2 〈 -……〈 pk, which is called the degree pattern of G. We say a group G is k-fold OD-characterizable if there exist exactly k non-isomorphic finite groups with the same order and degree pattern as G. Specially, a l-fold OD-characterizable group is simply called an OD-characterizable group. Let L ：= U6（2）. In this article, we classify all finite groups with the same order and degree pattern as an almost simple groups related to L. In fact, we prove that L and L.2 are OD-characterizable, L.3 is 3-fold OD-characterizable, and L.S3 is 5-fold OD-characterizable.展开更多
文摘很多频繁子图挖掘算法已被提出.然而,这些算法产生的频繁子图数量太多而不能被用户有效地利用.为此,提出了一个新的研究问题:挖掘图数据库中的频繁跳跃模式.挖掘频繁跳跃模式既可以大幅度地减少输出模式的数量,又能使有意义的图模式保留在挖掘结果中.此外,跳跃模式还具有抗噪声干扰能力强等优点.然而,由于跳跃模式不具有反单调性质,挖掘它们非常具有挑战性.通过研究跳跃模式自身的特性,提出了两种新的裁剪技术:基于内扩展的裁剪和基于外扩展的裁剪.在此基础上又给出了一种高效的挖掘算法GraphJP(an algorithm for mining jump patterns from graph databases).另外,还严格证明了裁剪技术和算法GraphJP的正确性.实验结果表明,所提出的裁剪技术能够有效地裁剪图模式搜索空间,算法GraphJP是高效、可扩展的.
基金Supported by National Natural Science Foundation of China (Grant No. 10871032)the SRFDP of China (Grant No. 20660285002)a subproject of National Natural Science Foundation of China (Grant No. 50674008) (Chongqing University, Nos. 104207520080834, 104207520080968)
文摘Let G be a finite group with order ｜G｜=p1^α1p2^α2……pk^αk, where p1 〈 p2 〈……〈 Pk are prime numbers. One of the well-known simple graphs associated with G is the prime graph （or Gruenberg- Kegel graph） denoted .by г（G） （or GK（G））. This graph is constructed as follows： The vertex set of it is π（G） = {p1,p2,…,pk} and two vertices pi, pj with i≠j are adjacent by an edge （and we write pi - pj） if and only if G contains an element of order pipj. The degree deg（pi） of a vertex pj ∈π（G） is the number of edges incident on pi. We define D（G） ：= （deg（p1）, deg（p2）,..., deg（pk））, which is called the degree pattern of G. A group G is called k-fold OD-characterizable if there exist exactly k non- isomorphic groups H such that ｜H｜ = ｜G｜ and D（H） = D（G）. Moreover, a 1-fold OD-characterizable group is simply called OD-characterizable. Let L ：= U3（5） be the projective special unitary group. In this paper, we classify groups with the same order and degree pattern as an almost simple group related to L. In fact, we obtain that L and L.2 are OD-characterizable; L.3 is 3-fold OD-characterizable; L.S3 is 6-fold OD-characterizable.
基金This work was partially supported by the National Key Research and Development Program(No.2018YFB1800203)National Natural Science Foundation of China(No.U19B2024)Postgraduate Scientific Research Innovation Project of Hunan Province(No.CX20210038).
文摘Discovering regularities between entities in temporal graphs is vital for many real-world applications(e.g.,social recommendation,emergency event detection,and cyberattack event detection).This paper proposes temporal graph association rules(TGARs)that extend traditional graph-pattern association rules in a static graph by incorporating the unique temporal information and constraints.We introduce quality measures(e.g.,support,confidence,and diversification)to characterize meaningful TGARs that are useful and diversified.In addition,the proposed support metric is an upper bound for alternative metrics,allowing us to guarantee a superset of patterns.We extend conventional confidence measures in terms of maximal occurrences of TGARs.The diversification score strikes a balance between interestingness and diversity.Although the problem is NP-hard,we develop an effective discovery algorithm for TGARs that integrates TGARs generation and TGARs selection and shows that mining TGARs is feasible over a temporal graph.We propose pruning strategies to filter TGARs that have low support or cannot make top-k as early as possible.Moreover,we design an auxiliary data structure to prune the TGARs that do not meet the constraints during the TGARs generation process to avoid conducting repeated subgraph matching for each extension in the search space.We experimentally verify the effectiveness,efficiency,and scalability of our algorithms in discovering diversified top-k TGARs from temporal graphs in real-life applications.
基金supported by Natural Science Foundation Project of CQ CSTC (2010BB9206)NNSF of China (10871032)+1 种基金Fundamental Research Funds for the Central Universities (Chongqing University, CDJZR10100009)National Science Foundation for Distinguished Young Scholars of China (11001226)
文摘Let G be a finite group and π（G） = {pl,p2,…… ,pk} be the set of the primes dividing the order of G. We define its prime graph F（G） as follows. The vertex set of this graph is 7r（G）, and two distinct vertices p, q are joined by an edge if and only if pq ∈ πe（G）. In this case, we write p - q. For p ∈π（G）, put deg（p） ：= ｜{q ∈ π（G）｜p - q}｜, which is called the degree of p. We also define D（G） ：= （deg（p1）, deg（p2）,..., deg（pk））, where pl 〈 p2 〈 -……〈 pk, which is called the degree pattern of G. We say a group G is k-fold OD-characterizable if there exist exactly k non-isomorphic finite groups with the same order and degree pattern as G. Specially, a l-fold OD-characterizable group is simply called an OD-characterizable group. Let L ：= U6（2）. In this article, we classify all finite groups with the same order and degree pattern as an almost simple groups related to L. In fact, we prove that L and L.2 are OD-characterizable, L.3 is 3-fold OD-characterizable, and L.S3 is 5-fold OD-characterizable.
