Search

Large scale iterative graph computation presents an interesting systems challenge due to two well known problems: (1) the lack of access locality and (2) the lack of storage efficiency. This paper presents PathGraph, a system for improving iterative graph computation on graphs with billions of edges. First, we improve the memory and disk access locality for iterative computation algorithms on large graphs by modeling a large graph using a collection of tree-based partitions. This enables us to use path-centric computation rather than vertex-centric or edge-centric computation. For each tree partition, we re-label vertices using DFS in order to preserve consistency between the order of vertex ids and vertex order in the paths. Second, a compact storage that is optimized for iterative graph parallel computation is developed in the PathGraph system. Concretely, we employ delta-compression and store tree-based partitions in a DFS order. By clustering highly correlated paths together as tree based partitions, we maximize sequential access and minimize random access on storage media. Third but not the least, our path-centric computation model is implemented using a scatter/gather programming model. We parallel the iterative computation at partition tree level and perform sequential local updates for vertices in each tree partition to improve the convergence speed. To provide well balanced workloads among parallel threads at tree partition level, we introduce the concept of multiple stealing points based task queue to allow work stealings from multiple points in the task queue. We evaluate the effectiveness of PathGraph by comparing with recent representative graph processing systems such as GraphChi and X-Stream etc. Our experimental results show that our approach outperforms the two systems on a number of graph algorithms for both in-memory and out-of-core graphs. While our approach achieves better data balance and load balance, it also shows better speedup than the two systems with the growth of threads.

Graph matching is important for a wide variety of applications in different domains such as social network analysis and knowledge discovery. Despite extensive research over the last few decades, graph matching is still challenging particularly when it comes with new conditions and constraints. In this paper, we focus on a new class of graph matching, in which each node can accept multiple labels instead of one. In particular, we address the problem of finding the top-k nodes of a data graph which best match a labeled query node from a given pattern graph. We firstly prove this to be an NP-Complete problem. Then, to address this issue and improve the scalability of our approach, we introduce a more flexible graph simulation, namely surjective simulation. This new graph simulation reduces the unnecessary complexity that is due to the unnecessary constraints imposed by the existing definitions while achieving high-quality matching results. In addition, our approach is associated with an early stop strategy to further boost the performance. To approximate the maximum size of a simulation, our approach utilizes Metropolis Hastings algorithm and ranks the top-k matches after computing the set of surjective simulations. The experimental results over social network graphs demonstrate the efficiency of the proposed approach and superiority over existing approaches.

In this paper, the problem of construction of exponentially many minimum genus embeddings of complete graphs in surfaces are studied. There are three approaches to solve this problem. The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding (or rotation) schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to this three approaches, we can construct exponentially many minimum genus embeddings of complete graph K 12s+8 in orientable surfaces, which show that there are at least $$\frac{10}{3} \times (\frac{200}{9})^s$$ distinct minimum genus embeddings for K 12s+8 in orientable surfaces. We have also proved that K 12s+8 has at least $$\frac{10}{3} \times (\frac{200}{9})^s$$ distinct minimum genus embeddings in non-orientable surfaces.

Efficiently answering reachability queries, which checks whether one vertex can reach another in a directed graph, has been studied extensively during recent years. However, the size of the graph that people are facing and generating nowadays is growing so rapidly that simple algorithms, such as BFS and DFS, are no longer feasible. Although Refined Online Search algorithms can scale to large graphs, they all suffer from the false positive problem. In this paper, we analyze the cause of false positive and propose an efficient High Dimensional coordinate generating method based on Graph Dominance Drawing (HD-GDD) to answer reachability queries in linear or even constant time. We conduct experiments on different graph structures and different graph sizes to fully evaluate the performance and behavior of our proposal. Empirical results demonstrate that our method outperforms state-of-the-art algorithms and can handle extensive graphs.

In this paper, we study the problem of modifying a graph such that the resulting graph has a dominating set of size at most k. Solving this problem determines the minimum number of edges to be added to a given graph such that at most k vertices can dominate all vertices. We show that this problem is NP-hard, and therefore, has no polynomial-time algorithm (unless P = NP ). Also, we show that the problem is FPT parameterized by the treewidth of the input graph. Furthermore, we show that the problem parameterized by k is W2-hard and belongs to WP.

