Let H be a hypergraph with vertex set V(H)and hyperedge set E(H).We call a vertex set R ■V(H)a transversal if it has a nonempty intersection with every hyperedge of H.The transversal number,denoted by τ(H),is the mi...Let H be a hypergraph with vertex set V(H)and hyperedge set E(H).We call a vertex set R ■V(H)a transversal if it has a nonempty intersection with every hyperedge of H.The transversal number,denoted by τ(H),is the minimum cardinality of transversals.In 2021,Diao verified that the upper bound of transversal number for any connected 3-uniform hypergraph H is at most 2m+1/3,that is,τ(H)≤2m+1/3, where m is the size of H.Moreover,they gave the necessary and sufficient conditions to reachthe upper bound,namely τ(H)≤2m+1/3,if and only if H is a hypertreewitha 3 perfect matching.In this paper,we investigate the transversal number of connected kunifom hypergraphs for k≥3.We confrm that τ(H)≤(k-1)m+1/k for any k-unifom hypegraphH with size m.Furthermore,we show that τ(H)≤(k-1)m+1/k if and only if H is a hypertree with a perfect matching,which generalizes the results of Diao.展开更多
Complex networks play a crucial role in the study of collective behavior,encompassing the analysis of dynamical properties and network topology.In real-world systems,higher-order interactions among multiple entities a...Complex networks play a crucial role in the study of collective behavior,encompassing the analysis of dynamical properties and network topology.In real-world systems,higher-order interactions among multiple entities are widespread and significantly influence collective dynamics.Here,we extend the synchronization alignment function framework to hypergraphs of arbitrary order by leveraging the multi-order Laplacian matrix to encode higher-order interactions.Our findings reveal that the upper bound of synchronous behavior is determined by the maximum eigenvalue of the multi-order Laplacian matrix.Furthermore,we decompose the contribution of each hyperedge to this eigenvalue and utilize it as a basis for designing an eigenvalue-based topology modification algorithm.This algorithm effectively enhances the upper bound of synchronous behavior without altering the total number of higher-order interactions.Our study provides new insights into dynamical optimization and topology tuning in hypergraphs,advancing the understanding of the interplay between higher-order interactions and collective dynamics.展开更多
Let SI and S2 be two （k- 1）-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E（H） such that S1 ∩ e≠ 0 and S2 ∩ e ≠0 or e S1 ∪...Let SI and S2 be two （k- 1）-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E（H） such that S1 ∩ e≠ 0 and S2 ∩ e ≠0 or e S1 ∪ S2 or e S1 ∪ S2, respectively. In this paper, we obtain the following results concerning these three independence. （1） For any n ≥ 2k2 - k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent （k - 1）-sets equal to 2n - 4（k - 1）, contains no perfect matching; （2） Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd＋ （k- 2）k. If the degree sum of any two middle independent （k- 1）-subsets is larger than 2（d- 1）, then H contains a d-matching; （3） For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent （k - 1）-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n.展开更多
Hypergraphs,which encapsulate interactions of higher-order beyond mere pairwise connections,are essential for representing polyadic relationships within complex systems.Consequently,an increasing number of researchers...Hypergraphs,which encapsulate interactions of higher-order beyond mere pairwise connections,are essential for representing polyadic relationships within complex systems.Consequently,an increasing number of researchers are focusing on the centrality problem in hypergraphs.Specifically,researchers are tackling the challenge of utilizing higher-order structures to effectively define centrality metrics.This paper presents a novel approach,LGK,derived from the K-shell decomposition method,which incorporates both global and local perspectives.Empirical evaluations indicate that the LGK method provides several advantages,including reduced time complexity and improved accuracy in identifying critical nodes in hypergraphs.展开更多
The problem of decomposing a complete 3-uniform hypergraph into Hamilton cycles was introduced by Bailey and Stevens using a generalization of Hamiltonian chain to uniform hypergraphs by Katona and Kierstead. Decompos...The problem of decomposing a complete 3-uniform hypergraph into Hamilton cycles was introduced by Bailey and Stevens using a generalization of Hamiltonian chain to uniform hypergraphs by Katona and Kierstead. Decomposing the complete 3-uniform hypergraphs Kn（3） into k-cycles （3 ≤ k 〈 n） was then considered by Meszka and Rosa. This study investigates this problem using a difference pattern of combinatorics and shows that Kn·5m（3） can be decomposed into 5-cycles for n ∈ {5, 7, 10, 11, 16, 17, 20, 22, 26} using computer programming.展开更多
In this paper, we consider the r-uniform hypergraphs H with spectral radius at most ■. We show that H must have a quipus-structure, which is similar to the graphs with spectral radius at most ■ [Woo-Neumaier, Graphs...In this paper, we consider the r-uniform hypergraphs H with spectral radius at most ■. We show that H must have a quipus-structure, which is similar to the graphs with spectral radius at most ■ [Woo-Neumaier, Graphs Combin. 2007].展开更多
The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T...The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T（H）, p（H）}; DT（H） ≤αT（H）; S（H）≤ Dv （H） ＋ α（H）≤n; 2≤ Dv （H） ＋ T（H） ≤n; 2 〈 Dv （H） ＋ v（H）≤n/2 ＋ [n/r]; Dv （H） ＋ p（H） 〈_n;2≤De（H） ＋ Dv（H）≤n/2 ＋ [n/r];α（H） ＋ De（H）≤n;2 ≤ De（H） ＋ v（H）≤2[n/r]; 2 De（H） ＋ p（H）≤n-r ＋ 2.展开更多
It is proved in this paper that if G is a simple connected r-uniform hypergraph with ｜｜G｜｜≥2, then G has an edge e such that G - e - V1（e） is also a simple connected r-uniform hypergraph. This reduction is natu...It is proved in this paper that if G is a simple connected r-uniform hypergraph with ｜｜G｜｜≥2, then G has an edge e such that G - e - V1（e） is also a simple connected r-uniform hypergraph. This reduction is naturally called a combined Graham reduction. Under the simple reductions of single edge removals and single edge contractions, the minor minimal connected simple r-uniform hypergraphs are also determined.展开更多
Suppose to toss an independent coin with equal probability of success and failure for each subset of [n] = {1, 2, ..., n}, and form the random hypergraph H(n) by taking as hyperedges the subsets with successful coin t...Suppose to toss an independent coin with equal probability of success and failure for each subset of [n] = {1, 2, ..., n}, and form the random hypergraph H(n) by taking as hyperedges the subsets with successful coin tosses. It is proved that H(n) is almost surely connected. By defining a graph G(S) according to a subset system S, it is shown that the intersecting problem is NP-complete.展开更多
In this paper, we set ρ_r =~r4^（1/2） and ρ′_r= β^（-1/r）, where β =-1/6 ·（100 ＋ 12·（69）^（1/2））^（1/3）-2/（3·（100＋12·（69）^（1/2）））^（1/3）＋4/3≈0.2451223338. We consider conn...In this paper, we set ρ_r =~r4^（1/2） and ρ′_r= β^（-1/r）, where β =-1/6 ·（100 ＋ 12·（69）^（1/2））^（1/3）-2/（3·（100＋12·（69）^（1/2）））^（1/3）＋4/3≈0.2451223338. We consider connected r-uniform hypergraphs with spectral radius between ρ_r and ρ′_r and give a description of such hypergraphs.展开更多
A k-edge coloring of a hypergraph H is a coloring of the edges of H with k colors such that any two intersecting edges receive distinct colors. The Erdos-Faber-Lovasz conjecture states that every loopless linear hyper...A k-edge coloring of a hypergraph H is a coloring of the edges of H with k colors such that any two intersecting edges receive distinct colors. The Erdos-Faber-Lovasz conjecture states that every loopless linear hypergraph with n vertices has an n-edge coloring. In 2021,Kang, Kelly, K¨uhn, Methuku and Osthus confirmed the conjecture for sufficiently large n. In this paper, the conjecture is verified for collision-weak hypergraphs. This result strictly extends two related ones of Bretto, Faisant and Hennecart in 2020.展开更多
This paper mainly studies the influence maximization problem of threshold models in hypergraphs,which aims to identify the most influential nodes in hypergraphs.Firstly,we introduce a novel information diffusion rule ...This paper mainly studies the influence maximization problem of threshold models in hypergraphs,which aims to identify the most influential nodes in hypergraphs.Firstly,we introduce a novel information diffusion rule in hypergraphs based on Threshold Models and conduct the stability analysis.Then we extend the CI-TM algorithm,originally designed for complex networks,to hypergraphs,denoted as the H-CI-TM algorithm.Secondly,we use an iterative approach to get the globally optimal solutions.The analysis reveals that our algorithm ultimately identifies the most influential set of nodes.Based on the numerical simulations,HCI-TM algorithm outperforms several competing algorithms in both synthetic and real-world hypergraphs.Essentially,when provided with the same number of initial seeds,our algorithm can achieve a larger activation size.Our method not only accurately assesses the influence of individual nodes but also identifies a set of nodes with greater impact.Furthermore,our results demonstrate good scalability when handling intricate relationships and large-scale hypergraphs.The outcomes of our research provide substantial support for the applications of the threshold models across diverse fields,including social network analysis and marketing strategies.展开更多
The celebrated Erdos-Ko-Rado theorem states that given n≥2k,every intersecting k-uni-n-1 form hypergraph G on n vertices has at most(n-1 k-1)edges.This paper states spectral versions of the Erd6s-_Ko--Rado theorem:le...The celebrated Erdos-Ko-Rado theorem states that given n≥2k,every intersecting k-uni-n-1 form hypergraph G on n vertices has at most(n-1 k-1)edges.This paper states spectral versions of the Erd6s-_Ko--Rado theorem:let G be an intersecting k-uniform hypergraph on n vertices with n≥2k.Then,the sharp upper bounds for the spectral radius of Aα(G)and 2*(G)are presented,where Aα(G)=αD(G)+(1-α).A(G)is a convex linear combination of the degree diagonal tensor D(G)and the adjacency tensor A(G)for 0≤α<1,and Q^(*)(G)is the incidence Q-tensor,respectively.Furthermore,when n>2k,the extremal hypergraphs which attain the sharp upper bounds are characterized.The proof mainly relies on the Perron-Frobenius theorem for nonnegative tensor and the property of the maximizing connected hypergraphs.展开更多
An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromatic index of H and is ...An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromatic index of H and is denoted by . Erdös, Faber and Lovász proposed a famous conjecture that holds for any loopless linear hypergraph H with n vertices. In this paper, we show that is true for gap-restricted hypergraphs. Our result extends a result of Alesandroni in 2021.展开更多
This paper studies the problem of the spectral radius of the uniform hypergraph determined by the signless Laplacian matrix.The upper bound of the spectral radius of a uniform hypergraph is obtained by using Rayleigh ...This paper studies the problem of the spectral radius of the uniform hypergraph determined by the signless Laplacian matrix.The upper bound of the spectral radius of a uniform hypergraph is obtained by using Rayleigh principle and the perturbation of the spectral radius under moving the edge operation,and the extremal hypergraphs are characterized for both supertree and unicyclic hypergraphs.The spectral radius of the graph is generalized.展开更多
Due to self-occlusion and high degree of freedom,estimating 3D hand pose from a single RGB image is a great challenging problem.Graph convolutional networks(GCNs)use graphs to describe the physical connection relation...Due to self-occlusion and high degree of freedom,estimating 3D hand pose from a single RGB image is a great challenging problem.Graph convolutional networks(GCNs)use graphs to describe the physical connection relationships between hand joints and improve the accuracy of 3D hand pose regression.However,GCNs cannot effectively describe the relationships between non-adjacent hand joints.Recently,hypergraph convolutional networks(HGCNs)have received much attention as they can describe multi-dimensional relationships between nodes through hyperedges;therefore,this paper proposes a framework for 3D hand pose estimation based on HGCN,which can better extract correlated relationships between adjacent and non-adjacent hand joints.To overcome the shortcomings of predefined hypergraph structures,a kind of dynamic hypergraph convolutional network is proposed,in which hyperedges are constructed dynamically based on hand joint feature similarity.To better explore the local semantic relationships between nodes,a kind of semantic dynamic hypergraph convolution is proposed.The proposed method is evaluated on publicly available benchmark datasets.Qualitative and quantitative experimental results both show that the proposed HGCN and improved methods for 3D hand pose estimation are better than GCN,and achieve state-of-the-art performance compared with existing methods.展开更多
This paper focuses on the problem of traffic flow forecasting,with the aim of forecasting future traffic conditions based on historical traffic data.This problem is typically tackled by utilizing spatio-temporal graph...This paper focuses on the problem of traffic flow forecasting,with the aim of forecasting future traffic conditions based on historical traffic data.This problem is typically tackled by utilizing spatio-temporal graph neural networks to model the intricate spatio-temporal correlations among traffic data.Although these methods have achieved performance improvements,they often suffer from the following limitations:These methods face challenges in modeling high-order correlations between nodes.These methods overlook the interactions between nodes at different scales.To tackle these issues,in this paper,we propose a novel model named multi-scale dynamic hypergraph convolutional network(MSDHGCN)for traffic flow forecasting.Our MSDHGCN can effectively model the dynamic higher-order relationships between nodes at multiple time scales,thereby enhancing the capability for traffic forecasting.Experiments on two real-world datasets demonstrate the effectiveness of the proposed method.展开更多
Graph labeling is the assignment of integers to the vertices,edges,or both,subject to certain conditions.Accordingly,hypergraph labeling is also the assignment of integers to the vertices,edges,or both,subject to cert...Graph labeling is the assignment of integers to the vertices,edges,or both,subject to certain conditions.Accordingly,hypergraph labeling is also the assignment of integers to the vertices,edges,or both,subject to certain conditions.This paper is to generalize the coprime labelings of graph to hypergraph.We give the definition of coprime labelings of hypergraph.By using Rosser-Schoenfeld's inequality and the coprime mapping theorem of Pomerance and Selfridge,we prove that some linear hypergraphs are prime.展开更多
Hypergraphs can accurately capture complex higher-order relationships,but it is challenging to identify their important nodes.In this paper,an improved PageRank(ImPageRank)algorithm is designed to identify important n...Hypergraphs can accurately capture complex higher-order relationships,but it is challenging to identify their important nodes.In this paper,an improved PageRank(ImPageRank)algorithm is designed to identify important nodes in a directed hypergraph.The algorithm introduces the Jaccard similarity of directed hypergraphs.By comparing the numbers of common neighbors between nodes with the total number of their neighbors,the Jaccard similarity measure takes into account the similarity between nodes that are not directly connected,and can reflect the potential correlation between nodes.An improved susceptible–infected(SI)model in directed hypergraph is proposed,which considers nonlinear propagation mode and more realistic propagation mechanism.In addition,some important node evaluation methods are transferred from undirected hypergraphs and applied to directed hypergraphs.Finally,the ImPageRank algorithm is used to evaluate the performance of the SI model,network robustness and monotonicity.Simulations of real networks demonstrate the excellent performance of the proposed algorithm and provide a powerful framework for identifying important nodes in directed hypergraphs.展开更多
Unlike traditional video cameras,event cameras capture asynchronous event streams in which each event encodes pixel location,triggers’timestamps,and the polarity of brightness changes.In this paper,we introduce a nov...Unlike traditional video cameras,event cameras capture asynchronous event streams in which each event encodes pixel location,triggers’timestamps,and the polarity of brightness changes.In this paper,we introduce a novel hypergraph-based framework for moving object classification.Specifically,we capture moving objects with an event camera,to perceive and collect asynchronous event streams in a high temporal resolution.Unlike stacked event frames,we encode asynchronous event data into a hypergraph,fully mining the high-order correlation of event data,and designing a mixed convolutional hypergraph neural network for training to achieve a more efficient and accurate motion target recognition.The experimental results show that our method has a good performance in moving object classification(e.g.,gait identification).展开更多
基金supported by the National Natural Science Foundation of China(No.12171089).
文摘Let H be a hypergraph with vertex set V(H)and hyperedge set E(H).We call a vertex set R ■V(H)a transversal if it has a nonempty intersection with every hyperedge of H.The transversal number,denoted by τ(H),is the minimum cardinality of transversals.In 2021,Diao verified that the upper bound of transversal number for any connected 3-uniform hypergraph H is at most 2m+1/3,that is,τ(H)≤2m+1/3, where m is the size of H.Moreover,they gave the necessary and sufficient conditions to reachthe upper bound,namely τ(H)≤2m+1/3,if and only if H is a hypertreewitha 3 perfect matching.In this paper,we investigate the transversal number of connected kunifom hypergraphs for k≥3.We confrm that τ(H)≤(k-1)m+1/k for any k-unifom hypegraphH with size m.Furthermore,we show that τ(H)≤(k-1)m+1/k if and only if H is a hypertree with a perfect matching,which generalizes the results of Diao.
基金Project supported by the National Natural Science Foundation of China(Grant Nos.12247153,T2293771,and 12247101)the Zhejiang Provincial Natural Science Foundation of China(Grant No.LTGY24A050002)+3 种基金the Sichuan Science and Technology Program(Grant Nos.2024NSFSC1364 and 2023NSFSC1919)the Project of Huzhou Science and Technology Bureau(Grant No.2022YZ29)the UESTCYDRI research start-up(Grant No.U03210066)the New Cornerstone Science Foundation through the Xplorer Prize。
文摘Complex networks play a crucial role in the study of collective behavior,encompassing the analysis of dynamical properties and network topology.In real-world systems,higher-order interactions among multiple entities are widespread and significantly influence collective dynamics.Here,we extend the synchronization alignment function framework to hypergraphs of arbitrary order by leveraging the multi-order Laplacian matrix to encode higher-order interactions.Our findings reveal that the upper bound of synchronous behavior is determined by the maximum eigenvalue of the multi-order Laplacian matrix.Furthermore,we decompose the contribution of each hyperedge to this eigenvalue and utilize it as a basis for designing an eigenvalue-based topology modification algorithm.This algorithm effectively enhances the upper bound of synchronous behavior without altering the total number of higher-order interactions.Our study provides new insights into dynamical optimization and topology tuning in hypergraphs,advancing the understanding of the interplay between higher-order interactions and collective dynamics.
基金Supported by National Natural Science Foundation of China(Grant No.11771247)
文摘Let SI and S2 be two （k- 1）-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E（H） such that S1 ∩ e≠ 0 and S2 ∩ e ≠0 or e S1 ∪ S2 or e S1 ∪ S2, respectively. In this paper, we obtain the following results concerning these three independence. （1） For any n ≥ 2k2 - k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent （k - 1）-sets equal to 2n - 4（k - 1）, contains no perfect matching; （2） Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd＋ （k- 2）k. If the degree sum of any two middle independent （k- 1）-subsets is larger than 2（d- 1）, then H contains a d-matching; （3） For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent （k - 1）-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n.
文摘Hypergraphs,which encapsulate interactions of higher-order beyond mere pairwise connections,are essential for representing polyadic relationships within complex systems.Consequently,an increasing number of researchers are focusing on the centrality problem in hypergraphs.Specifically,researchers are tackling the challenge of utilizing higher-order structures to effectively define centrality metrics.This paper presents a novel approach,LGK,derived from the K-shell decomposition method,which incorporates both global and local perspectives.Empirical evaluations indicate that the LGK method provides several advantages,including reduced time complexity and improved accuracy in identifying critical nodes in hypergraphs.
基金Supported by the National Natural Science Foundation of China(Grant No.11161032)
文摘The problem of decomposing a complete 3-uniform hypergraph into Hamilton cycles was introduced by Bailey and Stevens using a generalization of Hamiltonian chain to uniform hypergraphs by Katona and Kierstead. Decomposing the complete 3-uniform hypergraphs Kn（3） into k-cycles （3 ≤ k 〈 n） was then considered by Meszka and Rosa. This study investigates this problem using a difference pattern of combinatorics and shows that Kn·5m（3） can be decomposed into 5-cycles for n ∈ {5, 7, 10, 11, 16, 17, 20, 22, 26} using computer programming.
基金Supported by the National Natural Science Foundation of China(Grant No.11601368)
文摘In this paper, we consider the r-uniform hypergraphs H with spectral radius at most ■. We show that H must have a quipus-structure, which is similar to the graphs with spectral radius at most ■ [Woo-Neumaier, Graphs Combin. 2007].
基金Supported by Ningbo Institute of Technology, Zhejiang Univ. Youth Innovation Foundation and Zhejiang Provincial Natural Science Foundation( Y604167).
文摘The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T（H）, p（H）}; DT（H） ≤αT（H）; S（H）≤ Dv （H） ＋ α（H）≤n; 2≤ Dv （H） ＋ T（H） ≤n; 2 〈 Dv （H） ＋ v（H）≤n/2 ＋ [n/r]; Dv （H） ＋ p（H） 〈_n;2≤De（H） ＋ Dv（H）≤n/2 ＋ [n/r];α（H） ＋ De（H）≤n;2 ≤ De（H） ＋ v（H）≤2[n/r]; 2 De（H） ＋ p（H）≤n-r ＋ 2.
基金Supported by NRF South Africathe National Natural Science Foundation of China(Grant No.11161032)
文摘It is proved in this paper that if G is a simple connected r-uniform hypergraph with ｜｜G｜｜≥2, then G has an edge e such that G - e - V1（e） is also a simple connected r-uniform hypergraph. This reduction is naturally called a combined Graham reduction. Under the simple reductions of single edge removals and single edge contractions, the minor minimal connected simple r-uniform hypergraphs are also determined.
文摘Suppose to toss an independent coin with equal probability of success and failure for each subset of [n] = {1, 2, ..., n}, and form the random hypergraph H(n) by taking as hyperedges the subsets with successful coin tosses. It is proved that H(n) is almost surely connected. By defining a graph G(S) according to a subset system S, it is shown that the intersecting problem is NP-complete.
基金Supported by the National Natural Science Foundation of China(Grant Nos.116013681140143411771322)
文摘In this paper, we set ρ_r =~r4^（1/2） and ρ′_r= β^（-1/r）, where β =-1/6 ·（100 ＋ 12·（69）^（1/2））^（1/3）-2/（3·（100＋12·（69）^（1/2）））^（1/3）＋4/3≈0.2451223338. We consider connected r-uniform hypergraphs with spectral radius between ρ_r and ρ′_r and give a description of such hypergraphs.
基金Supported by the National Natural Science Foundation of China (Grant No. 12071265)the Natural Science Foundation of Shandong Province (Grant No. ZR2019MA032)。
文摘A k-edge coloring of a hypergraph H is a coloring of the edges of H with k colors such that any two intersecting edges receive distinct colors. The Erdos-Faber-Lovasz conjecture states that every loopless linear hypergraph with n vertices has an n-edge coloring. In 2021,Kang, Kelly, K¨uhn, Methuku and Osthus confirmed the conjecture for sufficiently large n. In this paper, the conjecture is verified for collision-weak hypergraphs. This result strictly extends two related ones of Bretto, Faisant and Hennecart in 2020.
基金Supported by the National Natural Science Foundation of China(Grant No.12371516)the Natural Science Foundation of Liaoning Province(Grant No.2022-MS-152)the Fundamental Research Funds for the Central Universities(Grant No.DUT22LAB305)。
文摘This paper mainly studies the influence maximization problem of threshold models in hypergraphs,which aims to identify the most influential nodes in hypergraphs.Firstly,we introduce a novel information diffusion rule in hypergraphs based on Threshold Models and conduct the stability analysis.Then we extend the CI-TM algorithm,originally designed for complex networks,to hypergraphs,denoted as the H-CI-TM algorithm.Secondly,we use an iterative approach to get the globally optimal solutions.The analysis reveals that our algorithm ultimately identifies the most influential set of nodes.Based on the numerical simulations,HCI-TM algorithm outperforms several competing algorithms in both synthetic and real-world hypergraphs.Essentially,when provided with the same number of initial seeds,our algorithm can achieve a larger activation size.Our method not only accurately assesses the influence of individual nodes but also identifies a set of nodes with greater impact.Furthermore,our results demonstrate good scalability when handling intricate relationships and large-scale hypergraphs.The outcomes of our research provide substantial support for the applications of the threshold models across diverse fields,including social network analysis and marketing strategies.
基金the National Natural Science Foundation of China(Nos.11971311,11531001)the Montenegrin-Chinese Science and Technology Cooperation Project(No.3-12).
文摘The celebrated Erdos-Ko-Rado theorem states that given n≥2k,every intersecting k-uni-n-1 form hypergraph G on n vertices has at most(n-1 k-1)edges.This paper states spectral versions of the Erd6s-_Ko--Rado theorem:let G be an intersecting k-uniform hypergraph on n vertices with n≥2k.Then,the sharp upper bounds for the spectral radius of Aα(G)and 2*(G)are presented,where Aα(G)=αD(G)+(1-α).A(G)is a convex linear combination of the degree diagonal tensor D(G)and the adjacency tensor A(G)for 0≤α<1,and Q^(*)(G)is the incidence Q-tensor,respectively.Furthermore,when n>2k,the extremal hypergraphs which attain the sharp upper bounds are characterized.The proof mainly relies on the Perron-Frobenius theorem for nonnegative tensor and the property of the maximizing connected hypergraphs.
文摘An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromatic index of H and is denoted by . Erdös, Faber and Lovász proposed a famous conjecture that holds for any loopless linear hypergraph H with n vertices. In this paper, we show that is true for gap-restricted hypergraphs. Our result extends a result of Alesandroni in 2021.
基金Supported by Natural Science Foundation of HuBei Province(2022CFB299).
文摘This paper studies the problem of the spectral radius of the uniform hypergraph determined by the signless Laplacian matrix.The upper bound of the spectral radius of a uniform hypergraph is obtained by using Rayleigh principle and the perturbation of the spectral radius under moving the edge operation,and the extremal hypergraphs are characterized for both supertree and unicyclic hypergraphs.The spectral radius of the graph is generalized.
基金the National Key Research and Development Program of China(No.2021ZD0111902)the National Natural Science Foundation of China(Nos.62172022 and U21B2038)。
文摘Due to self-occlusion and high degree of freedom,estimating 3D hand pose from a single RGB image is a great challenging problem.Graph convolutional networks(GCNs)use graphs to describe the physical connection relationships between hand joints and improve the accuracy of 3D hand pose regression.However,GCNs cannot effectively describe the relationships between non-adjacent hand joints.Recently,hypergraph convolutional networks(HGCNs)have received much attention as they can describe multi-dimensional relationships between nodes through hyperedges;therefore,this paper proposes a framework for 3D hand pose estimation based on HGCN,which can better extract correlated relationships between adjacent and non-adjacent hand joints.To overcome the shortcomings of predefined hypergraph structures,a kind of dynamic hypergraph convolutional network is proposed,in which hyperedges are constructed dynamically based on hand joint feature similarity.To better explore the local semantic relationships between nodes,a kind of semantic dynamic hypergraph convolution is proposed.The proposed method is evaluated on publicly available benchmark datasets.Qualitative and quantitative experimental results both show that the proposed HGCN and improved methods for 3D hand pose estimation are better than GCN,and achieve state-of-the-art performance compared with existing methods.
基金the National Key Research and Development Program of China(No.2021ZD0112400)。
文摘This paper focuses on the problem of traffic flow forecasting,with the aim of forecasting future traffic conditions based on historical traffic data.This problem is typically tackled by utilizing spatio-temporal graph neural networks to model the intricate spatio-temporal correlations among traffic data.Although these methods have achieved performance improvements,they often suffer from the following limitations:These methods face challenges in modeling high-order correlations between nodes.These methods overlook the interactions between nodes at different scales.To tackle these issues,in this paper,we propose a novel model named multi-scale dynamic hypergraph convolutional network(MSDHGCN)for traffic flow forecasting.Our MSDHGCN can effectively model the dynamic higher-order relationships between nodes at multiple time scales,thereby enhancing the capability for traffic forecasting.Experiments on two real-world datasets demonstrate the effectiveness of the proposed method.
基金Supported by the Natural Science Foundation of Chongqing(CSTB2022NSCQ-MSX0884)。
文摘Graph labeling is the assignment of integers to the vertices,edges,or both,subject to certain conditions.Accordingly,hypergraph labeling is also the assignment of integers to the vertices,edges,or both,subject to certain conditions.This paper is to generalize the coprime labelings of graph to hypergraph.We give the definition of coprime labelings of hypergraph.By using Rosser-Schoenfeld's inequality and the coprime mapping theorem of Pomerance and Selfridge,we prove that some linear hypergraphs are prime.
基金Project supported by the National Natural Science Foundation of China(Grant No.62166010)the Guangxi Natural Science Foundation(Grant No.2023GXNSFAA026087).
文摘Hypergraphs can accurately capture complex higher-order relationships,but it is challenging to identify their important nodes.In this paper,an improved PageRank(ImPageRank)algorithm is designed to identify important nodes in a directed hypergraph.The algorithm introduces the Jaccard similarity of directed hypergraphs.By comparing the numbers of common neighbors between nodes with the total number of their neighbors,the Jaccard similarity measure takes into account the similarity between nodes that are not directly connected,and can reflect the potential correlation between nodes.An improved susceptible–infected(SI)model in directed hypergraph is proposed,which considers nonlinear propagation mode and more realistic propagation mechanism.In addition,some important node evaluation methods are transferred from undirected hypergraphs and applied to directed hypergraphs.Finally,the ImPageRank algorithm is used to evaluate the performance of the SI model,network robustness and monotonicity.Simulations of real networks demonstrate the excellent performance of the proposed algorithm and provide a powerful framework for identifying important nodes in directed hypergraphs.
基金the National Key Research and Development Program of China(No.2021ZD0112400)。
文摘Unlike traditional video cameras,event cameras capture asynchronous event streams in which each event encodes pixel location,triggers’timestamps,and the polarity of brightness changes.In this paper,we introduce a novel hypergraph-based framework for moving object classification.Specifically,we capture moving objects with an event camera,to perceive and collect asynchronous event streams in a high temporal resolution.Unlike stacked event frames,we encode asynchronous event data into a hypergraph,fully mining the high-order correlation of event data,and designing a mixed convolutional hypergraph neural network for training to achieve a more efficient and accurate motion target recognition.The experimental results show that our method has a good performance in moving object classification(e.g.,gait identification).
