Graph Theory Concepts

graph_theory_concepts.md

Graph Theory Concepts

• clique https://en.wikipedia.org/wiki/Clique_(graph_theory) - a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent (its induced subgraph is complete).Finding the largest clique in a graph is NP-complete problem with exponential running time see https://en.wikipedia.org/wiki/Clique_problem

• Ramsey number https://en.wikipedia.org/wiki/Ramsey%27s_theorem the minimum number of vertices, v = R(m, n), such that all undirected simple graphs of order v, contain a clique of order m, or an independent set of order n. Ramsey's theorem states that such a number exists for all m and n.

• connectivity https://en.wikipedia.org/wiki/Connectivity_(graph_theory) the minimum number of elements (nodes or edges) that need to be removed to disconnect the remaining nodes from each other. For network flow problems. The connectivity of a graph is an important measure of network resilience.

• Vertex Cover https://en.wikipedia.org/wiki/Vertex_cover set of vertices such that each edge of the graph is incident to at least one vertex of the set.

• Bipartite graph https://en.wikipedia.org/wiki/Bipartite_graph [AKA bigraph] a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent.

• Assortativity https://en.wikipedia.org/wiki/Assortativity [AKA assortative mixing] a preference for a network's nodes to attach to others according to a specific measure of similarity, in terms of a node's degree.

• Bipartite network projection https://en.wikipedia.org/wiki/Bipartite_network_projection method for compressing information about bipartite networks, aimed at minimizing information loss.

• Bridge https://en.wikipedia.org/wiki/Bridge_(graph_theory) [AKA isthmus, cut-edge, or cut arc] - an edge of a graph whose deletion increases its number of connected components.[1] Equivalently, an edge is a bridge if and only if it is not contained in any cycle. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

• degree https://en.wikipedia.org/wiki/Degree_(graph_theory) [AKA valency] - number of edges incident to a vertex, with loops counted twice.

• eigenvectors and eigenvalues https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors characteristic vector of a linear transformation - a non-zero vector that only changes by an overall scale when that linear transformation is applied to it. the eigenvalue is a characteristic root associated with the eigenvector v. If the vector space V is finite-dimensional, then the linear transformation T can be represented as a square matrix A, and the vector v by a column vector, rendering the above mapping as a matrix multiplication on the left hand side and a scaling of the column vector on the right hand side. Geometrically an eigenvector, corresponding to a real nonzero eigenvalue, points in a direction that is stretched by the transformation and the eigenvalue is the factor by which it is stretched. If the eigenvalue is negative, the direction is reversed.

• eigenvector centrality https://en.wikipedia.org/wiki/Eigenvector_centrality (AKA eigencentrality) is a measure of the influence of a node in a network. Google's PageRank and the Katz centrality are variants of this

• algebraic connectivity https://en.wikipedia.org/wiki/Algebraic_connectivity (AKA Fiedler eigenvalue) of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G. The magnitude of this value reflects how well connected the overall graph is. It has been used in analysing the robustness and synchronizability of networks. Spanning tree https://en.wikipedia.org/wiki/Spanning_tree a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges.

• Closeness centrality https://en.wikipedia.org/wiki/Closeness_centrality a measure of centrality of a node to a network, calculated as the sum of the length of the shortest paths between the node and all other nodes in the graph. Thus the more central a node is, the closer it is to all other nodes.

• rooted graph https://en.wikipedia.org/wiki/Rooted_graph a graph in which a vertex has been distinguished as the root

• Flow network https://en.wikipedia.org/wiki/Flow_network a directed graph where each edge has a capacity and receives a flow

• reachability https://en.wikipedia.org/wiki/Reachability refers to the ability to get from one vertex to another within a graph.

• Estrada index https://en.wikipedia.org/wiki/Estrada_index In chemical graph theory, a topological index of protein folding.

• chordal graph https://en.wikipedia.org/wiki/Chordal_graph is chordal if every cycle of length at least 4 has a chord (an edge joining two nodes not adjacent in the cycle).

• Clustering - Algorithms to characterize the number of triangles in a graph.

• graph coloring https://en.wikipedia.org/wiki/Graph_coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.

• Cut https://en.wikipedia.org/wiki/Cut_(graph_theory) - a partition of of a graph into two subsets S and T. The cut-set of a cut is the set of edges that have one endpoint in S and the other endpoint in T. If s and t are specified vertices of the graph G, then an s–t cut is a cut in which s belongs to the set S and t belongs to the set T.

• Degeneracy https://en.wikipedia.org/wiki/Degeneracy_(graph_theory) - A k-core of a graph G is a maximal connected subgraph of G in which all vertices have degree at least k. Equivalently, it is one of the connected components of the subgraph of G formed by repeatedly deleting all vertices of degree less than k.

