N1H111SM's Miniverse

Subgraph Related

字数统计: 729阅读时长: 4 min
2020/03/03 Share


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_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).

  1. 1. Subgraph isomorphism problem
  2. 2. Induced subgraph
  3. 3. Edge contraction
  4. 4. Graph minor
  5. 5. Graph clique
  6. 6. Graphlets
  7. 7. GRAph ALigner (GRAAL)