Truss decomposition of uncertain graphs

The k-truss of a graph is the largest edge-induced subgraph such that every edge is contained in at least k triangles within the subgraph, where a triangle is a cycle consisting of three vertices. As a new notion of cohesive subgraphs, truss has recently attracted a lot of research attentions in the database and data mining fields. At the same time, uncertainty is an intrinsic property of massive graph data, and truss decomposition (i.e., finding all k-trusses of a graph) has become a key primitive on uncertain graphs. In this paper, we study the truss decomposition problem on uncertain graphs, that is, finding all highly probable k-trusses of an uncertain graph. We first give an formal statement of the truss decomposition problem on uncertain graphs. Then, we prove that the truss decomposition of an uncertain graph attains two elegant properties, namely uniqueness and hierarchy. We show that the truss decomposition of an uncertain graph can be found in \(O(m^{1.5}Q)\) time by proposing an in-memory algorithm called \(\mathtt {TD_{mem}}\), where m is the number of edges of the uncertain graph, and Q is at most the maximum number of common neighbors of the endpoints of an edge. When an uncertain graph is too large to fit into main memory, we propose an external-memory algorithm \(\mathtt {TD_{I/O}}\) to find the truss decomposition of the uncertain graph. Extensive experiments have been carried out to evaluate the practical performance of the proposed algorithms. The experimental results verify that both \(\mathtt {TD_{mem}}\) and \(\mathtt {TD_{I/O}}\) are efficient when an uncertain graph is small enough to fit into main memory, and that \(\mathtt {TD_{I/O}}\) is much faster than \(\mathtt {TD_{mem}}\) when the graph is too large to fit into main memory.     

Cleaning uncertain graphs via noisy crowdsourcing

World Wide Web - Uncertain graph is an important data model for many real-world applications. To answer the query on the uncertain graphs, the edges in these graphs are associated with existential...     

Aggregate nearest neighbor queries in uncertain graphs

Most recently, uncertain graph data begin attracting significant interests of database research community, because uncertainty is the intrinsic property of the real-world and data are more suitable to be modeled as graphs in numbers of applications, e.g. social network analysis, PPI networks in biology, and road network monitoring. Meanwhile, as one of the basic query operators, aggregate nearest neighbor (ANN) query retrieves a data entity whose aggregate distance, e.g. sum, max, to the given query data entities is smaller than those of other data entities in a database. ANN query on both certain graph data and high dimensional data has been well studied by previous work. However, existing ANN query processing approaches cannot handle the situation of uncertain graphs, because topological structures of an uncertain graph may vary in different possible worlds. Motivated by this, we propose the aggregate nearest neighbor query in uncertain graphs (UG-ANN) in this paper. First of all, we give the formal definition of UG-ANN query and the basic UG-ANN query algorithm. After that, to improve the efficiency of UG-ANN query processing, we develop two kinds of pruning approaches, i.e. structural pruning and instance pruning. The structural pruning takes advantages the monotonicity of the aggregate distance to derive the upper and lower bounds of the aggregate distance for reducing the graph size. Whereas, the instance pruning decreases the number of possible worlds to be checked in the searching tree. Comprehensive experimental results on real-world data sets demonstrate that the proposed method significantly improves the efficiency of the UG-ANN query processing.     

面向不确定平面图的模式匹配查询

平面图的模式匹配查询可广泛应用于生物网络、社会网络、指纹识别和图像分割等。由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定平面图的查询处理技术不能有效地处理不确定性,因此利用概率语义描述的平面图的模式进行匹配查询。具体地,使用可能世界概率模型定义不确定平面图,基于该模型,研究了不确定模式匹配(UPM)查询。首先给出一个确定算法可避免枚举所有的可能世界,同时给出改进的确定算法可更快速地求解查询。其次设计出采样算法,可快速地估算出匹配概率,并具有较高的精确度。基于真实不确定平面图数据的大量实验验证了该设计。最后将该查询应用于肺部CT图像的分割,结果表明此方法优于经典的图像分割算法。     

A survey on mining and analysis of uncertain graphs

Knowledge and Information Systems - An uncertain graph (also known as probabilistic graph) is a generic model to represent many real-world networks from social to biological. In recent times,...     

基于能量函数和模块最优化的不确定图聚类