$$\mathcal {L}_1$$ graph is an effective way to represent data samples in many graph-oriented machine learning applications. Its original construction algorithm is nonparametric, and the graphs it generates may have high sparsity. Meanwhile, the construction algorithm also requires many iterative convex optimization calculations and is very time-consuming. Such characteristics would severely limit the application scope of $$\mathcal {L}_1$$ graph in many real-world tasks. In this paper, we design a greedy algorithm to speed up the construction of $$\mathcal {L}_1$$ graph. Moreover, we introduce the concept of “Ranked Dictionary” for $$\mathcal {L}_1$$ minimization. This ranked dictionary not only preserves the locality but also removes the randomness of neighborhood selection during the process of graph construction. To demonstrate the effectiveness of our proposed algorithm, we present our experimental results on several commonly used datasets using two different ranking strategies: One is based on Euclidean distance, and another is based on diffusion distance.

We show that every C6-free graph G has a C4-free, bipartite subgraph with at least 3e(G)/8 edges. Our proof is probabilistic and uses a theorem of Fredi etal. (2006) on C6-free graphs.

Eigen-functions are of key importance in graph mining since they can be used to approximate many graph parameters, such as node centrality, epidemic threshold, graph robustness, with high accuracy. As real-world graphs are changing over time, those parameters may get sharp changes correspondingly. Taking virus propagation network for example, new connections between infected and susceptible people appear all the time, and some of the crucial infections may lead to large decreasing on the epidemic threshold of the network. As a consequence, the virus would spread around the network quickly. However, if we can keep track of the epidemic threshold as the graph structure changes, those crucial infections would be identified timely so that counter measures can be taken proactively to contain the spread process. In our paper, we propose two online eigen-functions tracking algorithms which can effectively monitor those key parameters with linear complexity. Furthermore, we propose a general attribution analysis framework which can be used to identify important structural changes in the evolving process. In addition, we introduce an error estimation method for the proposed eigen-functions tracking algorithms to estimate the tracking error at each time stamp. Finally, extensive evaluations are conducted to validate the effectiveness and efficiency of the proposed algorithms. © 2016 Wiley Periodicals, Inc. Statistical Analysis and Data Mining: The ASA Data Science Journal, 2016

In this paper we survey the behavior of various graph operations on the graph parameters clique-width and NLC-width. We give upper and lower bounds for the clique-width and NLC-width of the modified graphs in terms of the clique-width and NLC-width of the involved graphs. Therefor we consider the binary graph operations join, co-join, sum, difference, products, corona, substitution, and 1-sum, and the unary graph operations quotient, subgraph, edge complement, bipartite edge complement, power of graphs, switching, local complementation, edge addition, edge subdivision, vertex identification, and vertex addition.

The M inimum L inear A rrangement (MLA) problem involves embedding a given graph on the integer line so that the sum of the edge lengths of the embedded graph is minimized. Most layout problems are either intractable or not known to be tractable, parameterized by the treewidth of the input graph. We investigate MLA with respect to three parameters that provide more structure than treewidth. In particular, we give a factor (1 + ε)-approximation algorithm for MLA parameterized by (ε, k ), where k is the vertex cover number of the input graph. By a similar approach, we obtain two FPT algorithms that exactly solve MLA parameterized by, respectively, the max leaf and edge clique cover numbers of the input graph.

The energy E ( G ) of a graph G is defined as the sum of the absolute values of the eigenvalues of its adjacency matrix. If a graph G of order n has the same energy as the complete graph K n , i.e., if E ( G ) = 2 ( n − 1 ) , then G is said to be borderenergetic. We obtain three asymptotically tight bounds on the edge number of borderenergetic graphs. Then, by using disconnected regular graphs we construct connected non-complete borderenergetic graphs.