• Covering Graph https://en.wikipedia.org/wiki/Covering_graph a graph C is a covering graph of another graph G if there is a covering map from the vertex set of C to the vertex set of G. A covering map f is a surjection and a local isomorphism: the neighbourhood of a vertex v in C is mapped bijectively onto the neighbourhood of f(v) in G. may also refer to a subgraph that contains either all edges (edge cover) or all vertexes (vertex cover).

• Cycle graph https://en.wikipedia.org/wiki/Cycle_graph [aka circular graph] consists of a single cycle: some vertices connected in a closed chain.

• Transitive closure https://en.wikipedia.org/wiki/Transitive_closure Given a directed graph, find out if a vertex j is reachable (there is a path) from another vertex i for all vertex pairs (i, j) in the given graph. The reach-ability matrix is called transitive closure of a graph.

• automorphism https://en.wikipedia.org/wiki/Graph_automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.

• regular graph https://en.wikipedia.org/wiki/Regular_graph a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. the indegree and outdegree of each vertex are equal to each other. called a k‑regular graph of degree k. Handshaking lemma: a regular graph of odd degree will contain an even number of vertices.

• distance-regular graph https://en.wikipedia.org/wiki/Distance-regular_graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and i = d(v, w).

• Hamiltonian path https://en.wikipedia.org/wiki/Hamiltonian_path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

• Dominator https://en.wikipedia.org/wiki/Dominator_(graph_theory) in control flow graphs, a node d dominates a node n if every path from the entry node to n must go through d. Notationally, this is written as d dom n. By definition, every node dominates itself.

• control flow graph https://en.wikipedia.org/wiki/Control_flow_graph (CFG) in computer science a graph notation representation of all paths that might be traversed through a program during its execution. Arose from boolean connectivity matrices for flow analysis.

• Eulerian path https://en.wikipedia.org/wiki/Eulerian_path a trail in a finite graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail which starts and ends on the same vertex.

• Maximum flow problem https://en.wikipedia.org/wiki/Maximum_flow_problem In optimization theory, find a feasible flow through a single-source, single-sink flow network that is maximum. A special case of the circulation problem.

• flow network https://en.wikipedia.org/wiki/Flow_network (AKA transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

• network simplex algorithm https://en.wikipedia.org/wiki/Network_simplex_algorithm a graph theoretic specialization of the simplex algorithm formulated as a minimum-cost flow problem - can be efficiently solved in polynomial time. Fast.

• Cosine similarity https://en.wikipedia.org/wiki/Cosine_similarity a measure of similarity between two non-zero vectors of an inner product space that measures the cosine of the angle between them. It is a judgment of orientation and not magnitude: two vectors with the same orientation have a cosine similarity of 1, two vectors at 90° have a similarity of 0, and two vectors diametrically opposed have a similarity of -1, independent of their magnitude. used in positive space, where the outcome is neatly bounded in [0,1].

• Graph Isomporhism an isomorphism of graphs G and H is a bijection between their vertex sets. Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. EXACT graph matching.

• Graph minor https://en.wikipedia.org/wiki/Graph_minor 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.

• independent set https://en.wikipedia.org/wiki/Independent_set_(graph_theory) [AKA stable set] - set of vertices in a graph, no two of which are adjacent. (for every two vertices in S, there is no edge connecting the two - each edge in the graph has at most one endpoint in S).

• maximal independent set (MIS) https://en.wikipedia.org/wiki/Maximal_independent_set - an independent set that is not a subset of any other independent set - no vertex outside the independent set may join it

• reciprocity https://en.wikipedia.org/wiki/Reciprocity_(network_science) - a measure of the likelihood of vertices in a directed network to be mutually linked.[1] Like the clustering coefficient, scale-free degree distribution, or community structure, reciprocity is a quantitative measure used to study complex networks.

• Rich-club coefficient https://en.wikipedia.org/wiki/Rich-club_coefficient - measure of the extent to which well-connected nodes also connect to each other.

• tournament https://en.wikipedia.org/wiki/Tournament_%28graph_theory%29 a directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph. every pair of distinct vertices is connected by a single directed edge. Landau (1953) used to model dominance relations in flocks of chickens. Current applications: voting theory and social choice theory.

• Beam search https://en.wikipedia.org/wiki/Beam_search a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. an optimization of best-first search that reduces its memory requirements.

• closeness (graph theory) https://en.wikipedia.org/wiki/Centrality#Closeness_centrality the shortest path between one vertex and another vertex

• Voronoi diagram https://en.wikipedia.org/wiki/Voronoi_diagram partitioning of a plane into regions based on distance to points in a specific subset of the plane. That set of points (called seeds, sites, or generators) is specified beforehand, and for each seed there is a corresponding region consisting of all points closer to that seed than to any other. These regions are called Voronoi cells. The Voronoi diagram of a set of points is dual to its Delaunay triangulation. Wiener index https://en.wikipedia.org/wiki/Wiener_index In chemical graph theory, the Wiener index (also Wiener number) is a topological index of a molecule, defined as the sum of the lengths of the shortest paths between all pairs of vertices in the chemical graph representing the non-hydrogen atoms in the molecule.[1]

