The Erdös-Faber-Lovász Conjecture for Gap-Restricted 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.

基于Hypergraph的突发事件情景案例表示与检索方法研究

[研究目的]突发事件具有情景演化特征,突发事件案例不仅要对单个情景特征进行描述,也要描述不同情景之间的演化关系。[研究方法]在对突发事件情景演化机理和情景案例特征分析基础上,引入超图理论,将其应用于突发事件情景案例表示,建立了突发事件情景链超图模型,并基于该模型提出了包括情景链检索和情景特征检索的两阶段检索策略和相应的相似度计算方法。[研究结论]该模型能够有效描述突发事件情景案例的复杂演化特征,并能提高案例检索的质量和效果。

Brain Functional Networks with Dynamic Hypergraph Manifold Regularization for Classification of End-Stage Renal Disease Associated with Mild Cognitive Impairment

The structure and function of brain networks have been altered in patients with end-stage renal disease(ESRD).Manifold regularization(MR)only considers the pairing relationship between two brain regions and cannot represent functional interactions or higher-order relationships between multiple brain regions.To solve this issue,we developed a method to construct a dynamic brain functional network(DBFN)based on dynamic hypergraph MR(DHMR)and applied it to the classification of ESRD associated with mild cognitive impairment(ESRDaMCI).The construction of DBFN with Pearson’s correlation(PC)was transformed into an optimization model.Node convolution and hyperedge convolution superposition were adopted to dynamically modify the hypergraph structure,and then got the dynamic hypergraph to form the manifold regular terms of the dynamic hypergraph.The DHMR and L_(1) norm regularization were introduced into the PC-based optimization model to obtain the final DHMR-based DBFN(DDBFN).Experiment results demonstrated the validity of the DDBFN method by comparing the classification results with several related brain functional network construction methods.Our work not only improves better classification performance but also reveals the discriminative regions of ESRDaMCI,providing a reference for clinical research and auxiliary diagnosis of concomitant cognitive impairments.

Diverse Deep Matrix Factorization With Hypergraph Regularization for Multi-View Data Representation

Deep matrix factorization(DMF)has been demonstrated to be a powerful tool to take in the complex hierarchical information of multi-view data(MDR).However,existing multiview DMF methods mainly explore the consistency of multi-view data,while neglecting the diversity among different views as well as the high-order relationships of data,resulting in the loss of valuable complementary information.In this paper,we design a hypergraph regularized diverse deep matrix factorization(HDDMF)model for multi-view data representation,to jointly utilize multi-view diversity and a high-order manifold in a multilayer factorization framework.A novel diversity enhancement term is designed to exploit the structural complementarity between different views of data.Hypergraph regularization is utilized to preserve the high-order geometry structure of data in each view.An efficient iterative optimization algorithm is developed to solve the proposed model with theoretical convergence analysis.Experimental results on five real-world data sets demonstrate that the proposed method significantly outperforms stateof-the-art multi-view learning approaches.

Load-Aware VM Migration Using Hypergraph Based CDB-LSTM

Live Virtual Machine(VM)migration is one of the foremost techniques for progressing Cloud Data Centers’(CDC)proficiency as it leads to better resource usage.The workload of CDC is often dynamic in nature,it is better to envisage the upcoming workload for early detection of overload status,underload status and to trigger the migration at an appropriate point wherein enough number of resources are available.Though various statistical and machine learning approaches are widely applied for resource usage prediction,they often failed to handle the increase of non-linear CDC data.To overcome this issue,a novel Hypergrah based Convolutional Deep Bi-Directional-Long Short Term Memory(CDB-LSTM)model is proposed.The CDB-LSTM adopts Helly property of Hypergraph and Savitzky–Golay(SG)filter to select informative samples and exclude noisy inference&outliers.The proposed approach optimizes resource usage prediction and reduces the number of migrations with minimal computa-tional complexity during live VM migration.Further,the proposed prediction approach implements the correlation co-efficient measure to select the appropriate destination server for VM migration.A Hypergraph based CDB-LSTM was vali-dated using Google cluster dataset and compared with state-of-the-art approaches in terms of various evaluation metrics.

A Nonlinear Spatiotemporal Optimization Method of Hypergraph Convolution Networks for Traffic Prediction