In this paper, we leverage the concept of the metric backbone to improve the efficiency of large-scale graph analytics. The metric backbone is the minimum subgraph that preserves the shortest paths of a weighted graph. We use the metric backbone in place of the original graph to compute various graph metrics exactly or with good approximation. By computing on a smaller graph, we improve the performance of graph analytics applications on two different systems, a batch graph processing system and a graph database. Further, we provide an algorithm for the computation of the metric backbone on large graphs. While one can compute the metric backbone by solving the all-pairs-shortest-paths problem, this approach incurs prohibitive time and space complexity for big graphs. Instead, we propose a heuristic that makes computing the metric backbone practical even for large graphs. Additionally, we analyze several real datasets of different sizes and domains and we show that we can approximate the metric backbone by removing only first-order semi-metric edges; edges for which a shorter two-hop path exists. We provide a distributed implementation of our algorithm and apply it in large scale scenarios. We evaluate our algorithm using a variety of real graphs, including a Facebook social network subgraph of ~50 billion edges. We measure the impact of using the metric backbone on runtime performance in two graph management systems. We achieve query speedups of up to 6.7x in the Neo4j commercial graph database and job speedups of up to 6x in the Giraph graph processing system.

We describe the clique-width of path powers by an exact formula, depending only on the number of vertices and the clique number. As a consequence, the clique-width of path powers can be computed in linear time. Path powers are a graph class of unbounded clique-width. Prior to our result, square grids constituted the only known graph class of unbounded clique-width with a similar result. We also show that clique-width and linear clique-width coincide on path powers.

Visualizing dynamic graphs is challenging due to the many data dimensions to be displayed such as graph vertices and edges with their attached weights or attributes and the additional time dimension. Moreover, edge directions with multiplicities and the graph topology are also important inherent features. However, in many dynamic graph visualization techniques each graph in a sequence is treated the same way, i.e., it is visually encoded in the same visual metaphor or even in the same layout. This visualization strategy can be problematic if the graphs are changing topologically over time, i.e., if a sparse graph becomes denser and denser over time or a star pattern is changing into a dense cluster of connected vertices. Such a dynamic graph data scenario demands for a visualization approach which is able to adapt the applied visual metaphor to each graph separately. In this paper we describe the dynamic graph wall to solve this problem by using multiple visual metaphors for dynamic graphs which are computed automatically by algorithms analysing each individual graph based on a given repertoire of graph features. The biggest issue in this technique for the graph dynamics, however, is the preservation of the viewer’s mental map at metaphor changes, i.e., to guide him through the graph changes with the goal to explore the data for time-varying patterns. To reach this goal we support the analyst by an interactive highlighting feature but we also display graphs in comparative metaphor rows to visually investigate the commonalities and differences over time. Graphical Abstract text

Triangle listing is a basic operator when dealing with many graph problems. However, in-memory algorithms do not work well with recently developed massive graphs such as social networks because these graphs cannot be accommodated in the memory. Thus, external memory-based algorithms have been proposed recently, but these approaches still require frequent multiple scans of the whole graph on the disk and large volumes of calculations are performed that involve the whole graph during every iteration. In this study, we propose a novel index-based method for listing triangles in massive graphs. First, we present new notions for the vertex range index and potential cone vertex index. Next, we propose an index join-based triangle listing algorithm. Our method accesses the indexed data asynchronously and joins them to list triangles using a multi-threaded parallel processing technique. Based on experiments, we demonstrate that our algorithm outperforms the state-of-the-art solution methods by three to eight times in terms of the wall clock time.

Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This paper surveys several graph parameters tied to treewidth, including separation number, tangle number, well-linked number and Cartesian tree product number. We review many results in the literature showing these parameters are tied to treewidth. In a number of cases we also improve known bounds, provide simpler proofs and show that the inequalities presented are tight., Comment: 22 pages, 1 figure

The class of cographs is known to have unbounded linear clique-width. We prove that a hereditary class of cographs has bounded linear clique-width if and only if it does not contain all quasi-threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes., 10 pages. Accepted for J. Graph Theory

A co-complete k -partite graph G = (V1,V2, … ,Vk, E), k ≥ 2 is a graph with the smallest number k of disjoint parts in which any pair of vertices in the same part is at a distance two. The number of parts in co-complete k -partite graph G is denoted by k (G). In this paper, we investigate k() , k(L(G)), k(M(G)) and k(T(G)), where , L(G) , M(G) and T(G) are complement graph, line graph, middle graph and total graph, respectively of some standard graphs. We also discuss the relationship between them. Each set in the partition has subpartitions such that each set in the subpartition induces K1 or any two vertices in this subpartition are at distance two and this result has significance in providing a stable network.