• similarity measure https://en.wikipedia.org/wiki/Similarity_measure In statistics and related fields, a real-valued function that quantifies the similarity between two objects. Usually some inverse of distance metrics: they take on large values for similar objects and either zero or a negative value for very dissimilar objects. Cosine similarity is a commonly used similarity measure for real-valued vectors, to score the similarity of documents in the vector space model. In machine learning, the RBF kernel is a similarity function.

• Statistical parsing https://en.wikipedia.org/wiki/Statistical_parsing NLP methods that associate grammar rules (defining the valid sentences) with a probability. provides the relative frequency of any given grammar rule and, by deduction, the probability of a complete parse for a sentence. statistical parsers search over a space of all candidate parses, and the computation of each candidate's probability, to derive the most probable parse of a sentence. The Viterbi algorithm is one popular method of searching for the most probable parse.

• Context-free grammar https://en.wikipedia.org/wiki/Context-free_grammar In formal language theory, a set of production rules (placeholder substitutions) that describe all possible strings in a given formal language.

• edit distance https://en.wikipedia.org/wiki/Edit_distance In computational linguistics, Bioinformatics and computer science, quantifies how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other. Different definitions of an edit distance use different sets of string operations. The Levenshtein distance operations are the removal, insertion, or substitution of a character in the string.

• Levenshtein distance https://en.wikipedia.org/wiki/Levenshtein_distance In information theory, Linguistics and computer science, a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. 1965.

• band matrix https://en.wikipedia.org/wiki/Band_matrix a sparse matrix whose non-zero entries are confined to a diagonal band, comprising the main diagonal and zero or more diagonals on either side.

• spectral graph theory https://en.wikipedia.org/wiki/Spectral_graph_theory the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix.

• adjacency matrix https://en.wikipedia.org/wiki/Adjacency_matrix a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. The relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory. Difference from incidence matrix whose elements indicate whether vertex–edge pairs are incident or not, and degree matrix which contains information about the degree of each vertex.

• incidence matrix https://en.wikipedia.org/wiki/Incidence_matrix a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related (called incident in this context) and 0 if they are not.

• Degree matrix https://en.wikipedia.org/wiki/Degree_matrix a diagonal matrix which contains information about the degree of each vertex (number of edges attached to it). It is used together with the adjacency matrix to construct the Laplacian matrix.

• Laplacian Matrix [AKA admittance matrix, Kirchhoff matrix or discrete Laplacian] a matrix representation of a graph. using Kirchhoff's theorem, it can be used to calculate the number of spanning trees for a given graph. The sparsest cut of a graph can be approximated through the second smallest eigenvalue of its Laplacian by Cheeger's inequality.

• Matrix spectrum https://en.wikipedia.org/wiki/Spectrum_of_a_matrix the spectrum of a matrix is the set of its eigenvalues. The determinant of the matrix equals the product of its eigenvalues & the trace of the matrix equals the sum of its eigenvalues. The pseudo-determinant for a singular matrix is the product of its nonzero eigenvalues (the density of multivariate normal distribution). Eg PageRank is interested in the dominant eigenvalue, i.e. that which is largest in absolute value.

• Graph Edit Distance https://en.wikipedia.org/wiki/Graph_edit_distance a measure of similarity (or dissimilarity) between two graphs. First formalized in 1983 for inexact graph matching. Related to the string edit distance between strings - classical methods such as Levenshtein distance,Hamming distance and Jaro–Winkler distance may be interpreted as graph edit distances between suitably constrained graphs. Likewise, graph edit distance is also a generalization of tree edit distance between rooted trees.

• Belief propagation https://en.wikipedia.org/wiki/Belief_propagation [AKA sum-product message passing] - a message-passing algorithm for performing inference on graphical models, such as Bayesian networks and Markov random fields. It calculates the marginal distribution for each unobserved node, conditional on any observed nodes. used in low-density parity-check codes, turbo codes, free energy approximation, and satisfiability. The algorithm was first proposed by Judea Pearl in 1982 on trees, and was later extended to polytrees, then on general graphs.

• Spectral theorem https://en.wikipedia.org/wiki/Spectral_theorem a linear operator or matrix can be diagonalized (represented as a diagonal matrix in some basis) --> can be reduced to much simpler computations.

• Spectral clustering https://en.wikipedia.org/wiki/Spectral_clustering in multivariate statistics, use the spectrum (eigenvalues) of the similarity matrix of the data to perform dimensionality reduction before clustering in fewer dimensions. Used in image analysis: segmentation-based object categorization.

• Link analysis https://en.wikipedia.org/wiki/Link_analysis - In network theory, used to evaluate relationships (connections) between graph nodes.

• Jaccard index https://en.wikipedia.org/wiki/Jaccard_index Intersection over Union - for comparing the similarity and diversity of sample sets.