CiteULike: bigbossman's graph

GraphStream: A Tool for bridging the gap between Complex Systems and Dynamic Graphs

Yoann Pigné — 2008-03-17T04:46:56-00:00

(14 Mar 2008)

The notion of complex systems is common to many domains, from Biology to Economy, Computer Science, Physics, etc. Often, these systems are made of sets of entities moving in an evolving environment. One of their major characteristics is the emergence of some global properties stemmed from local interactions between the entities themselves and between the entities and the environment. The structure of these systems as sets of interacting entities leads researchers to model them as graphs. However, their understanding requires most often to consider the dynamics of their evolution. It is indeed not relevant to study some properties out of any temporal consideration. Thus, dynamic graphs seem to be a very suitable model for investigating the emergence and the conservation of some properties. GraphStream is a Java-based library whose main purpose is to help researchers and developers in their daily tasks of dynamic problem modeling and of classical graph management tasks: creation, processing, display, etc. It may also be used, and is indeed already used, for teaching purpose. GraphStream relies on an event-based engine allowing several event sources. Events may be included in the core of the application, read from a file or received from an event handler.

Drawing graphs by eigenvectors: theory and practice

Y Koren — 2008-03-02T22:40:20-00:00

Computers & Mathematics with Applications, Vol. 49, No. 11-12. (June 2005), pp. 1867-1888.

The spectral approach for graph visualization computes the layout of a graph using certain eigenvectors of related matrices. Two important advantages of this approach are an ability to compute optimal layouts (according to specific requirements) and a very rapid computation time. In this paper, we explore spectral visualization techniques and study their properties from different points of view. We also suggest a novel algorithm for calculating spectral layouts resulting in an extremely fast computation by optimizing the layout within a small vector space.

Diffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partitioning, and data set parameterization

S Lafon — 2007-02-20T18:55:09-00:00

Pattern Analysis and Machine Intelligence, IEEE Transactions on, Vol. 28, No. 9. (2006), pp. 1393-1403.

We provide evidence that nonlinear dimensionality reduction, clustering, and data set parameterization can be solved within one and the same framework. The main idea is to define a system of coordinates with an explicit metric that reflects the connectivity of a given data set and that is robust to noise. Our construction, which is based on a Markov random walk on the data, offers a general scheme of simultaneously reorganizing and subsampling graphs and arbitrarily shaped data sets in high dimensions using intrinsic geometry. We show that clustering in embedding spaces is equivalent to compressing operators. The objective of data partitioning and clustering is to coarse-grain the random walk on the data while at the same time preserving a diffusion operator for the intrinsic geometry or connectivity of the data set up to some accuracy. We show that the quantization distortion in diffusion space bounds the error of compression of the operator, thus giving a rigorous justification for k-means clustering in diffusion space and a precise measure of the performance of general clustering algorithms.

Visual exploration of multivariate graphs

Martin Wattenberg — 2008-02-28T03:38:06-00:00

(2006), pp. 811-819.

GraphScape: integrated multivariate network visualization

K Xu — 2008-02-28T03:35:03-00:00

Visualization, 2007. APVIS '07. 2007 6th International Asia-Pacific Symposium on (2007), pp. 33-40.

In this paper, we introduce a new method, GraphScape, to visualize multivariate networks, i.e., graphs with multivariate data associated with their nodes. GraphScape adopts a landscape metaphor with network structure displayed on a 2D plane and the surface height in the third dimension represents node attribute. More than one attribute can be visualized simultaneously by using multiple surfaces. In addition, GraphScape can be easily combined with existing methods to further increase the total number of attributes visualized. One of the major goals of GraphScape is to reveal multivariate graph clustering, which is based on both network structure and node attributes. This is achieved by a new layout algorithm and an innovative way of constructing attribute surface, which also allows visual clustering at different scales through interaction. A simplified attribute surface model is also proposed to reduce computation requirement when visualizing large networks. GraphScape is applied to networks of three different size (20, 100, and 1500) to demonstrate its effectiveness

A graph drawing algorithm for visualizing multivariate categorical data

Jingwei Huang — 2008-02-28T03:34:28-00:00

Wuhan University Journal of Natural Sciences, Vol. 12, No. 2. (11 March 2007), pp. 239-242.