The idea of positional inverted index is exploited for indexing of graph database. The main idea is the use of hashing tables in order to prune a considerable portion of graph database that cannot contain the answer set. These tables are implemented using column-based techniques and are used to store graphs of database, frequent sub-graphs and the neighborhood of nodes. In order to exact checking of remaining graphs, the vertex invariant is used for isomorphism test which can be parallel implemented. The results of evaluation indicate that proposed method outperforms existing methods.

The problem of modeling and composing of aggregate systems is considered. The system components are described with finite automata with multiple entries and exits. The communication between automata is described with message passing over simplex communication channels. The system is described with a directed graph of links. Each node of the graph corresponds to automaton of a component and an arc corresponds to a communication channel connecting exit of one automaton with entry of another automaton. Automaton of the graph node in each state can accept multiple messages from its entries (at most one message from each entry) and send multiple messages to its exits (at most one message to each exit). Entries (exits) of the automata not connected to exits (entries) of automata are considered to be external and used for communication between the system and its environment. The automata of the system operate synchronously: on each cycle each automaton performs one transition. A transition of an automaton imposes requirements on states of all its entries and exits (messages in them are specified) and explicitly specifies subset of entries and exits through which the messages are received or sent, respectively. Synchronous communication between automata means that for each link the requirements of the automata connected with this link must conform to each other. It makes possible to describe a wider spectrum of automata behavior. For example, a priority of message receiving: if there are multiple message in the automata entries, it can receive messages with the highest priority and discard the rest of the messages. It also makes possible for the automaton to receive messages regardless of ability to simultaneously send some message to some exit. A composition of the automata of the system according to the graph of links is defined and its associativity is proved. In conclusion, the directions of future research are described.

We define various features that characterize individual node assignments.Based on the features we train a classifier to predict the correctness of assignments.We confirm that our methodology predicts assignment correctness with high accuracy. Due to their high representational power and flexibility, graphs have emerged as a widely used data structure for complex pattern representation. The advantages of graphs are, however, at the expense of a substantial increase of the computational complexity of the associated algorithms. For instance, exact graph similarity or distance can be computed in exponential time only. An algorithmic framework based on bipartite graph matching (allowing graph dissimilarity computation in cubic time) has been presented recently. However, this fast computation leads in general to some incorrect node assignments with respect to a globally optimal graph matching. In this paper we present a novel methodology for predicting which of the node assignments are actually incorrectly assigned by this approximation. To this end, a comprehensive set of features - which numerically characterize the assignments - is defined and extracted from the underlying graphs. These features are in turn used for training a statistical classifier, which can eventually be employed for predicting unseen assignments. The power and applicability of our novel approach is empirically verified on eight real world data sets.

Many graph parameters of grid-like graphs are studied because of their algorithmic consequences. An important concept in this context is that of treewidth. Treewidth of graphs is a graph parameter for measuring how close a graph is to a tree. In this paper, we study the treewidth of toroidal grids and show that the treewidth of the n × n toroidal grid is either 2 n - 2 or 2 n - 1 . We then show that these bounds are tight in some cases. To show the lower bounds, we construct brambles of high orders.

International audience; We consider hereditary classes of bipartite graphs where clique-width is bounded, but linear clique-width is not. Our goal is identifying classes that are critical with respect to linear clique-width. We discover four such classes and conjecture that this list is complete, i.e. a hereditary class of bipartite graphs of bounded clique-width that excludes a graph from each of the four critical classes has bounded linear clique-width.

Graph decompositions are important for algorithmic purposes and for graph structure theory. We relate the split decomposition introduced by Cunnigham to vertex substitution, graph grammars and clique-width. For this purpose, we extend the usual notion of substitution, upon which modular decomposition is based, by considering graphs with dead (or non-boundary) vertices. We obtain a graph grammar for distance-hereditary graphs consisting of four rules collected in a single equation. We also bound the clique-width of a graph in terms of those of the components of a split decomposition that need not be canonical. For extending these results to directed graphs and their split decompositions (that we handle formally as graph-labelled trees), we need another extension of substitution : instead of two types of vertices, dead or alive as for undirected graphs, we need four types, in order to encode edge directions. We bound linearly the clique-width of a directed graph G in terms of the maximal clique-width of a component arising in a graph-labelled tree that defines G . This result concerns all directed graphs, not only the strongly connected ones considered by Cunningham.

