Graph



Complex Networks
Single-scale networks
similar to a lattice in that every node has (roughly) the same degree
Scale-free networks
if its degree distribution, i.e., the probability that a node selected uniformly at random has a certain number of links (degree), follows a particular mathematical function called a power law.
:: the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as
P(k) ~  k^{-γ} , γ is a parameter whose value is typically in the range 2 < \gamma < 3
Small-world networks
by analogy with the small-world phenomenon (popularly known as six degrees of separation).
with the addition of only a small number of long-range links, a regular graph, in which the diameter is proportional to the size of the network, can be transformed into a "small world" in which the average number of edges between any two vertices is very small (mathematically, it should grow as the logarithm of the size of the network), while the clustering coefficient stays large.
 It is known that a wide variety of abstract graphs exhibit the small-world property, e.g., random graphs and scale-free networks. Further, real world networks such as theWorld Wide Web and the metabolic network also exhibit this property.
::  the typical distance L between two randomly chosen nodes (the number of steps required) grows proportionally to the logarithm of the number of nodesN in the network L ~ log N

Cohen and Havlin showed analytically that scale-free networks are ultra-small worlds. In this case, due to hubs, the shortest paths become significantly smaller and scale as L ~ log log N




Isomorphism in Graphs
an isomorphism of graphs G and H is a bijection between the vertex sets of G and H
f:V(G) -> V(H)
such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly called "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection.


Dual Graph
has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G.
symmetric: If H is a dual of G, then G is a dual of H (if G is connected)




Steiner Tree Problem
given a flow network in which each edge is given both a cost and a capacity, and a matrix of flow amounts between different pairs of terminal vertices; the task is to find a subnetwork of minimum cost whose capacities are sufficient to support a flow with the given flow amounts between any pair of terminals. When the flow amounts are all equal, this reduces to the classical Steiner tree problem.



Laplacian Matrix
is the difference of the degree matrix D and the adjacency matrix A of the graph. In the case of directed graphs, either the indegree or outdegree might be used, depending on the application.  So it's value is the degree of the node on the diagonal and -1 if those two nodes are adjacent.

[2 0 0 0 0 0]           [0 1 0 0 1 0]
|0 3 0 0 0 0|            |1 0 1 0 1 0|
|0 0 2 0 0 0|     -      |0 1 0 1 0 0|
|0 0 0 3 0 0|            |0 0 1 0 1 1|
|0 0 0 0 3 0|            |1 1 0 1 0 0|
[0 0 0 0 0 1]           [0 0 0 1 0 0]


For a graph G and its Laplacian matrix L with eigenvalues  λ0 <= λ1 <= ...<= λn-1,
L is always positive-semidefinite (∀i, λi >= 0, λ0 = 0)
The number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph.
λ0 = 0 (because every Laplacian matrix has an eigenvector v0 = [1 1 ... 1] that, for each row, adds the corresponding node's degree (from the diagonal) to a "-1" for each neighbor so that L v0 = 0)
The second smallest eigenvalue of L is the algebraic connectivity (or Fiedler value) of G.

Algebraic Connectivity
The second smallest eigenvalue of the laplacian matrix of a graph. It is greater than zero if and only if the graph is connected.
This is a corollary to the fact that the number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph. The magnitude of this value reflects how well connected the overall graph is, and has been used in analysing the robustness and synchronizability of networks.

Connectivity
It asks for the minimum number of elements (nodes or edges) which need to be removed to disconnect the remaining nodes from each other.
• Weakly connected: if changing directed edges of a graph to undirected makes it connected.
Connected: if there is a directed path from u to v for every pair
Strongly connected: if there is a directed path from u to v and from v to u for every pair
k-connectivity: if there does not exist a set of k-1 vertices whose removal disconnects the graph.
Edge connectivity: specific edge would disconnect the graph, that edge is called a bridge. More generally, the edge cut of G is a group of edges whose total removal renders the graph disconnected.
The greatest number of independent paths between u and v is written as κ′(u,v), and the greatest number of edge-independent paths between u and v is written as λ′(u,v).
It is closely related to the theory of network flow problems. It is an important measure of its robustness as a network.

Network Flow
for each edge of the graph there is a capacity that it can handle and there is a flow that can flow through it. flow <= capacity. flow-in=flow-out unless source or destination. flow-in= - flow-out





Subpages (1): Random Graph
Comments