Traffic prediction is a necessary function in intelligent transporta-tion systems to alleviate traffic congestion.Graph learning methods mainly focus on the spatiotemporal dimension,but ignore the nonlinear movement of traffic prediction and the high-order relationships among various kinds of road segments.There exist two issues:1)deep integration of the spatiotempo-ral information and 2)global spatial dependencies for structural properties.To address these issues,we propose a nonlinear spatiotemporal optimization method,which introduces hypergraph convolution networks(HGCN).The method utilizes the higher-order spatial features of the road network captured by HGCN,and dynamically integrates them with the historical data to weigh the influence of spatiotemporal dependencies.On this basis,an extended Kalman filter is used to improve the accuracy of traffic prediction.In this study,a set of experiments were conducted on the real-world dataset in Chengdu,China.The result showed that the proposed method is feasible and accurate by two different time steps.Especially at the 15-minute time step,compared with the second-best method,the proposed method achieved 3.0%,11.7%,and 9.0%improvements in RMSE,MAE,and MAPE,respectively.

Hypergraph Regularized Deep Autoencoder for Unsupervised Unmixing Hyperspectral Images

Deep learning(DL)has shown its superior performance in dealing with various computer vision tasks in recent years.As a simple and effective DL model,autoencoder(AE)is popularly used to decompose hyperspectral images(HSIs)due to its powerful ability of feature extraction and data reconstruction.However,most existing AE-based unmixing algorithms usually ignore the spatial information of HSIs.To solve this problem,a hypergraph regularized deep autoencoder(HGAE)is proposed for unmixing.Firstly,the traditional AE architecture is specifically improved as an unsupervised unmixing framework.Secondly,hypergraph learning is employed to reformulate the loss function,which facilitates the expression of high-order similarity among locally neighboring pixels and promotes the consistency of their abundances.Moreover,L_(1/2)norm is further used to enhance abundances sparsity.Finally,the experiments on simulated data,real hyperspectral remote sensing images,and textile cloth images are used to verify that the proposed method can perform better than several state-of-the-art unmixing algorithms.

The Rupture Degree of <i>k</i>-Uniform Linear Hypergraph

We employ graph parameter, the rupture degree, to measure the vulnerability of k-uniform hypergraph Gk. For the k-uniform hypergraph Gk underlying a non-complete graph G = (V, E), its rupture degree r(Gk) is defined as r(Gk) = max{ω(Gk - X) - |X| - m(Gk - X): X ⊂ V(Gk), ω(Gk - X) > 1}, where X is a cut set (or destruction strategy) of Gk, ω(Gk - X) and m(Gk - X) denote the number of components and the order of a largest component in Gk - X, respectively. It is shown that this parameter can be used to measure the vulnerability of networks. In this paper, the rupture degrees of several specific classes of k-uniform hypergraph are determined.

New Clustering Method in High-Di mensional Space Based on Hypergraph-Models

To overcome the limitation of the traditional clustering algorithms which fail to produce meaningful clusters in high-dimensional, sparseness and binary value data sets, a new method based on hypergraph model is proposed. The hypergraph model maps the relationship present in the original data in high dimensional space into a hypergraph. A hyperedge represents the similarity of attrlbute-value distribution between two points. A hypergraph partitioning algorithm is used to find a partitioning of the vertices such that the corresponding data items in each partition are highly related and the weight of the hyperedges cut by the partitioning is minimized. The quality of the clustering result can be evaluated by applying the intra-cluster singularity value. Analysis and experimental results have demonstrated that this approach is applicable and effective in wide ranging scheme.

Data-driven Product Functional Confguration:Patent Data and Hypergraph

The product functional confguration(PFC)is typically used by frms to satisfy the individual requirements of customers and is realized based on market analysis.This study aims to help frms analyze functions and realize functional confgurations using patent data.This study frst proposes a patent-data-driven PFC method based on a hypergraph network.It then constructs a weighted network model to optimize the combination of product function quantity and object from the perspective of big data,as follows:(1)The functional knowledge contained in the patent is extracted.(2)The functional hypergraph is constructed based on the co-occurrence relationship between patents and applicants.(3)The function and patent weight are calculated from the patent applicant’s perspective and patent value.(4)A weight calculation model of the PFC is developed.(5)The weighted frequent subgraph algorithm is used to obtain the optimal function combination list.This method is applied to an innovative design process of a bathroom shower.The results indicate that this method can help frms detach optimal function candidates and develop a multifunctional product.

Study on the P2P Cloud Storage Architecture Based on Semantic Hypergraph

Cloud storage has the characteristics of distributed and virtual, and it makes the ownership rights and management rights of users data separated. The master-slave architecture of cloud storage has a problem of single point failure. In this paper, we provide a cloud storage architecture model based on Semantic equivalence. According to semantic matching degree, this architecture divides the nodes into node cluster by creating semantic tree and maintains system routing through semantic hypergraph. Through simulation experiments show that dividing network into semantic can enhance scalability and flexibility of the system, and it can improve the efficiency of network organization and the security of cloud storage system, at the same time, it can also reduce the cloud data storage and the delay of reading time.

RELATIONS AMONG SOME PARAMETERS OF HYPERGRAPHS

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.