MotivationThe de Bruijn graph is a simple and efficient data structure that is used in many areas of sequence analysis including genome assembly, read error correction and variant calling. The data structure has a single parameter k, is straightforward to implement and is tractable for large genomes with high sequencing depth. It also enables representation of multiple samples simultaneously to facilitate comparison. However, unlike the string graph, a de Bruijn graph does not retain long range information that is inherent in the read data. For this reason, applications that rely on de Bruijn graphs can produce sub-optimal results given their input.ResultsWe present a novel assembly graph data structure: the Linked de Bruijn Graph (LdBG). Constructed by adding annotations on top of a de Bruijn graph, it stores long range connectivity information through the graph. We show that with error-free data it is possible to losslessly store and recover sequence from a Linked de Bruijn graph. With assembly simulations we demonstrate that the LdBG data structure outperforms both the de Bruijn graph and the String Graph Assembler (SGA). Finally we apply the LdBG to Klebsiella pneumoniae short read data to make large (12 kbp) variant calls, which we validate using PacBio sequencing data, and to characterise the genomic context of drug-resistance genes.AvailabilityLinked de Bruijn Graphs and associated algorithms are implemented as part of McCortex, available under the MIT license at https://github.com/mcvean/mccortex.Contactturner.isaac@gmail.com.

This paper introduces the Bag of Graphs (BoG), a Bag-of-Words model that encodes in graphs the local structures of a digital object. We present a formal definition, introducing concepts and rules that make this model flexible and adaptable for different applications. We define two BoG-based methods – Bag of Singleton Graphs (BoSG) and Bag of Visual Graphs (BoVG), which create vector representations for graphs and images, respectively. We evaluate the Bag of Singleton Graphs (BoSG) for graph classification on four datasets of the IAM repository, obtaining significant results in accuracy and execution time. The method Bag of Visual Graphs (BoVG) is evaluated for image classification on Caltech and ALOI datasets, and for remote sensing image classification on images of Monte Santo and Campinas datasets. This framework opens possibilities for retrieval, classification, and clustering tasks on large datasets that use graph-based representations impractical before due to the complexity of inexact graph matching.

Parameterized complexity theory has enabled a refined classification of the difficulty of NP-hard optimization problems on graphs with respect to key structural properties, and so to a better understanding of their true difficulties. More recently, hardness results for problems in P were achieved using reasonable complexity theoretic assumptions such as: Strong Exponential Time Hypothesis (SETH), 3SUM and All-Pairs Shortest-Paths (APSP). According to these assumptions, many graph theoretic problems do not admit truly subquadratic algorithms, nor even truly subcubic algorithms (Williams and Williams, FOCS 2010 and Abboud, Grandoni, Williams, SODA 2015). A central technique used to tackle the difficulty of the above mentioned problems is fixed-parameter algorithms for polynomial-time problems with polynomial dependency in the fixed parameter (P-FPT). This technique was introduced by Abboud, Williams and Wang in SODA 2016 and continued by Husfeldt (IPEC 2016) and Fomin et al. (SODA 2017), using the treewidth as a parameter. Applying this technique to clique-width, another important graph parameter, remained to be done. In this paper we study several graph theoretic problems for which hardness results exist such as cycle problems (triangle detection, triangle counting, girth, diameter), distance problems (diameter, eccentricities, Gromov hyperbolicity, betweenness centrality) and maximum matching. We provide hardness results and fully polynomial FPT algorithms, using clique-width and some of its upper-bounds as parameters (split-width, modular-width and $P\_4$-sparseness). We believe that our most important result is an ${\cal O}(k^4 \cdot n + m)$-time algorithm for computing a maximum matching where $k$ is either the modular-width or the $P\_4$-sparseness. The latter generalizes many algorithms that have been introduced so far for specific subclasses such as cographs, $P\_4$-lite graphs, $P\_4$-extendible graphs and $P\_4$-tidy graphs. Our algorithms are based on preprocessing methods using modular decomposition, split decomposition and primeval decomposition. Thus they can also be generalized to some graph classes with unbounded clique-width.