Abstract In this paper, a new approach for visualizing multivariate categorical data is presented. The approach uses a graph to represent multivariate categorical data and draws the graph in such a way that we can identify patterns, trends and relationship within the data. A mathematical model for the graph layout problem is deduced and a spectral graph drawing algorithm for visualizing multivariate categorical data is proposed. The experiments show that the drawings by the algorithm well capture the structures of multivariate categorical data and the computing speed is fast.

Survey of graph database models

Renzo Angles — 2008-02-25T22:23:48-00:00

ACM Comput. Surv., Vol. 40, No. 1. (February 2008), pp. 1-39.

Choice numbers of graphs

Shai Gutner — 2008-02-18T18:53:06-00:00

(15 Feb 2008)

A solution to a problem of Erd\Hos, Rubin and Taylor is obtained by showing that if a graph $G$ is $(a:b)$-choosable, and $c/d > a/b$, then $G$ is not necessarily $(c:d)$-choosable. The simplest case of another problem, stated by the same authors, is settled, proving that every 2-choosable graph is also $(4:2)$-choosable. Applying probabilistic methods, an upper bound for the $k^th$ choice number of a graph is given. We also prove that a directed graph with maximum outdegree $d$ and no odd directed cycle is $(k(d+1):k)$-choosable for every $k ≥ 1$. Other results presented in this article are related to the strong choice number of graphs (a generalization of the strong chromatic number). We conclude with complexity analysis of some decision problems related to graph choosability.

Domination in graphs with bounded propagation: algorithms, formulations and hardness results

Ashkan Aazami — 2008-02-18T15:46:39-00:00

(15 Feb 2008)

We introduce a hierarchy of problems between the \textscDominating Set problem and the \textscPower Dominating Set (PDS) problem called the $\ell$-round power dominating set ($\ell$-round PDS, for short) problem. For $\ell=1$, this is the \textscDominating Set problem, and for $\ell≥ n-1$, this is the PDS problem; here $n$ denotes the number of nodes in the input graph. In PDS the goal is to find a minimum size set of nodes $S$ that power dominates all the nodes, where a node $v$ is power dominated if (1) $v$ is in $S$ or it has a neighbor in $S$, or (2) $v$ has a neighbor $u$ such that $u$ and all of its neighbors except $v$ are power dominated. Note that rule (1) is the same as for the \textscDominating Set problem, and that rule (2) is a type of propagation rule that applies iteratively. The $\ell$-round PDS problem has the same set of rules as PDS, except we apply rule (2) in “parallel” in at most $\ell-1$ rounds. We prove that $\ell$-round PDS cannot be approximated better than $2^\log^1-εn$ even for $\ell=4$ in general graphs. We provide a dynamic programming algorithm to solve $\ell$-round PDS optimally in polynomial time on graphs of bounded tree-width. We present a PTAS (polynomial time approximation scheme) for $\ell$-round PDS on planar graphs for $\ell=O(\tfrac\logn\log\logn)$. Finally, we give integer programming formulations for $\ell$-round PDS.

A decentralized algorithm for spectral analysis

David Kempe — 2006-05-07T20:15:24-00:00

(2004), pp. 561-568.

Dynamic Multilevel Graph Visualization

Todd Veldhuizen — 2007-12-12T08:23:59-00:00

(10 Dec 2007)

We adapt multilevel, force-directed graph layout techniques to visualizing dynamic graphs in which vertices and edges are added and removed in an online fashion (i.e., unpredictably). We maintain multiple levels of coarseness using a dynamic, randomized coarsening algorithm. To ensure the vertices follow smooth trajectories, we employ dynamics simulation techniques, treating the vertices as point particles. We simulate fine and coarse levels of the graph simultaneously, coupling the dynamics of adjacent levels. Projection from coarser to finer levels is adaptive, with the projection determined by an affine transformation that evolves alongside the graph layouts. The result is a dynamic graph visualizer that quickly and smoothly adapts to changes in a graph.

Model indexing: the graph-hashing approach

H Sossa — 2007-12-06T03:07:36-00:00

Computer Vision and Pattern Recognition, 1992. Proceedings CVPR '92., 1992 IEEE Computer Society Conference on (1992), pp. 811-814.