为证明不确定性的存在对聚类结果不可忽略的影响,改进了基于能量模型布局和模块化聚类的算法LinLogLayout,使之可以处理不确定图数据。提出了不确定图的定义并产生满足Zipf分布的不确定图数据,对确定算法进行不确定化使之满足应用要求。实验结果表明,不论是在确定图数据、不确定图数据还是人工数据集、真实数据集上,改进的LinLogLayout算法都具有较好的聚类效果。实验结果也表明,不确定性的存在对聚类结果具有不可忽略的影响。     

Tree graphs of RNA secondary structures and their comparisons

To facilitate comparison of RNA secondary structures each structure is represented as an ordered labeled tree. Several alternate secondary structures yielding a set of trees can be computed for any given RNA molecule (sequence). Frequently recurring subtrees are searched in this set of trees. The consensus structure motifs are then selected and used to construct a secondary structure model of the RNA. Given the difficulties involved in RNA secondary structure calculations, this procedure may significantly improve our predictive capabilities. In addition, the change of secondary structures between two different RNA sequences is described as a transformation of ordered trees. The transferable ratio of tree A from tree B is defined as a proportion of the largest common subtrees in trees A and B occurring in tree A. The method is applied to the study of the mechanism of human alpha 1 globin pre-mRNA splicing. In the study, two tentative splicing mechanisms, A and B, with different orders of intron excision from alpha 1 globin pre-mRNA have been stimulated. A possible relationship between the structural features of the secondary structures and the order of intron excision in the pathway of precursor splicing of human alpha 1 globin is discussed.     

Tree spanners on chordal graphs: complexity and algorithms

A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The T t-S problem asks whether a graph admits a tree t-spanner, given t. We substantially strengthen the hardness result of Cai and Corneil (SIAM J. Discrete Math. 8 (1995) 359–387) by showing that, for any t4, T t-S is NP-complete even on chordal graphs of diameter at most t+1 (if t is even), respectively, at most t+2 (if t is odd). Then we point out that every chordal graph of diameter at most t−1 (respectively, t−2) admits a tree t-spanner whenever t2 is even (respectively, t3 is odd), and such a tree spanner can be constructed in linear time.

The complexity status of T 3-S still remains open for chordal graphs, even on the subclass of undirected path graphs that are strongly chordal as well. For other important subclasses of chordal graphs, such as very strongly chordal graphs (containing all interval graphs), 1-split graphs (containing all split graphs) and chordal graphs of diameter at most 2, we are able to decide T 3-S efficiently.     

Acyclic chromatic index of planar graphs with triangles

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by , is the least number of colors in an acyclic edge coloring of G. Let G be a planar graph with maximum degree Δ(G). In this paper, we show that , if G contains no 4-cycle; , if G contains no intersecting triangles; and if G contains no adjacent triangles.     

一种适用连续不确定XML数据的索引

针对连续不确定XML数据概率阈值范围查询,提出一种新的CUXI索引树。该索引树的构建方法是借鉴U树对空间数据自顶向下递归构建索引树的思想,将连续不确定XML文档中具有相同父亲的叶子节点构建二维数据矩形,在聚类的基础上来构建相应的CUXI索引树,其中叶子节点存储连续不确定数据辅助信息。为了提高查询效率,对连续不确定数据制定了过滤策略,通过遍历索引树过滤掉不满足查询范围的子树。理论和实验结果表明,此索引技术可提高查询处理的性能。     

图上基于局部敏感哈希的多关键字索引