This paper proposes a framework for supporting the design process by defining design requirements over graph-based representations of designs. First, hierarchical layout hypergraphs (HL-graphs) representing designs and hierarchical layout graph grammars generating them are specified. Then, local and global graph requirements over HL-graphs, which correspond to design constraints, are defined. The proposed ontological interpretations transform first-order and monadic second-order logic formulas expressing design criteria into equivalent local and global graph requirements. The satisfiability of graph requirements by representations of designs allows for checking correctness of design solutions. The approach is illustrated on examples of designing floor layouts of buildings. Hierarchical graphs representing designs and grammars generating them are defined.Local and global requirements over graph representations of designs are specified.The proposed interpretations transform logic formulas into graph requirements.The satisfiability of graph requirements by representations of designs is tested.The approach is illustrated on examples of designing building layouts.

Tree-width and clique-width are two important graph complexity measures that serve as parameters in many fixed-parameter tractable algorithms. We give two algorithms that transform tree-decompositions represented by normal trees into clique-width terms (a rooted tree is normal for a graph if its nodes are the vertices of the graph and every two adjacent vertices are on a path of the tree starting at the root). As a consequence, we obtain that, for certain classes of sparse graphs, clique-width is polynomially bounded in terms of tree-width. It is even linearly bounded for planar graphs and incidence graphs. These results are useful in the construction of model-checking algorithms for problems described by monadic second-order formulae, including those allowing edge set quantifications.

A neutrosophic cubic set is the hybridization of the concept of a neutrosophic set and an interval neutrosophic set. A neutrosophic cubic set has the capacity to express the hybrid information of both the interval neutrosophic set and the single valued neutrosophic set simultaneously. In this paper, the authors Surapati Pramanik, Shyamal Dalapati, Shariful Alam and Tapan Kumar Roy propose score and accuracy functions for neutrosophic cubic sets and prove their basic properties. They also develop a strategy for ranking of neutrosophic cubic numbers based on the score and accuracy functions. The authors firstly develop a TODIM (Tomada de decisao interativa e multicritévio) in the neutrosophic cubic set (NC) environment, which is called the NC-TODIM. They establish a new NC-TODIM strategy for solving multi-attribute group decision-making (MAGDM) problems in neutrosophic cubic set environments. They illustrate the proposed NC-TODIM strategy for solving a multi-attribute group decision-making problem to show the applicability and effectiveness of the developed strategy. They also conduct sensitivity analysis to show the impact of the ranking order of the alternatives on the different values of the attenuation factor of losses for multi-attribute group decision-making strategies.

The sparsest cut problem consists of identifying a small set of edges that breaks the graph into balanced sets of vertices. The normalized cut problem balances the total degree, instead of the size, of the resulting sets. Applications of graph cuts include community detection and computer vision. However, cut problems were originally proposed for static graphs, an assumption that does not hold in many modern applications where graphs are highly dynamic. In this paper, we introduce the sparsest and normalized cut problems in temporal graphs, which generalize their standard definitions by enforcing the smoothness of cuts over time. We propose novel formulations and algorithms for computing temporal cuts using spectral graph theory, multiplex graphs, divide-and-conquer and low-rank matrix approximation. Furthermore, we extend our formulation to dynamic graph signals, where cuts also capture node values, as graph wavelets. Experiments show that our solutions are accurate and scalable, enabling the discovery of dynamic communities and the analysis of dynamic graph processes.

We prove that the strong perfect graph conjecture holds for graphs that do not contain parachutes or proper wheels. This is done by showing the following theorem: If a graph G contains no odd hole, no parachute and no proper wheel, then G is bipartite or the line graph of a bipartite graph or G contains a star cutset or an extended strong 2-join or Ḡ is disconnected. To prove this theorem, we prove two decomposition theorems which are interesting in their own rights. The first is a generalization of the Burlet–Fonlupt decomposition of Meyniel graphs by clique cutsets and amalgams. The second is a precursor of the recent decomposition theorem of Chudnovsky, Robertson, Seymour and Thomas for Berge graphs that contain a line graph of a bipartite subdivision of a 3-connected graph.