The problem of object recognition in computer vision is addressed. A method for model indexing, which, given a group of image features, rapidly extracts from the list of objects those objects containing this group of features, is presented. The method operates on an abstract representation of features, more precisely, groups of features. In practice, this abstract representation takes the form of a graph. The present study deals with binary graphs only, that is, only one feature-type and one feature-relationship-type can be embedded in the representation

Indexing hierarchical structures using graph spectra

A Shokoufandeh — 2007-12-06T03:06:57-00:00

Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, No. 7. (2005), pp. 1125-1140.

Hierarchical image structures are abundant in computer vision and have been used to encode part structure, scale spaces, and a variety of multiresolution features. In this paper, we describe a framework for indexing such representations that embeds the topological structure of a directed acyclic graph (DAG) into a low-dimensional vector space. Based on a novel spectral characterization of a DAG, this topological signature allows us to efficiently retrieve a promising set of candidates from a database of models using a simple nearest-neighbor search. We establish the insensitivity of the signature to minor perturbation of graph structure due to noise, occlusion, or node split/merge. To accommodate large-scale occlusion, the DAG rooted at each nonleaf node of the query "votes" for model objects that share that "part," effectively accumulating local evidence in a model DAG's topological subspaces. We demonstrate the approach with a series of indexing experiments in the domain of view-based 3D object recognition using shock graphs.

Graphgrep: A fast and universal method for querying graphs

R Giugno — 2007-12-06T03:04:37-00:00

(2002)

GraphGrep is an application-independent method for querying graphs, finding all the occurrences of a subgraph in a database of graphs. The interface to GraphGrep is a regular expression graph query language Glide that combines features from XPath and Smart. Glide incorporates both single node and variable-length wildcards. Our algorithm uses hash-based fingerprinting to represent the graphs in an abstract form and to filter the database. GraphGrep has been tested on databases of size up to...

A Polynominal Time Algorithm for Graph Isomorphism

Reiner Czerwinski — 2007-11-14T04:51:00-00:00

(13 Nov 2007)

Algorithms testing two graphs for isomorphism known as yet have exponential worst case complexity. In this paper we propose a new algorithm that has polynomial complexity and constructively supplies the evidence that the graph isomorphism lies in P.

A Tutorial on Spectral Clustering

Ulrike von Luxburg — 2007-11-02T16:25:32-00:00

(1 Nov 2007)

In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms traditional clustering algorithms such as the k-means algorithm. On the first glance spectral clustering appears slightly mysterious, and it is not obvious to see why it works at all and what it really does. The goal of this tutorial is to give some intuition on those questions. We describe different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches. Advantages and disadvantages of the different spectral clustering algorithms are discussed.

Indexing Hierarchical Structures Using Graph Spectra

A Shokoufandeh — 2007-11-02T02:06:06-00:00

(2005)

Hierarchical image structures are abundant in computer vision and have been used to encode part structure, scale spaces, and a variety of multiresolution features. In this paper, we describe a framework for indexing such representations that embeds the topological structure of a directed acyclic graph (DAG) into a low-dimensional vector space. Based on a novel spectral characterization of a DAG, this topological signature allows us to efficiently retrieve a promising set of candidates from a ...

Correlation search in graph databases

Yiping Ke — 2007-08-21T13:19:17-00:00

(2007), pp. 390-399.

Detecting research topics via the correlation between graphs and texts

Yookyung Jo — 2007-11-02T01:59:42-00:00

(2007), pp. 370-379.

Geometric representation of graphs in low dimension

Sunil Chandran — 2007-08-01T06:21:27-00:00

(31 Jul 2007)

We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (Δ + 2) \ln n$ dimensions, where $Δ$ is the maximum degree of G. We also show that $\boxi(G) ≤ (Δ + 2) \ln n$ for any graph G. Our bound is tight up to a factor of $\ln n$. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree $Δ$, we show that for almost all graphs on n vertices, its boxicity is upper bound by $c⋅(d_av + 1) \ln n$ where d_av is the average degree and c is a small constant. Also, we show that for any graph G, $\boxi(G) ≤ \sqrt8 n d_av \ln n$, which is tight up to a factor of $b \sqrt\ln n$ for a constant b.

A fast multilevel algorithm for graph clustering and community detection