针对目前基于倒排表的图关键字索引不能有效处理多个关键字查询,也不能对关键字拼写容错的问题,提出一种位图和局部敏感哈希(BLH）相结合的双层索引来支持图的多关键字查询:上层构建位图,依据关键字组合的n-gram映射到子图类簇,每个类簇存储相似的子图;下层在每个类簇上构建局部敏感哈希索引,根据关键字组合的n-gram定位到包含关键字组合的子图。该方法可显著减少图上关键字查询的I/O,查询时间缩减80%;并且,基于n-gram构建索引,可以避免索引对拼写错误敏感,在关键字容错的前提下返回用户期望的结果。实际数据集上的实验结果表明BLH索引的有效性,可以支持万维网、社会网络的高效查询。     

共轭单圈图的广义Randic指标

化学分子图的拓扑指标理论是组合化学的一个重要研究分支,Randic指标与烷烃分子的很多物理和化学性质都显示了很强的相关性,如沸点、表面积以及水溶解度等等。Randic指标具有很低的退化度,能很好的描述分子结构和结构活性之间的关系。每一个顶点都是饱和的单圈图称为共轭单圈图。图G的广义Randic指标定义为R_a(G)=(d_ud_v)~a,其中α为任意实数,d_u为顶点u的度。本文使用反证法,通过分类讨论,研究了α∈[-1.3867,-1]时,共轭单圈图的广义Randic指标的最小值问题,给出了最小值及其相应的结构。给出的分子结构具有最小的广义Randic指标值,以及由此衍生而来的某类分子结构,可以帮助建立分子图数据库,对合成一些分子或药物具有非常重要的理论价值和应用背景。     

Euler index of uncertain random graph: concepts and properties

We are usually in the state of indeterminacy. Uncertainty and randomness are two basic types of indeterminacy. In many cases, uncertainty and randomness exist simultaneously in a complex system. This paper considers the Euler tour of an uncertain random graph, in which some edges exist with some degrees in uncertain measure and others exist with some degrees in probability measure. In order to show how likely an uncertain random graph is Eulerian, an Euler index of an uncertain random graph is proposed first. Then a method to calculate the Euler index of an uncertain random graph is given. In addition, some properties of the Euler index are discussed.     

New internal index for clustering validation based on graphs

This paper presents two different versions of a new internal index for clustering validation using graphs. These graphs capture the structural characteristics of each cluster. In this way, the new index overcomes the limitations of traditional indices based on statistics measurements and it is effective on clusters of different shapes and sizes. These graphs are generated through an iterative process based on the principal component analysis, which partitions the clusters in a configurable number of “sub-clusters”. Then, a minimum spanning tree based on the centroids of each of these sub-clusters is built and used to estimate both the quality of the clusters and the distances between them. In particular, the quality of a cluster is defined in this paper as the level of “cohesion” among its sub-clusters. The difference between the two versions of the proposed index is how this level of "cohesion" is measured. Finally, a comparison of the performance of these two versions of the proposed index with a selected group of well-known internal indices is carried out. In these tests, the two versions of the index show a superior capacity to deal with datasets that present different configurations of variances, densities, geometries and levels of noise.     

基于压缩全文索引的演变图查询

演变图中含有大量的时间和空间信息,其中某些空间信息随着时间的推移表现出相似的演变规律。给出了一种演变图查询模型,可以挖掘出在相同时间范围内具有相同变化规律的演变子图。但是演变图的规模往往是巨大的,当需要对其进行多次查询时,每次遍历整个演变图将带来非常高的查询代价,而现有的基于枚举的哈希索引算法又使得预处理过程拥有相当大的时间和空间开销,为了减少对大规模演变图的预处理代价,将压缩的全文索引技术应用于演变图,它基于涡轮转换和后缀数组。在构建后缀数组时,给出了两种不同的线性算法,确保了预处理过程的稳定性。通过在Facebook、Enron邮件系统以及模拟数据集上的实验,评估了该算法的可行性、效率以及可扩展性。     

基于一致性指标的两类不确定偏好信息集结

研究了两类区间数判断矩阵偏好信息的集结问题.首先,基于Saaty提出的数字互反判断矩阵一致性检验指标(CR),给出了区间数互反判断矩阵的满意一致性条件;然后利用互反与互补判断矩阵之间的关系求解出数字互补判断矩阵的一致性指标(CGCI),并在此基础上给出了区间数互补判断矩阵的满意一致性条件;最后建立了一致性指标最大的两类区间数判断矩阵偏好信息的集结模型,并用此模型解决了供应链中伙伴企业的选择问题.     

Structure and attribute index for approximate graph matching in large graphs

The increasing popularity of graph data in various domains has lead to a renewed interest in developing efficient graph matching techniques, especially for processing large graphs. In this paper, we study the problem of approximate graph matching in a large attributed graph. Given a large attributed graph and a query graph, we compute a subgraph of the large graph that best matches the query graph. We propose a novel structure-aware and attribute-aware index to process approximate graph matching in a large attributed graph. We first construct an index on the similarity of the attributed graph, by partitioning the large search space into smaller subgraphs based on structure similarity and attribute similarity. Then, we construct a connectivity-based index to give a concise representation of inter-partition connections. We use the index to find a set of best matching paths. From these best matching paths, we compute the best matching answer graph using a greedy algorithm. Experimental results on real datasets demonstrate the efficiency of both index construction and query processing. We also show that our approach attains high-quality query answers.