Network motif discovery is the problem of finding subgraphs of a network that occur more frequently than expected, according to some reasonable null hypothesis. Such subgraphs may indicate small scale interaction features in genomic interaction networks or intriguing relationships involving actors or a relationship among airlines. When nodes are labeled, they can carry information such as the genomic entity under study or the dominant genre of an actor. For that reason, labeled subgraphs convey information beyond structure and could therefore enjoy more applications. To identify statistically significant motifs in a given network, we propose an analytical method (i.e. simulation-free) that extends the works of Picard et al. (J Comput Biol 15(1):1---20, 2008) and Schbath et al. (J Bioinform Syst Biol 2009(1):616234, 2009) to label-dependent scale-free graph models. We provide an analytical expression of the mean and variance of the count under the Expected Degree Distribution random graph model. Our model deals with both induced and non-induced motifs. We have tested our methodology on a wide set of graphs ranging from protein---protein interaction networks to movie networks. The analytical model is a fast (usually faster by orders of magnitude) alternative to simulation. This advantage increases as graphs grow in size.

We prove that in the class of bi-complement reducible graphs linear clique-width is unbounded and show that this class contains exactly two minimal hereditary subclasses of unbounded linear clique-width.

It is shown that if G has clique-width k, and a corresponding tree decomposition is known, then a diagonal matrix congruent to \(A - cI\) for constants c, where A is the adjacency matrix of the graph G of order n, can be computed in time \(O(k^2 n)\). This allows to quickly tell the number of eigenvalues in a given interval.

This paper studies continuous pattern detection over large evolving graphs, which plays an important role in monitoring-related applications. The problem is challenging due to the large size and dynamic updates of graphs, the massive search space of pattern detection and inconsistent query results on dynamic graphs. This paper first introduces a snapshot isolation requirement, which ensures that the query results come from a consistent graph snapshot instead of a mixture of partial evolving graphs. Second, we propose an SSD (single sink directed acyclic graph) plan friendly to vertex-centric-distributed graph processing frameworks. SSD plan can guide the message transformation and transfer among graph vertices, and determine the satisfaction of the pattern on graph vertices for the sink vertex. Third, we devise strategies for major steps in the SSD evaluation, including the location of valid messages to achieve snapshot isolation, AO-List to determine the satisfaction of transition rule over dynamic graph, and message-on-change policy to reduce outgoing messages. The experiments on billion-edge graphs using Giraph, an open source implementation of Pregel, illustrate the efficiency and effectiveness of our method.

Tree-decompositions are the cornerstone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. However, practical algorithms computing tree-decompositions only exist for graphs with treewidth less than 4. In such graphs, the time-complexity of dynamic programming algorithms is dominated by the size (number of bags) of the tree-decompositions. It is then interesting to minimize the size of the tree-decompositions. In this extended abstract, we consider the problem of computing a tree-decomposition of a graph with width at most k and minimum size. We prove that the problem is NP-complete for any fixed k ≥ 4 and polynomial for k ≤ 2; for k = 3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs.

Every graph property expressible in monadic second-order (MSO) logic, can be checked in linear time on graphs of bounded tree-width by means of finite automata running on terms denoting tree-decompositions. Implementing these automata is difficult because of their huge sizes. Fly-automata (FA) are deterministic automata that compute the necessary states and transitions when running (instead of looking into tables); they overcome this difficulty. Previously, we constructed FA to check MSO properties of graphs of bounded clique-width. An MSO property with edge quantifications (called an MSO2 property) is an MSO property of the incidence graph and, graphs of tree-width k have incidence graphs of clique-width O ( k ) . Our existing constructions can be used for MSO2 properties of graphs of bounded tree-width. We examine concrete aspects of this adaptation.

We characterize the structure of graph G and the integers k for which the kth power of graph G, Gk is (2, 2) bipartite whenever the graph G is among cycle, n-cube and tree.