On vertex ranking of a starlike graph

A vertex coloring c:V→{1,2,…,t} of a graph G=(V,E) is a vertex t-ranking if for any two vertices of the same color every path between them contains a vertex of larger color. The vertex ranking number χ_r(G) is the smallest value of t such that G has a vertex t-ranking. A χ_r(G)-ranking of G is said to be an optimal vertex ranking. In this paper, we present an O(|V|+|E|) time algorithm for finding an optimal vertex ranking of a starlike graph G=(V,E). Our result implies that an optimal vertex ranking of a split graph can be computed in linear time.     

支持共识决策过程的群排序集结

为了支持共识决策过程,引入最大共识排序概念,设计了基于共识排序树的群排序集结算法。该算法能够从排序数据中发现最大共识排序和需要进一步协商的冲突项目。应用模拟数据进行实验,结果表明了这种计算方法的有效性。     

基于数据图的关系数据库关键词查询排序研究

针对基于数据图的关系数据库关键词查询结果的排序问题, 提出了基于多因素的结果二度排序法。该方法结合结果结构权重和信息检索中常用的内容匹配, 首先采用结果路径权重衡量关键词之间的关联紧密程度对结果粗排序; 然后, 对于结构权重相等的结果, 引入信息元组中的关键词词频和包含关键词的信息量对结果细排序。实验分析表明, 该排序方法能将与查询条件高度相关的结果排在前面, 提高结果的查准率。     

Two new criteria for finding Steiner hulls in Steiner tree problems

The Steiner tree problem considered in this paper is that of finding a network of minimum length connecting a given setK of terminals in a regionR of the Euclidean plane. ASteiner hull forK inR is any subregion ofR known to contain a Steiner tree forK inR. Two new criteria are given for finding Steiner hulls—one for the Steiner tree problem on plane graphs and one for the rectilinear Steiner tree problem—which strengthen known polynomial-time methods of finding Steiner hulls.This research was supported by the Air Force Office of Scientific Research under Grant AFOSR-84-0140. Reproduction in whole or part is permitted for any purpose of the United States Government.     

基于DCT域内拉普拉斯值排序的人脸识别方法

基于DCT域内的人脸识别方法的关键是如何选择有效的DCT系数,提出了一种基于DCT域内拉普拉斯值排序的人脸识别方法。首先将图像划分为若干个大小相同的子块,对每一个子块进行DCT变换,得到分块DCT系数,然后利用拉普拉斯值作为局部保持能力判据选择那些能够很好保持样本流形结构的分块DCT系数,最后对选定的DCT系数执行LPP算法提取识别特征,在ORL和Yale人脸数据库上的实验结果证明了该方法的有效性。     

基于图学习的社会网络图像标签排序算法

提出一种社会网络图像标签排序算法。将SIFT特征、卷积神经网络特征以及视觉词袋模型相结合,从图像训练集中获取目标图像的视觉近邻图像集;令所有视觉近邻图像为目标图像的初始标签进行加权投票,通过对图像视觉相似度和标签语义相似度的线性融合,计算投票权值;利用目标图像及其视觉近邻图像的标签,构造标签图模型;利用加权投票结果在标签图上执行随机漫步,完成标签排序任务。实验结果验证了提出方法的有效性。     

Extracting frequent connected subgraphs from large graph sets

Mining frequent patterns from datasets is one of the key success of data mining research. Currently,most of the studies focus on the data sets in which the elements are independent, such as the items in the marketing basket. However, the objects in the real world often have close relationship with each other. How to extract frequent patterns from these relations is the objective of this paper. The authors use graphs to model the relations, and select a simple type for analysis. Combining the graph theory and algorithms to generate frequent patterns, a new algorithm called Topology, which can mine these graphs efficiently, has been proposed.The performance of the algorithm is evaluated by doing experiments with synthetic datasets and real data. The experimental results show that Topology can do the job well. At the end of this paper, the potential improvement is mentioned.     

Searching Steiner trees for web graph query

The enormous growth in information technology has revolutionized the way people can access information sources. Web search engines have played an important role to support what the user wants precisely and efficiently from the vast web database. Different from conventional search engine approaches, searching the structure of the web, where the answer comprises more than a single page connected by hyperlinks, needs to be meritoriously developed. We propose Linear Programming models in order to generate the optimal structured web objects searching for relevant web graphs. In the model, the web objects with node and edge weights that represent the ranking measures for Webpages and hyperlinks are devised to rank the relevance in terms of keyword vectors. We also developed a tree-filtering algorithm and top-k Steiner tree algorithm that is used to provide the search recommendations in practical applications. With real web databases, the experimental study shows that the LP approach outperforms the conventional search engines with respect to execution time and quality of results.     

Web image retrieval using majority-based ranking approach

