Graph Terminology
Graph Terminology
Graph
Graph
A graph is a collection of vertices ("nodes") and edges. Vertices are basically points, and edges connect two vertices. Edges can be undirected or directed (like a one-way street). Edges can also have weights associated with them. Let's say we had a graph representing a country, with vertices for cities and edges for highways between cities. In this case, the weight of an edge could be the distance between the two cities.
A connected graph is a graph where every vertex is reachable from every other vertex. This is not a connected graph, since there isn't a way to go from vertex to .
A connected graph is a graph where every vertex is reachable from every other vertex. This is not a connected graph, since there isn't a way to go from vertex
1
2
Out[]=
A complete graph is a graph where an edge exists between every pair of vertices. This is a complete graph with five vertices.
Out[]=
Isomorphism
Isomorphism
Let's label the vertices of a graph from , which we can do in ways. Two graphs are called isomorphic if they are both labels of the same graph. For example, consider these two graphs:
1...N
N!
Out[]=
These two graphs are isomorphic, since we can relabel the vertices of the first graph with the mapping .If we were to generate two random graphs, it is more likely that they will not be . Sometimes we want to figure out how similar two graphs are. However, there isn't a well defined way to do this, unlike Euclidean and Manhattan distance for points in space, Levenshtein distance for strings, and simple subtraction for numerical data. The purpose of this project is to explore graph metrics.
{11,24,32,45,53}
[citationneeded]
isomorphic
Chartrand-Kubicki-Schultz Distance
Chartrand-Kubicki-Schultz Distance
The Chartrand-Kubicki-Schultz (CKS) distance measures how close two connected graphs with vertices are. Let the vertices of two graphs be enumerated from in some way. Then, the distance between these two graphs is (i,j)-(i,j) where (i,j) is the distance between vertices and in graph .In less formal terms, take two graphs and number both of them, so that there's a way to compare them. Then, we can ask, "how far away are vertices 2 and 4 in the first graph, and how far are they in the second? How much do these values differ?" Total this difference for every pair of vertices, and we get the distance between the two graphs.Just like Euclidean distance is the shortest distance between two points, we want to know the shortest distance between the two graphs. Renumber the vertices of one graph and repeat. The CKS distance is the minimum distance over all these enumerations.For my implementation specifically, both graphs were unweighted and the distance function was the shortest path between two vertices, although this isn't required for the metric.
N
1...N
∑
i,j
d
G
1
d
G
2
d
G
i
j
G
d
G
Code
Code
To go through all enumerations, I wrote a small function that, given a permutation, returns the next-biggest permutation. There's a very convenient Wikipedia page that provides the algorithm to do this.
N!
In[]:=
NextPermutation[p_]:=Module[{n=Length[p],i=-1,j=1},For[ti=1,ti<n,ti++,If[p[[ti]]<p[[ti+1]],i=ti]];For[tj=i+1,tj≤n,tj++,If[p[[tj]]>p[[i]],j=tj]];out=p;t=out[[i]];out=ReplacePart[out,iout[[j]]];out=ReplacePart[out,jt];For[j=n;i++,i<j,i++;j--,t=out[[i]];out=ReplacePart[out,iout[[j]]];out=ReplacePart[out,jt];];out]NextPermutation[{1,2,3,4}]
Out[]=
{1,2,4,3}
GraphDistanceMatrix is a very, very convenient built-in function that calculates the shortest path between every pair for a given graph. Afterwards, I go through all the possible enumerations and find the distance between the two graphs.
CKS[g1_,g2_]:=Module[{n=VertexCount[g1],adj=GraphDistanceMatrix/@{g1,g2},ans=Infinity},p=Range[n];Do[tans=0;For[i=1,i≤n,i++,For[j=1,j<i,j++,tans+=Abs[adj[[1]][[i,j]]-adj[[2]][[p[[i]],p[[j]]]]]]];ans=Min[ans,tans];p=NextPermutation[p];,n!];ans]
In[]:=
g1=Graph[{12,13,14},VertexLabelsAutomatic];g2=Graph[{12,23,34,41,24},VertexLabelsAutomatic];
In[]:=
Print[GraphicsGrid[{{g1,g2}}]];CKS[g1,g2]
Out[]=
2
If we relabel the vertices of with the mapping , then the distances between and are in but only in . Every other distance is the same for both graphs.
G
1
{14,23,32,41}
12
23
2
G
1
1
G
2
Rectangle Distance
Rectangle Distance
The rectangle distance measures how close two complete weighted graphs of size are. Let be the vertex weights of graph such that all >0, and be the edge weights of graph .Let , and be the matrix . The rectangle distance between two graphs and is -+-. The maximum is taken over all possible subsets for and .This metric is a lot less intuitive and harder to visualize than the CKS distance since it deals with edge and vertex weights, as opposed to the structures of the graphs.
N
α
G
α
i
β
G
v=
∑
i
α
i
A(G)
NN
α
i
α
j
β
i,j
2
v
G
G'
max
I,J⊂{1...N}
∑
i∈I,j∈J
a
i,j
a'
i,j
∑
i
α
i
v
α'
i
v'
N
2
I
J
Code
Code
A[a_,b_,v_]:=Module[{n=Length[a]},out=Normal[SparseArray[{},{n,n}]];For[i=1,i≤n,i++,For[j=1,j≤n,j++,out[[i,j]]=a[[i]]*a[[j]]*b[[i,j]]/v]];out]RectDist[g1_,g2_]:=Module[{n=VertexCount[g1],b1=Normal@WeightedAdjacencyMatrix[g1],b2=Normal@WeightedAdjacencyMatrix[g2],a1=AnnotationValue[g1,VertexWeight],a2=AnnotationValue[g2,VertexWeight],},t1=Total[a1];t2=Total[a2];c1=A[a1,b1,t1^2];c2=A[a2,b2,t2^2];v=Sum[Abs[a1[[i]]/t1-a2[[i]]/t2],{i,n}];v2=0;lim=2^n;For[i=0,i<lim,i++,For[j=0,j<lim,j++,tv=0;For[i2=1,i2≤n,i2++,If[BitAnd[i,2^(i2-1)]>0,For[j2=1,j2≤n,j2++,If[BitAnd[j,2^(j2-1)]>0,tv+=c1[[i2,j2]]-c2[[i2,j2]]]]]];v2=Max[v2,Abs[tv]]]];v+v2]
Conclusion
Conclusion
Both of these metrics work only for specific types of graphs, and it'd be really great to generalize one or both algorithms to any two graphs. Graph distances also have real-world applications in scenarios like handwriting or fingerprint recognition -- for a future project, it would be interesting to incorporate one of these metrics into a handwriting/fingerprint system.
Keywords
Keywords
◼
graph
◼
distance
◼
heuristic
◼
math