Materials
Subgraph isomorphism problem
In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs $G$ and $H$ are given as input, and one must determine whether $G$ contains a subgraph that is isomorphic to $H$.
One reason to be interested in such a question is that many graph properties are hereditary for subgraphs, which means that a graph has the property if and only if all subgraphs have it too. Unfortunately, finding maximal subgraphs of a certain kind is often an NP-complete problem.
Induced subgraph
In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset.
Formally, let $G = (V, E)$ be any graph, and let $S\in V$ be any subset of vertices of $G$. Then the induced subgraph $G[S]$ is the graph whose vertex set is $S$ and whose edge set consists of all of the edges in $E$ that have both endpoints in $S$. The same definition works for undirected graphs, directed graphs, and even multigraphs.
Edge contraction
In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors.
Contractions are useful in structures where we wish to simplify a graph by identifying vertices that represent essentially equivalent entities. One of the most common examples is the reduction of a general directed graph to an acyclic directed graph by contracting all of the vertices in each strongly connected component. If the relation described by the graph is transitive, no information is lost as long as we label each vertex with the set of labels of the vertices that were contracted to form it.
Graph minor
In graph theory, an undirected graph $H$ is called a minor of the graph $G$ if $H$ can be formed from $G$ by deleting edges and vertices and by contracting edges. Many graph properties are hereditary for minors, which means that a graph has a property if and only if all minors have it too.
Graph clique
In the mathematical area of graph theory, a cliqueis a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete.
A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique. Some authors define cliques in a way that requires them to be maximal, and use other terminology for complete subgraphs that are not maximal.
A maximum clique of a graph, $G$, is a clique, such that there is no clique with more vertices. Moreover, the clique number $\omega (G)$ of a graph $G$ is the number of vertices in a maximum clique in $G$.
Graphlets
Graphlets_and_signature_similarities) are small connected non-isomorphic induced subgraphs of a large network. Graphlets differ from network motifs, since they must be induced subgraphs, whereas motifs are partial subgraphs. Graphlets were first introduced by Nataša Pržulj, when they were used as a basis for designing two new highly sensitive measures of network local structural similarities: the relative graphlet frequency distance (RGF-distance) and the graphlet degree distribution agreement (GDD-agreement).
- Relative graphlet frequency distance
- Graphlet degree distribution agreement
- Graphlet degree vectors (signatures) and signature similarities
GRAph ALigner (GRAAL)
GRAaph ALigner (GRAAL)) is an algorithm for global network alignment that is based solely on network topology. GRAAL matches pairs of nodes originating in different networks based on their graphlet degree signature similarities_and_signature_similarities), where a higher similarity between two nodes corresponds to a higher topological similarity between their extended neighborhoods (out to distance 4). GRAAL produces global alignments, i.e., it aligns each node in the smaller network to exactly one node in the larger network. The matching proceeds using a technique analogous to the “seed and extend” approach of the popular BLAST algorithm for sequence alignment: it first chooses a single “seed” pair of nodes (one node from each network) with high graphlet degree signature similarity. It then expands the alignment radially outward around the seed as far as practical using a greedy algorithm for details).
How to Form Subgraphs
From a graph, one can obtain subgraphs, or modules, by removing edges (cut edges) between nodes. Modularity is the divisibility of a graph into highly connected subgraphs with few edges between them. This may reflect the substructure of any spatial graph. Newman (2006) provides an algorithm for dividing a univariate graph into such subgraphs based on the eigenvectors of a characteristic matrix for the graph. This process of dividing the graph into modules is much like spatially constrained clustering (Fortin & Dale 2005), where the most similar nodes are joined into clusters, but only if they are adjacent in space (as defined by some algorithm; see sidebar, How to Join Nodes).
How to Compare Graph Structures
To compare graph structures, many metrics have been developed (Albert & Baraba ́si 2002, Estrada & Bodin 2008, Freeman 1977, Fortin 1994, Oden et al. 1993, Pascual-Hortal & Saura 2006, Urban & Keitt 2001, Wasserman & Faust 1994) to characterize different graph properties based on nodes [e.g., number of edges per node, degree of node assortativeness (Newman 2002), node importance to overall connectivity, and centrality of a node], based on edges (e.g., shortest path, path diameter), or based on the entire graph [e.g., diameter of a graph, network centrality metrics (Wasserman & Faust 1994)]. Each of these metrics assume that all the nodes have been included, and the metrics are sensitive to missing nodes to different degrees depending of the characteristics being measured; this sensitivity is referred to as the sampling issue (Clauset et al. 2008, Corson 2010, Lee et al. 2005). This sampling issue creates serious limitations for the interpretation of graph metrics when there is no assurance that there is a complete census of the objects depicted in the graph. Further comparisons of these metrics have been conducted by B. Rayfield, M.J. Fortin, and A. Fall (submitted), who proposed a classification framework for them based on the component of connectivity quantified and the structural level (element, neighborhood, cluster, and network) to which they can be applied.
Graph of graphs
A graph of graphs is a spatial graph where each node has its own associated graph representing some other structure (such as a food web). For example, Fortuna & Bascompte (2008) showed a graph of a metacommunity consisting of nodes, each of which contains a graph of multispecies interactions. Melia ́n et al. (2005) compared two complete graphs of five nodes representing habitats, with edges’ thickness depicting the number of shared trophic modules. The node representing each habitat has an associated tritrophic digraph showing a food chain with or without omnivory. As more spatial studies are completed, the number of examples of graphs of graphs will undoubtedly increase.