Web image retrieval has characteristics different from typical content-based image retrieval; web images have associated textual cues. However, a web image retrieval system often yields undesirable results, because it uses limited text information such as surrounding text, URLs, and image filenames. In this paper, we propose a new approach to retrieval, which uses the image content of retrieved results without relying on assistance from the user. Our basic hypothesis is that more popular images have a higher probability of being the ones that the user wishes to retrieve. According to this hypothesis, we propose a retrieval approach that is based on a majority of the images under consideration. We define four methods for finding the visual features of majority of images; (1) majority-first method, (2) centroid-of-all method, (3) centroid-of-top K method, and (4) centroid-of-largest-cluster method. In addition, we implement a graph/picture classifier for improving the effectiveness of web image retrieval. We evaluate the retrieval effectiveness of both our methods and conventional ones by using precision and recall graphs. Experimental results show that the proposed methods are more effective than conventional keyword-based retrieval methods.     

A novel edge-centric approach for graph edit similarity computation

Graph similarity is an important notion with many applications. Graph edit distance is one of the most flexible graph similarity measures available. The main problem with this measure is that in practice it can only be computed for small graphs due to its exponential time complexity. This paper addresses the high complexity of graph edit distance computations. Specifically, we present CSI_GED, a novel edge-centric approach for computing graph edit distance through common sub-structure isomorphisms enumeration. CSI_GED utilizes backtracking search combined with a number of heuristics to reduce memory requirements and quickly prune away a large portion of the mapping search space. Experiments show that CSI_GED is highly efficient for computing graph edit distance; it outperforms the state-of-the-art methods by over three orders of magnitude. It also shows that CSI_GED scales the computation gracefully to larger and distant graphs on which current methods fail to run. Moreover, we evaluated CSI_GED as a stand-alone graph edit similarity search query method. The experiments show that CSI_GED is effective and scalable, and outperforms the state-of-the-art indexing-based methods by over two orders of magnitude.     

A linear-time algorithm to compute a MAD tree of an interval graph

The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. We present a linear time algorithm that determines, for a given interval graph G, a spanning tree of G with minimum average distance (MAD tree). Such a tree is sometimes referred to as a minimum routing cost spanning tree.     

Two probabilistic results on rectilinear steiner trees

In recent years, researchers have proven many theorems of the following form: given points distributed according to a Poisson process with intensity parameterN on the unit square, the length of the shortest spanning tree (rectilinear Steiner tree, traveling salesman tour, or some other functional) on these points is, with probability one, asymptotic to N for some constant (which is presumably different for different functionals). Though these theorems are well understood, very little is known about the constants . In this paper we prove that the constants in the cases of rectilinear spanning tree and rectilinear Steiner tree do, indeed, differ. This proof is constructive in the sense that we give a polynomial-time heuristic algorithm that produces a Steiner tree of expected length some fraction shorter than a minimum spanning tree. We continue the analysis to prove a second result: the expected value of the minimum number of Steiner points in a shortest rectilinear Steiner tree grows linearly withN.Research supported in part by NSF Grant MCS-8311422. A preliminary version of this paper appeared in theProceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986.     

Using entropy metrics for pruning very large graph cubes

Emerging applications face the need to store and analyze interconnected data. Graph cubes permit multi-dimensional analysis of graph datasets based on attribute values available at the nodes and edges of these graphs. Like the data cube that contains an exponential number of aggregations, the graph cube results in an exponential number of aggregate graph cuboids. As a result, they are very hard to analyze. In this work, we first propose intuitive measures based on the information entropy in order to evaluate the rich information contained in the graph cube. We then introduce an efficient algorithm that suggests portions of a precomputed graph cube based on these measures. The proposed algorithm exploits novel entropy bounds that we derive between different levels of aggregation in the graph cube. Per these bounds we are able to prune large parts of the graph cube, saving costly entropy calculations that would be otherwise required. We experimentally validate our techniques on real and synthetic datasets and demonstrate the pruning power and efficiency of our proposed techniques.     

Evaluation and ranking DMUs in the presence of both undesirable and ordinal factors in data envelopment analysis

In the last decade,ranking units in data envelopment analysis(DEA) has become the interests of many DEA researchers and a variety of models were developed to rank units with multiple inputs and multiple outputs.These performance factors(inputs and outputs) are classified into two groups:desirable and undesirable.Obviously,undesirable factors in production process should be reduced to improve the performance.Also,some of these data may be known only in terms of ordinal relations.While the models developed in the past are interesting and meaningful,they didn t consider both undesirable and ordinal factors at the same time.In this research,we develop an evaluating model and a ranking model to overcome some deficiencies in the earlier models.This paper incorporates undesirable and ordinal data in DEA and discusses the efficiency evaluation and ranking of decision making units(DMUs) with undesirable and ordinal data.For this purpose,we transform the ordinal data into definite data,and then we consider each undesirable input and output as desirable output and input,respectively.Finally,an application that shows the capability of the proposed method is illustrated.     

基于PageRank的页面排序改进算法