Hristo Djidjev — 2007-07-18T12:38:22-00:00

(16 Jul 2007)

One of the most useful measures of cluster quality is the modularity of a partition, which measures the difference between the number of the edges joining vertices from the same cluster and the expected number of such edges in a random (unstructured) graph. In this paper we show that the problem of finding a partition maximizing the modularity of a given graph G can be reduced to a minimum weighted cut problem on a complete graph with the same vertices as G. We then show that the resulted minimum cut problem can be efficiently solved with existing software for graph partitioning and that our algorithm finds clusterings of a better quality and much faster than the existing clustering algorithms.

A large-scale study of link spam detection by graph algorithms

Hiroo Saito — 2007-07-16T15:26:45-00:00

(2007), pp. 45-48.

Resilience of graphs

Benny Sudakov — 2007-07-02T17:53:51-00:00

(27 Jun 2007)

In this paper, we initiate a systematic study of graph resilience. The (local) resilience of a graph G with respect to a property P measures how much one has to change G (locally) in order to destroy P. Estimating the resilience leads to many new and challenging problems. Here we focus on random and pseudo-random graphs and prove several sharp results.

Dynamic Exploration of Networks: from general principles to the traceroute process

Luca Dall'asta — 2007-06-28T12:00:33-00:00

(26 Jun 2007)

Dynamical processes taking place on real networks define on them evolving subnetworks whose topology is not necessarily the same of the underlying one. We investigate the problem of determining the emerging degree distribution, focusing on a class of tree-like processes, such as those used to explore the Internet's topology. A general theory based on mean-field arguments is proposed, both for single-source and multiple-source cases, and applied to the specific example of the traceroute exploration of networks. Our results provide a qualitative improvement in the understanding of dynamical sampling and of the interplay between dynamics and topology in large networks like the Internet.

Graph Laplacians and their convergence on random neighborhood graphs

Matthias Hein — 2007-06-28T12:00:23-00:00

(27 Jun 2007)

Given a sample from a probability measure with support on a submanifold in Euclidean space one can construct a neighborhood graph which can be seen as an approximation of the submanifold. The graph Laplacian of such a graph is used in several machine learning methods like semi-supervised learning, dimensionality reduction and clustering. In this paper we determine the pointwise limit of three different graph Laplacians used in the literature as the sample size increases and the neighborhood size approaches zero. We show that for a uniform measure on the submanifold all graph Laplacians have the same limit up to constants. However in the case of a non-uniform measure on the submanifold only the so called random walk graph Laplacian converges to the weighted Laplace-Beltrami operator.

Random Graph-Homomorphisms and Logarithmic Degree

Itai Benjamini — 2007-06-26T13:09:03-00:00

(21 Jun 2007)