Robust Deep 3D Convolutional Autoencoder for Hyperspectral Unmixing with Hypergraph Learning

Hyperspectral unmixing aims to acquire pure spectra of distinct substances(endmembers)and fractional abundances from highly mixed pixels.In this paper,a deep unmixing network framework is designed to deal with the noise disturbance.It contains two parts:a three⁃dimensional convolutional autoencoder(denoising 3D CAE)which recovers data from noised input,and a restrictive non⁃negative sparse autoencoder(NNSAE)which incorporates a hypergraph regularizer as well as a l2,1⁃norm sparsity constraint to improve the unmixing performance.The deep denoising 3D CAE network was constructed for noisy data retrieval,and had strong capacity of extracting the principle and robust local features in spatial and spectral domains efficiently by training with corrupted data.Furthermore,a part⁃based nonnegative sparse autoencoder with l2,1⁃norm penalty was concatenated,and a hypergraph regularizer was designed elaborately to represent similarity of neighboring pixels in spatial dimensions.Comparative experiments were conducted on synthetic and real⁃world data,which both demonstrate the effectiveness and robustness of the proposed network.

Make U-Net Greater: An Easy-to-Embed Approach to Improve Segmentation Performance Using Hypergraph

semantics information while maintaining spatial detail con-texts.Long-range context information plays a crucial role in this scenario.How-ever,the traditional convolution kernel only provides the local and small size of the receptivefield.To address the problem,we propose a plug-and-play module aggregating both local and global information(aka LGIA module)to capture the high-order relationship between nodes that are far apart.We incorporate both local and global correlations into hypergraph which is able to capture high-order rela-tionships between nodes via the concept of a hyperedge connecting a subset of nodes.The local correlation considers neighborhood nodes that are spatially adja-cent and similar in the same CNN feature maps of magnetic resonance(MR)image;and the global correlation is searched from a batch of CNN feature maps of MR images in feature space.The influence of these two correlations on seman-tic segmentation is complementary.We validated our LGIA module on various CNN segmentation models with the cardiac MR images dataset.Experimental results demonstrate that our approach outperformed several baseline models.

The Spectral Radii of Intersecting Uniform Hypergraphs

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.

Hypergraph-Based Data Reduced Scheduling Policy for Data-Intensive Workflow in Clouds

Data-intensive computing is expected to be the next-generation IT computing paradigm. Data-intensive workflows in clouds are becoming more and more popular. How to schedule data-intensive workflow efficiently has become the key issue. In this paper, first, we build a directed hypergraph model for data-intensive workflow, since Hypergraphs can more accurately model communication volume and better represent asymmetric problems, and the cut metric of hypergraphs is well suited for minimizing the total volume of communication.Second, we propose a concept data supportive ability to help the presentation of data-intensive workflow application and provide the merge operation details considering the data supportive ability. Third, we present an optimized hypergraph multi-level partitioning algorithm. Finally we bring a data reduced scheduling policy HEFT-P for data-intensive workflow. Through simulation,we compare HEFT-P with three typical workflow scheduling policies.The results indicate that HEFT-P could obtain reduced data scheduling and reduce the makespan of executing data-intensive

Hypergraph-based Object-oriented Model and Hypergraph Theory for GIS

This paper discusses the features and relevant theories of GIS spatial data model based on hypergraph,etc.The integrated concept model based on hypergraph and object_oriented model (HOOM) is proposed by the authors.The principal contribution of this paper is that we study the K_section and other theories of hypergraph.An application example using HOOM is given at the end of the paper.

Hypergraph High-Dimension Clustering Algorithm for Optimized Cooperative Wireless Multicast

In order to guarantee the wireless multicast throughput at a minimum cost, we propose a layered hypergraph high-dimension clustering algorithm (LayerHC) considering the channels and statistical locations of mobile members. The algorithm can achieve a minimum multicast spanning tree to obtain a minimum number of relays and effective cooperative areas with low computational complexity.

A Key Management Scheme Based on Hypergraph for Fog Computing

Fog computing is a new paradigm supporting the stringent requirements of mobility applications by bridging cloud computing and smart devices. Since the smart devices may be deployed in dynamic areas where are out of strict monitoring and protection, fog computing requires security protections to ensure confidentiality and integrity. In this article, to deal with security requirements and considering the distinctive features, a key management based on hypergraph schemed is designed. Firstly, based on the key hypergraph, the three hierarchy architecture of fog computing is divided into two subnetworks. Furthermore, each key management process of both two subnetworks is designed to satisfy the operational and security requirements of fog computing. Finally, the performance evaluation and numerical simulation have been provided to validate the proposed scheme.

Random Hypergraphs and Subset Systems

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.