首先对PageRank算法进行了一般性介绍,研究了现有的基于链接结构的改进算法.在此基础上,指出PageRank算法给不同网页分配相同的Pagegank值影响了网页的排序质量,提出了一种基于多层分类技术的改进算法HCPR,并对PageRank和HCPR算法进行了相应测试和比较.实验结果表明,HCPR的排序结果比PageRank提高了约15.3%的相关度.     

基于注意力与图卷积网络的关系抽取模型

针对关系抽取任务中句子依存树的信息利用率低和特征提取效果不佳的问题,提出了一种基于注意力引导的门控感知图卷积网络(Att-Gate-GCN)模型.首先,利用一种基于注意力机制的软剪枝策略,通过注意力机制为依存树中的边分配权重,以挖掘依存树中的有效信息,同时过滤无用信息;其次,构建一种门控感知图卷积网络(GCN)结构,通...     

Distance-based tree models for ranking data

Ranking data has applications in different fields of studies, like marketing, psychology and politics. Over the years, many models for ranking data have been developed. Among them, distance-based ranking models, which originate from the classical rank correlations, postulate that the probability of observing a ranking of items depends on the distance between the observed ranking and a modal ranking. The closer to the modal ranking, the higher the ranking probability is. However, such a model basically assumes a homogeneous population and does not incorporate the presence of covariates.To overcome these limitations, we combine the strength of a tree model and the existing distance-based models to build a model that can handle more complexity and improve prediction accuracy. We will introduce a recursive partitioning algorithm for building a tree model with a distance-based ranking model fitted at each leaf. We will also consider new weighted distance measures which allow different weights for different ranks in formulating more flexible distance-based tree models. Finally, we will apply the proposed methodology to analyze a ranking dataset of Inglehart’s items collected in the 1999 European Values Studies.     

A graph grammars based framework for querying graph-like data

The widespread use of graph-based models for representing data collections (e.g. object-oriented data, XML data, etc.) has stimulated the database research community to investigate the problem of defining declarative languages for querying graph-like databases. In this paper, a new framework for querying graph-like data based on graph grammars is proposed. The new paradigm allows us to verify structural properties of graphs and to extract sub-graphs. More specifically, a new form of query (namely graph query) is proposed, consisting in a particular graph grammar which defines a class of graphs to be matched on the graph representing the database. Thus, differently from path queries, the answer of a graph query is not just a set of nodes, but a subgraph, extracted from the input graph, which satisfies the structural properties defined by the graph grammar. Expressiveness and complexity of different forms of graph queries are discussed, and some practical applications are shown.     

T-GAN: A deep learning framework for prediction of temporal complex networks with adaptive graph convolution and attention mechanism

Complex network is graph network with non-trivial topological features often occurring in real systems, such as video monitoring networks, social networks and sensor networks. While there is growing research study on complex networks, the main focus has been on the analysis and modeling of large networks with static topology. Predicting and control of temporal complex networks with evolving patterns are urgently needed but have been rarely studied. In view of the research gaps we are motivated to propose a novel end-to-end deep learning based network model, which is called temporal graph convolution and attention (T-GAN) for prediction of temporal complex networks. To joint extract both spatial and temporal features of complex networks, we design new adaptive graph convolution and integrate it with Long Short-Term Memory (LSTM) cells. An encoder-decoder framework is applied to achieve the objectives of predicting properties and trends of complex networks. And we proposed a dual attention block to improve the sensitivity of the model to different time slices. Our proposed T-GAN architecture is general and scalable, which can be used for a wide range of real applications. We demonstrate the applications of T-GAN to three prediction tasks for evolving complex networks, namely, node classification, feature forecasting and topology prediction over 6 open datasets. Our T-GAN based approach significantly outperforms the existing models, achieving improvement of more than 4.7% in recall and 25.1% in precision. Additional experiments are also conducted to show the generalization of the proposed model on learning the characteristic of time-series images. Extensive experiments demonstrate the effectiveness of T-GAN in learning spatial and temporal feature and predicting properties for complex networks.     

Towards data augmentation in graph neural network: An overview and evaluation

Many studies on Graph Data Augmentation (GDA) approaches have emerged. The techniques have rapidly improved performance for various graph neural network (GNN) models, increasing the current state-of-the-art accuracy by absolute values of 4.20%, 5.50%, and 4.40% on Cora, Citeseer, and PubMed, respectively. The success is attributed to two integral properties of relational approaches: topology-level and feature-level augmentation. This work provides an overview of some GDA algorithms which are reasonably categorized based on these integral properties. Next, we engage the three most widely used GNN backbones (GCN, GAT, and GraphSAGE) as plug-and-play methods for conducting experiments. We conclude by evaluating the algorithm’s effectiveness to demonstrate significant differences among various GDA techniques based on accuracy and time complexity with additional datasets different from those used in the original works. While discussing practical and theoretical motivations, considerations, and strategies for GDA, this work comprehensively investigates the challenges and future direction by pinpointing several open conceivable issues that may require further study based on far-reaching literature interpretation and empirical outcomes.