A graph homomorphism between two graphs is a map from the vertex set of one graph to the vertex set of the other graph, that maps edges to edges. In this note we study the range of a uniformly chosen homomorphism from a graph G to the infinite line Z. It is shown that if the maximal degree of G is `sub-logarithmic', then the range of such a homomorphism is super-constant. Furthermore, some examples are provided, suggesting that perhaps for graphs with super-logarithmic degree, the range of a typical homomorphism is bounded. In particular, a sharp transition is shown for a specific family of graphs C_n,k (which is the tensor product of the n-cycle and a complete graph, with self-loops, of size k). That is, given any function psi(n) tending to infinity, the range of a typical homomorphism of C_n,k is super-constant for k = 2 log(n) - psi(n), and is 3 for k = 2 log(n) + psi(n).

Out-of-core coherent closed quasi-clique mining from large dense graph databases

Zhiping Zeng — 2007-06-21T03:53:04-00:00

ACM Trans. Database Syst., Vol. 32, No. 2. (June 2007)

Mining Graph Data

Diane Cook — 2007-06-11T19:12:49-00:00

(28 November 2006)

This text takes a focused and comprehensive look at mining data represented as a graph, with the latest findings and applications in both theory and practice provided. Even if you have minimal background in analyzing graph data, with this book you’ll be able to represent data as graphs, extract patterns and concepts from the data, and apply the methodologies presented in the text to real datasets. <p> There is a misprint with the link to the accompanying Web page for this book. For those readers who would like to experiment with the techniques found in this book or test their own ideas on graph data, the Web page for the book should be http://www.eecs.wsu.edu/MGD.

An object-oriented design for graph visualization

MS Marshall — 2007-06-09T05:19:15-00:00

Software: Practice and Experience, Vol. 31, No. 8. (2001), pp. 739-756.

Many applications, from everyday file system browsers to visual programming tools, require the display of network and graph structures. The Graph Visualization Framework (GVF) (available at http://www.cwi.nl/InfoVisu/GVF) is an architecture that supports the tasks common to most graph browsers and editors. This article gives a brief overview of the design of the GVF and focuses on the core classes that are used to represent and manipulate graphs. The design of the core classes is justified by the requirements for navigation and visualization. Copyright © 2001 John Wiley & Sons, Ltd.

A spectral method to separate disconnected and nearly-disconnected web graph components

Chris Ding — 2007-05-21T23:41:12-00:00

(2001), pp. 275-280.

Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92) (Cbms Regional Conference Series in Mathematics)

Fan Chung — 2005-10-17T02:37:42-00:00

(06 February 1997)

Beautifully written and elegantly presented, this book is based on 10 lectures given at the CBMS workshop on spectral graph theory in June 1994 at Fresno State University. Chung's well-written exposition can be likened to a conversation with a good teacher--one who not only gives you the facts, but tells you what is really going on, why it is worth doing, and how it is related to familiar ideas in other areas. The monograph is accessible to the nonexpert who is interested in reading about this evolving area of mathematics.

Finding community structure in networks using the eigenvectors of matrices

MEJ Newman — 2007-04-11T22:37:21-00:00

Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), Vol. 74, No. 3. (2006)

We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks.

Pattern vectors from algebraic graph theory

RC Wilson — 2007-04-11T22:37:09-00:00

Pattern Analysis and Machine Intelligence, IEEE Transactions on, Vol. 27, No. 7. (2005), pp. 1112-1124.

Graph structures have proven computationally cumbersome for pattern analysis. The reason for this is that, before graphs can be converted to pattern vectors, correspondences must be established between the nodes of structures which are potentially of different size. To overcome this problem, in this paper, we turn to the spectral decomposition of the Laplacian matrix. We show how the elements of the spectral matrix for the Laplacian can be used to construct symmetric polynomials that are permutation invariants. The coefficients of these polynomials can be used as graph features which can be encoded in a vectorial manner. We extend this representation to graphs in which there are unary attributes on the nodes and binary attributes on the edges by using the spectral decomposition of a Hermitian property matrix that can be viewed as a complex analogue of the Laplacian. To embed the graphs in a pattern space, we explore whether the vectors of invariants can be embedded in a low-dimensional space using a number of alternative strategies, including principal components analysis (PCA), multidimensional scaling (MDS), and locality preserving projection (LPP). Experimentally, we demonstrate that the embeddings result in well-defined graph clusters. Our experiments with the spectral representation involve both synthetic and real-world data. The experiments with synthetic data demonstrate that the distances between spectral feature vectors can be used to discriminate between graphs on the basis of their structure. The real-world experiments show that the method can be used to locate clusters of graphs.

Diffusion-driven multiscale analysis on manifolds and graphs: top-down and bottom-up constructions

AD Szlam — 2007-03-27T18:10:58-00:00

(2005), pp. 445-455.

Cluster graph modification problems

Ron Shamir — 2006-09-28T12:28:03-00:00

Discrete Appl. Math., Vol. 144, No. 1-2. (2004), pp. 173-182.

Predicting Protein-Protein Interactions from Protein Domains Using a Set Cover Approach

Chengbang Huang — 2007-03-12T22:46:31-00:00

IEEE/ACM Trans. Comput. Biol. Bioinformatics, Vol. 4, No. 1. (January 2007), pp. 78-87.

Ortholog Clustering on a Multipartite Graph

Akshay Vashist — 2007-03-12T22:46:23-00:00

IEEE/ACM Trans. Comput. Biol. Bioinformatics, Vol. 4, No. 1. (January 2007), pp. 17-27.

GMine: a system for scalable, interactive graph visualization and mining

Jos&\#233; Rodrigues — 2007-02-24T02:23:59-00:00

(2006), pp. 1195-1198.

On Structural Properties of the Market Graph

V Boginski — 2007-02-23T23:50:46-00:00

(2003)

this paper, we will concentrate on another important real-life application - the graph representation of the stock market. Every year stock markets generate a huge amount of data, and this information can be used for constructing a graph that will reflect the market behavior

Fundamentals of Domination in Graphs (Pure and Applied Mathematics (Marcel Dekker))

Teresa Haynes — 2007-02-21T05:09:41-00:00

(05 January 1998)

<P>"Provides the first comprehensive treatment of theoretical, algorithmic, and application aspects of domination in graphs-discussing fundamental results and major research accomplishments in an easy-to-understand style. Includes chapters on domination algorithms and NP-completeness as well as frameworks for domination."</P>

Graph Theory

Frank Harary — 2005-11-30T17:15:17-00:00

An effort has been made to present the various topics in the theory of graphs in a logical order, to indicate the historical background, and to clarify the exposition by including figures to illustrate concepts and results. In addition, there are three appendices which provide diagrams of graphs, directed graphs, and trees. The emphasis throughout is on theorems rather than algorithms or applications, which however are occaisionally mentioned.

Ore-type graph packing problems

AV Kostochka — 2007-02-19T00:03:18-00:00

Combinatorics, Probability and Computing (2006), pp. 1-3.

Packing of graphs and permutations--a survey

Mariusz Wozniak — 2007-02-19T00:01:46-00:00

Discrete Mathematics, Vol. 276, No. 1-3. (6 February 2004), pp. 379-391.

An embedding of a graph G (into its complement ) is a permutation [sigma] on V(G) such that if an edge xy belongs to E(G) then [sigma](x)[sigma](y) does not belong to E(G). If there exists an embedding of G we say that G is embeddable or that there is a packing of two copies of the graph G into complete graph Kn. In this paper we discuss a variety of results, some quite recent, concerning the relationships between the embeddings of graphs in their complements and the structure of the embedding permutations.

Domination, Fractional Domination, 2-Packing, and Graph Products

David Fisher — 2007-02-18T23:54:52-00:00

SIAM Journal on Discrete Mathematics, Vol. 7, No. 3. (1994), pp. 493-498.

Motif Search in Graphs: Application to Metabolic Networks

Vincent Lacroix — 2007-01-05T02:31:38-00:00

IEEE/ACM Trans. Comput. Biol. Bioinformatics, Vol. 3, No. 4. (October 2006), pp. 360-368.

Feature-based similarity search in graph structures

Xifeng Yan — 2007-01-05T02:29:30-00:00

ACM Trans. Database Syst., Vol. 31, No. 4. (December 2006), pp. 1418-1453.

Fractal Graph Optimization Algorithms

JR Riehl — 2006-12-18T20:21:38-00:00

Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC '05. 44th IEEE Conference on (2005), pp. 2188-2193.

We introduce methods of hierarchically decomposing three types of graph optimization problems: all-pairs shortest path, all-pairs maximum flow,and search. Each method uses a partition on the graph to create a high level problem and several lower level problems. The computations on each level are identical, so the low level problems can be further decomposed. In this way, the problems become fractal in nature. We use these decomposition methods to establish upper and lower bounds on the optimal criteria of each problem, which can be achieved with much less computation than what is required to solve the original problem. Also, for each problem, we find an optimal number of partitions that minimizes computation time. As the number of hierarchical levels increases, the computational complexity decreases at the expense of looser bounds.

Graph building as a mining activity: finding links in the small

Antonio Badia — 2006-11-30T23:24:24-00:00

(2005), pp. 17-24.

Graph indexing: A frequent structure based approach

X Yan — 2006-11-30T22:55:49-00:00

(2004)

Graph has become increasingly important in modelling complicated structures and schemaless data such as proteins, chemical compounds, and XML documents. Given a graph query, it is desirable to retrieve graphs quickly from a large database via graph-based indices. In this paper, we investigate the issues of indexing graphs and propose a novel solution by applying a graph mining technique. Di#erent from the existing path-based methods, our approach, called gIndex, makes use of frequent...

Graph decomposition is NPC - a complete proof of Holyer's conjecture

Dorit Dor — 2006-11-30T22:33:13-00:00

(1992), pp. 252-263.