# Metrics for Multiset-Theoretic Subgraphs

Authors: Ray-Ming Chen
Journal: Journal of Function Spaces
 (2019)

---

## Abstract

We show how to define a plethora of metrics for graphs—either full graphs or subgraphs. The method mainly utilizes the minimal matching between any two multisets of positive real numbers by comparing the multiple edges with respect to their corresponding vertices. In the end of this article, we also demonstrate how to implement these defined metrics with the help of adjacency matrices. These metrics are easy to be manipulated in real applications and could be amended according to different situations. By our metrics, one should be able to compare the distances between graphs, trees, and networks, in particular those with fuzzy properties.


---

## Body

## 1. Introduction

In the real world, we face a lot of uncertain mathematical objects. Among them, some are easier to be formalized via graphs or tree structures or networks. Henceforth, the distances between such structures are vital as they provide deeper information between two different structures. In the article [1], we have shown how to define metrics for graphs with single-edged vertices. Single-edge graphs are graphs with at most one edge between any two vertices. Such graphical structures normally are deterministic. The basic idea is to, based on minimal matching concepts, define matched parts and mismatched parts of incoming or outgoing edges. However, due to the complexity of real applications, in particular some fuzzy or indecisive mathematical objects, the metrics we had defined in that paper are insufficient to cover the needs. Therefore, we put forward some novel metrics which could accommodate such complexity in this article. We would consider graphs with multiple edges between any two vertices. This mechanism could then be applied in modelling some indecisive objects. Our research is also partially motivated by some articles regarding fuzzy mathematical objects [2–5]. Furthermore, if one is interested in other variants of metrics for graphs, he could consult either [6] or [7].


## 2. Multisets

Let us introduce some definitions and operations of multisets. LetR+ denote the set of all positive real numbers. Let N0 denote the set of all the natural numbers including 0. Let Γ denote the set of all the functions R+→N0. Let Df be the domain of a function f. Let Df∗={r∈R+:f(r)≠0} be the nonzero domain of f. Define Γ<={f∈Γ:Df∗<∞}. In this article, we name each element in Γ< a multiset. Let f,g∈Γ< be arbitrary multisets. We use the notation f≤g (i.e., f is a multisubset of g) to denote that for all x∈R+, f(x)≤g(x).Definition 1 (empty multiset).
We call the zero function inΓ< the empty multiset.Definition 2 (equality=).
f = g iff f≤g and g≤f.Definition 3 (intersection∧).
The intersection of multisetf and g, denoted by the function f∧g:R+→N0, is defined by (f∧g)(α)≔min{f(α),g(α)} for all α∈R+.Definition 4 (union∨).
The union of multisetf and g, denoted by the function f∨g:R+→N0, is defined to be (f∨g)(α)≔max{f(α),g(α)} for all α∈R+.Definition 5 (difference⊖).
Exclusion of multisetg from f, denoted by the function f⊖g:R+→N0, is defined by (f⊖g)(α)≔f(α)-(f∧g)(α) for all α∈R+.
Note that each multisetf in Γ< could be uniquely represented by either a set of descending form as follows:(1)f-=α1fα1,α2fα2,…,αnfαn,or in short f-=α1f(α1)α2f(α2)⋯αnf(αn), or by a set of ascending form as follows:(2)f+=αnfαnαn-1fαn-1,…,α2fα2α1fα1,or in short f+=αnf(αn)αn-1f(αn-1)⋯α1f(α1), where α1>α2>α3…>αn>0 and α1,α2,…,αn∈Df∗ and f(αv)>0 for all 1≤v≤n. Define the cardinality of a multiset f by f=∑t=1nf(αt).Definition 6 (descending order).
Define thep-th element in f by function OD as follows:(3)ODp,f≔α1if1≤p≤fα1;αjif∑l=1j-1fαl<p≤∑l=1jfαlandDf∗≥j≥2;0otherwise.Definition 7 (ascending order).
Define thep-th element in f by function OA as follows:(4)OAp,f≔αnif1≤p≤fαn;αn-jif∑l=0j-1fαn-l<p≤∑l=0jfαn-landDf∗≥j≥1;0otherwise.


## 3. Metrics

LetV be a set of vertices and E be a set of directed edges. Let MP<(R+) denote the finite multipower set of R+. In this section, we show how to define metrics for labelled graphs and unlabelled graphs. The distance is mainly defined based on weights of the corresponding edges between the graphs.Definition 8.
We callG=(V,E,W:E→MP<(R+)) a multiset-theoretic graph if and only if (1)
For eachv∈V[(v,v)∈E],(2)
For alla,b∈V, every element in W(a,b) is non-negative and W(a,b)={0}iffa=b,
whereW is a multiset-valued weight function. Let SG denote the set of all the multiset-theoretic graphs. The main purpose of this article is to define some metrics for SG which is divided into two categories: labelled vertices and unlabelled vertices.Definition 9.
LetW(a,b) denote the sum of all the elements in the multiset W(a,b).


### 3.1. Metrics for Labelled Graphs and Subgraphs

In this section, we show how to define the distance between any two graphs (whose vertices are all named) that could be graphs with either compatible or incompatible vertices. In this subsection, we assume all the vertices are labelled. To begin with, we show how to define metrics forMP<(R+). These metrics will serve as the foundations for further construction of metrics. By the representations of multisets in descending and ascending forms as shown in (1) and (2), we have the following definitions. Based on the minimal matchings between any two multisets of positive real numbers [8], we derive the following metrics.Definition 10 (descending metric).
Define(5)ddf,g≔∑k=1max⁡f,gODk,f-ODk,g.Definition 11 (ascending metric).
Define(6)daf,g≔∑k=1max⁡f,gOAk,f-OAk,g.Definition 12 (halved metric).
Define(7)dhf,g≔α·ddf,g+β·daf,g,where α,β≥0 and α+β=1.In this article, we assumeα=β=1/2. Indeed α and β could be decided by some mechanisms. We omit this part.Example 13.
Supposef-=83643523 and g-=9443332416. Then f=15 and g=20. Hence dd(f,g)=3·9-8+1·9-6+3·4-6+3·3-3+2·2-3+2·2-2+1·1-2+5·1-0=20. Suppose f+=23356483 and g+=1624334394. Then da(f,g)=78 and dh(f,g))=1/2(20+78)=49. In the following, instead of explicitly showing the representative forms of a multiset, the distances of the corresponding form are understood from their contexts; for example, dd({8,3,2,8,9},{2,2,3,1,5,2}) is deemed as dd(91823121,51312311), while da({8,3,2,8,9},{2,2,3,1,5,2}) is deemed as da(21318291,11233151).Lemma 14.
d d , d a and dh are all metrics on Γ<.Proof.
They follow from the absolute triangle property. Letf,g,h∈Γ< be arbitrary. One could show the triangle property via the relation of cardinalities of f,g, and h. For a full proof, one could also consult the results in [8].Now we need to develop much more complicated metrics viadd,da, and dh metrics. For each vertex, there are two approaches to define its adjacent vertices: inbound or outbound. Hence we have the following definitions. Define outbound set(8)Outa,E≔b∈V:a,b∈Eand inbound set(9)Inb,E≔a∈V:a,b∈E.Definition 15.
DefineOut(a,E)  =  ∑b∈Out(a,E)W(a,b)and  In(a,E)  =  ∑c∈In(a,E)W(c,a).Example 16.
AssumeE = {(a,a),(c,a),(a,d),(a,k),(b,a),(a,b),(u,v)}, W(a,a)={0}, W(c,a)={1,3,6}, Wa,d=2,4,2,4,2, W(a,k)={3,5,3,1}, W(b,a)={1,2,3,1}, W(a,b)={1,6}, W(u,v)={2,6,8,8}. Then Out(a,E)={a,d,k,b} and In(a,E)={c,b}; thus Out(a,E)=W(a,a) + W(a,d) + W(a,k) + W(a,b)=0+14+12+7 = 33. Moreover, In(a,E)=W(c,a) + W(b,a)=10+7 = 17.
LetG1=(V1,E1,W1),G2=(V2,E2,W2)∈SG be arbitrary. We have the following abbreviations: (i)
Out12(a)=Out(a,E1)-Out(a,E2);(ii)
Out21(a)=Out(a,E2)-Out(a,E1);(iii)
In12(a)=In(a,E1)-In(a,E2);(iv)
In21(a)=In(a,E2)-In(a,E1).
In this article, we put forward two equivalent categories of distance functions for subgraphs as follows.Definition 17 (outbound measure: descending).
(10) d o u t d G 1 , G 2 ≔ ∑ v ∈ V 1 - V 2 O u t v , E 1 + ∑ v ∈ V 2 - V 1 O u t v , E 2 + ∑ a ∈ V 1 ∩ V 2 ∑ c ∈ O u t 12 a W a , c + ∑ c ∈ O u t 21 a W c , a + d d O u t a , E 1 , O u t a , E 2 .Definition 18 (inbound measure: descending).
(11) d i n d G 1 , G 2 ≔ ∑ v ∈ V 1 - V 2 I n v , E 1 + ∑ v ∈ V 2 - V 1 I n v , E 2 + ∑ a ∈ V 1 ∩ V 2 ∑ c ∈ I n 12 a W a , c + ∑ c ∈ I n 21 a W c , a + d d I n a , E 1 , I n a , E 2 .Definition 19 (outbound measure: ascending).
(12) d o u t a G 1 , G 2 ≔ ∑ v ∈ V 1 - V 2 O u t v , E 1 + ∑ v ∈ V 2 - V 1 O u t v , E 2 + ∑ a ∈ V 1 ∩ V 2 ∑ c ∈ O u t 12 a W a , c + ∑ c ∈ O u t 21 a W c , a + d a O u t a , E 1 , O u t a , E 2 .Definition 20 (inbound measure: ascending).
(13) d i n a G 1 , G 2 ≔ ∑ v ∈ V 1 - V 2 I n v , E 1 + ∑ v ∈ V 2 - V 1 I n v , E 2 + ∑ a ∈ V 1 ∩ V 2 ∑ c ∈ I n 12 a W a , c + ∑ c ∈ I n 21 a W c , a + d a I n a , E 1 , I n a , E 2 .Definition 21 (outbound measure: halved).
(14) d o u t h G 1 , G 2 ≔ ∑ v ∈ V 1 - V 2 O u t v , E 1 + ∑ v ∈ V 2 - V 1 O u t v , E 2 + ∑ a ∈ V 1 ∩ V 2 ∑ c ∈ O u t 12 a W a , c + ∑ c ∈ O u t 21 a W c , a + d h O u t a , E 1 , O u t a , E 2 .Definition 22 (inbound measure: halved).
(15) d i n h G 1 , G 2 ≔ ∑ v ∈ V 1 - V 2 I n v , E 1 + ∑ v ∈ V 2 - V 1 I n v , E 2 + ∑ a ∈ V 1 ∩ V 2 ∑ c ∈ I n 12 a W a , c + ∑ c ∈ I n 21 a W c , a + d h I n a , E 1 , I n a , E 2 .Theorem 23.
( 1 )  doutd,dind,douta,dina,douth,dinh are all metrics;
( 2 )  doutd=dind,douta=dina,douth=dinh.Proof.
They all follow from the definitions, in particular the property of set difference and the facts thatdd,da, and dh are all metrics. For a full proof, one could also consult the results in [1, 8].Sincedoutd=dind,douta=dina,douth=dinh, we use dd, da, and dh to represent them, respectively, in the following.


### 3.2. Metrics for Unlabelled Graphs and Subgraphs

In this section, we show how to define the distance between any two graphs (whose vertices are all unnamed) that could be either compatible or incompatible graphs. Since all the vertices are unnamed, the distance could not be defined as the one in the labelled cases. Hence all the possibilities of the interactions betweenG1 and G2 (whose vertices are all unnamed) should be taken into consideration. However, we could fix one graph, say G1, and permute G2. Then one computes all the possible distances and chooses the optimal permutation of G2, in the sense of minimal distance. Let ρG(k) denote the k-th graph whose vertices are identical to G with k-permutation of the names for the vertices. ρ indeed is treated as a naming system. There are V2! ways of assigning the names to the unnamed set V2. Based on metrics dd,da,dh, we define the unlabelled distances as follows.Definition 24.
d d ∗ ( G 1 , G 2 ) ≔ m i n { d d ( G 1 , ρ G 2 ( k ) ) : 1 ≤ k ≤ V 2 ! }.Definition 25.
d a ∗ ( G 1 , G 2 ) ≔ m i n { d a ( G 1 , ρ G 2 ( k ) ) : 1 ≤ k ≤ V 2 ! }.Definition 26.
d h ∗ ( G 1 , G 2 ) ≔ m i n { d h ( G 1 , ρ G 2 ( k ) ) : 1 ≤ k ≤ V 2 ! }.Theorem 27.
d d ∗ , d a ∗, and dh∗ are all metrics.Proof.
They follow from the definitions. For a full proof, one could also consult the results in [1, 8].


## 3.1. Metrics for Labelled Graphs and Subgraphs

In this section, we show how to define the distance between any two graphs (whose vertices are all named) that could be graphs with either compatible or incompatible vertices. In this subsection, we assume all the vertices are labelled. To begin with, we show how to define metrics forMP<(R+). These metrics will serve as the foundations for further construction of metrics. By the representations of multisets in descending and ascending forms as shown in (1) and (2), we have the following definitions. Based on the minimal matchings between any two multisets of positive real numbers [8], we derive the following metrics.Definition 10 (descending metric).
Define(5)ddf,g≔∑k=1max⁡f,gODk,f-ODk,g.Definition 11 (ascending metric).
Define(6)daf,g≔∑k=1max⁡f,gOAk,f-OAk,g.Definition 12 (halved metric).
Define(7)dhf,g≔α·ddf,g+β·daf,g,where α,β≥0 and α+β=1.In this article, we assumeα=β=1/2. Indeed α and β could be decided by some mechanisms. We omit this part.Example 13.
Supposef-=83643523 and g-=9443332416. Then f=15 and g=20. Hence dd(f,g)=3·9-8+1·9-6+3·4-6+3·3-3+2·2-3+2·2-2+1·1-2+5·1-0=20. Suppose f+=23356483 and g+=1624334394. Then da(f,g)=78 and dh(f,g))=1/2(20+78)=49. In the following, instead of explicitly showing the representative forms of a multiset, the distances of the corresponding form are understood from their contexts; for example, dd({8,3,2,8,9},{2,2,3,1,5,2}) is deemed as dd(91823121,51312311), while da({8,3,2,8,9},{2,2,3,1,5,2}) is deemed as da(21318291,11233151).Lemma 14.
d d , d a and dh are all metrics on Γ<.Proof.
They follow from the absolute triangle property. Letf,g,h∈Γ< be arbitrary. One could show the triangle property via the relation of cardinalities of f,g, and h. For a full proof, one could also consult the results in [8].Now we need to develop much more complicated metrics viadd,da, and dh metrics. For each vertex, there are two approaches to define its adjacent vertices: inbound or outbound. Hence we have the following definitions. Define outbound set(8)Outa,E≔b∈V:a,b∈Eand inbound set(9)Inb,E≔a∈V:a,b∈E.Definition 15.
DefineOut(a,E)  =  ∑b∈Out(a,E)W(a,b)and  In(a,E)  =  ∑c∈In(a,E)W(c,a).Example 16.
AssumeE = {(a,a),(c,a),(a,d),(a,k),(b,a),(a,b),(u,v)}, W(a,a)={0}, W(c,a)={1,3,6}, Wa,d=2,4,2,4,2, W(a,k)={3,5,3,1}, W(b,a)={1,2,3,1}, W(a,b)={1,6}, W(u,v)={2,6,8,8}. Then Out(a,E)={a,d,k,b} and In(a,E)={c,b}; thus Out(a,E)=W(a,a) + W(a,d) + W(a,k) + W(a,b)=0+14+12+7 = 33. Moreover, In(a,E)=W(c,a) + W(b,a)=10+7 = 17.
LetG1=(V1,E1,W1),G2=(V2,E2,W2)∈SG be arbitrary. We have the following abbreviations: (i)
Out12(a)=Out(a,E1)-Out(a,E2);(ii)
Out21(a)=Out(a,E2)-Out(a,E1);(iii)
In12(a)=In(a,E1)-In(a,E2);(iv)
In21(a)=In(a,E2)-In(a,E1).
In this article, we put forward two equivalent categories of distance functions for subgraphs as follows.Definition 17 (outbound measure: descending).
(10) d o u t d G 1 , G 2 ≔ ∑ v ∈ V 1 - V 2 O u t v , E 1 + ∑ v ∈ V 2 - V 1 O u t v , E 2 + ∑ a ∈ V 1 ∩ V 2 ∑ c ∈ O u t 12 a W a , c + ∑ c ∈ O u t 21 a W c , a + d d O u t a , E 1 , O u t a , E 2 .Definition 18 (inbound measure: descending).
(11) d i n d G 1 , G 2 ≔ ∑ v ∈ V 1 - V 2 I n v , E 1 + ∑ v ∈ V 2 - V 1 I n v , E 2 + ∑ a ∈ V 1 ∩ V 2 ∑ c ∈ I n 12 a W a , c + ∑ c ∈ I n 21 a W c , a + d d I n a , E 1 , I n a , E 2 .Definition 19 (outbound measure: ascending).
(12) d o u t a G 1 , G 2 ≔ ∑ v ∈ V 1 - V 2 O u t v , E 1 + ∑ v ∈ V 2 - V 1 O u t v , E 2 + ∑ a ∈ V 1 ∩ V 2 ∑ c ∈ O u t 12 a W a , c + ∑ c ∈ O u t 21 a W c , a + d a O u t a , E 1 , O u t a , E 2 .Definition 20 (inbound measure: ascending).
(13) d i n a G 1 , G 2 ≔ ∑ v ∈ V 1 - V 2 I n v , E 1 + ∑ v ∈ V 2 - V 1 I n v , E 2 + ∑ a ∈ V 1 ∩ V 2 ∑ c ∈ I n 12 a W a , c + ∑ c ∈ I n 21 a W c , a + d a I n a , E 1 , I n a , E 2 .Definition 21 (outbound measure: halved).
(14) d o u t h G 1 , G 2 ≔ ∑ v ∈ V 1 - V 2 O u t v , E 1 + ∑ v ∈ V 2 - V 1 O u t v , E 2 + ∑ a ∈ V 1 ∩ V 2 ∑ c ∈ O u t 12 a W a , c + ∑ c ∈ O u t 21 a W c , a + d h O u t a , E 1 , O u t a , E 2 .Definition 22 (inbound measure: halved).
(15) d i n h G 1 , G 2 ≔ ∑ v ∈ V 1 - V 2 I n v , E 1 + ∑ v ∈ V 2 - V 1 I n v , E 2 + ∑ a ∈ V 1 ∩ V 2 ∑ c ∈ I n 12 a W a , c + ∑ c ∈ I n 21 a W c , a + d h I n a , E 1 , I n a , E 2 .Theorem 23.
( 1 )  doutd,dind,douta,dina,douth,dinh are all metrics;
( 2 )  doutd=dind,douta=dina,douth=dinh.Proof.
They all follow from the definitions, in particular the property of set difference and the facts thatdd,da, and dh are all metrics. For a full proof, one could also consult the results in [1, 8].Sincedoutd=dind,douta=dina,douth=dinh, we use dd, da, and dh to represent them, respectively, in the following.


## 3.2. Metrics for Unlabelled Graphs and Subgraphs

In this section, we show how to define the distance between any two graphs (whose vertices are all unnamed) that could be either compatible or incompatible graphs. Since all the vertices are unnamed, the distance could not be defined as the one in the labelled cases. Hence all the possibilities of the interactions betweenG1 and G2 (whose vertices are all unnamed) should be taken into consideration. However, we could fix one graph, say G1, and permute G2. Then one computes all the possible distances and chooses the optimal permutation of G2, in the sense of minimal distance. Let ρG(k) denote the k-th graph whose vertices are identical to G with k-permutation of the names for the vertices. ρ indeed is treated as a naming system. There are V2! ways of assigning the names to the unnamed set V2. Based on metrics dd,da,dh, we define the unlabelled distances as follows.Definition 24.
d d ∗ ( G 1 , G 2 ) ≔ m i n { d d ( G 1 , ρ G 2 ( k ) ) : 1 ≤ k ≤ V 2 ! }.Definition 25.
d a ∗ ( G 1 , G 2 ) ≔ m i n { d a ( G 1 , ρ G 2 ( k ) ) : 1 ≤ k ≤ V 2 ! }.Definition 26.
d h ∗ ( G 1 , G 2 ) ≔ m i n { d h ( G 1 , ρ G 2 ( k ) ) : 1 ≤ k ≤ V 2 ! }.Theorem 27.
d d ∗ , d a ∗, and dh∗ are all metrics.Proof.
They follow from the definitions. For a full proof, one could also consult the results in [1, 8].


## 4. Computations and Implementations

In this section, we show how to implement all the above-mentioned metrics via adjacency matrices. LetV={v1,v2,v3,v4,v5}. Suppose G(V) is the set of all the graphs whose vertices are comprised of part or all of V. Let G1,G2,G3,G4∈G(V) defined as follows.G 1 = ( V 1 , E 1 , W 1 ), G2=(V2,E2,W2),G3=(V3,E3,W3), and G4=(V4,E4,W4), where V1=V2=V, V3={v1,v3,v4}, and V4={v2,v3,v4}; Ek=(eijk); and W1,W2,W3,W4 are defined as follows:(16)W1=02,2,57,1,9,14,5,4,5,91,2,12,4,101,2,15,56,2,8,92,1,25,2,7,607,4,92,5,56,76,8,18,9,502,4,25,56,6,11,9,11,5,50W2=01,2,3,67,7,9,24,5,56,2,54,4,506,7,21,6,56,7,71,16,6,606,4,8,81,2,26,1,12,21,5,508,4,4,81,2,588,5,2,25,50W3=04,1,61,9,9,44,506,6,9,11,4,4,5}8,1,60,W4=08,6,66,9,14,8,506,6,6,74,8,27,70.


### 4.1. Computations for Labelled Full Graphs

We callG1 and G2 full graphs. Based on the definitions regarding their components of distances, we have the following computations (which correspond to the original definitions, in matrix form): [W1,W2]ind=[W1,W2]outd=037139601125340877111101649810 and dd(G1,G2)=[W1,W2]ind=[W1,W2]outd=145.[ W 1 , W 2 ] i n a = [ W 1 , W 2 ] o u t a = 0 9 7 15 9 6 0 11 10 15 3 12 0 10 7 17 13 11 0 16 12 19 14 9 0 and da(G1,G2)=[W1,W2]ina=[W1,W2]outa=225. Furthermore, dh(G1,G2)=1/2·[145+225]=185.


### 4.2. Computations for Labelled Subgraphs

We callG3 and G4 subgraphs. To begin with, we show how to compute the distance between a full graph and a subgraph. Their interactive components of distances are illustrated in the following matrix form:[ W 1 , W 3 ] i n d = [ W 1 , W 3 ] o u t d = 0 9 7 12 4 7 0 4 10 25 6 20 0 4 12 9 15 7 0 8 10 13 11 11 0 and dd(G1,G3)=W1,W3ind=W1,W3outd=204.[ W 1 , W 3 ] i n a = [ W 1 , W 3 ] o u t a = 0 9 13 20 4 7 0 4 10 25 8 20 0 16 12 17 15 7 0 8 10 13 11 11 0 and da(G1,G3)=W1,W3ina=W1,W3outa=240. Furthermore, dh(G1,G3)=1/2·[204+240]=222.Now we show how to implement the computation of the distance between any two subgraphs via a matrix form and its norm as follows:[ W 3 , W 4 ] i n d = [ W 3 , W 4 ] o u t d = 0 31 39 26 0 7 28 3 0 and dd(G3,G4)=[W3,W4]ind=W3,W4outd=134;[W3,W4]ina=[W3,W4]outa=03139260728150 and da(G3,G4)=[W3,W4]ina=[W3,W4]outa=146. Furthermore, dh(G3,G4)=1/2·[134+146]=140.


### 4.3. Computations for Unlabelled Full Graphs

Suppose the vertices inV1,V2,V3,V4 are all unnamed. To compute the distance between unnamed G1 and G2, according to the definition, we need to pick the smallest distances between G1 and ρG2(k) for 1≤k≤V2!. To implement this, we fix the adjacency matrix of G1 and permutes the adjacency matrix of G2 and compute all the respective distances and then choose the least one and its resulting permutation. Through computation, we have the following result:By settingρG2(k) as follows: ρG2(v1)=v1,ρG2(v2)=v4,ρG2(v3)=v2,ρG2(v4)=v3,ρG2(v5)=v5 for some unique k, one has dd∗(G1,G2)=dd(G1,ρG2(k))=119.Similarly, by settingρG2(k) as follows: ρG2(v1)=v5,ρG2(v2)=v3,ρG2(v3)=v1,ρG2(v4)=v2,ρG2(v5)=v4 for some unique k, one has da∗(G1,G2)=da(G1,ρG2(k))=163. Furthermore, dh∗=1/2×[119+163]=141.


### 4.4. Computations for Unlabelled Subgraphs

As for thedd(G1,G3), after our computations, the optimal corresponding subgraph in G1 is the truncated one with vertex lying in {v1,v3,v4}; i.e., the optimal subgraph with respect to dd∗ is {0}{7,1,9,1}{4,5,4,5,9}{2,1,2}{0}{7,4,9}{6,7}{8,9,5}{0}. Then dd∗(G1,G3)=198. Similarly, the optimal subgraph with respect to da∗ is {0}{5,5}{6,2,8,9}{6,8,1}{0}{2,4,2}{6,6,1}{1,5,5}{0}. Then dd∗(G1,G3)=216. Furthermore, dh∗=1/2×[198+216]=207. By setting ρG4(k) as follows: ρG2(v1)=v3,ρG2(v2)=v1,ρG2(v3)=v2 for some unique k, one has dd∗(G3,G4)=dd(G3,ρG4(k))=36. By setting ρG4(k) as follows: ρG2(v1)=v1,ρG2(v2)=v2,ρG2(v3)=v3 for some unique k, one has da∗(G3,G4)=da(G3,ρG4(k))=60.To sum up all the results regarding different metrics and graphs, we have Table1.Table 1
Implementations of all the metrics.
Distance between distances:dd, dd∗ distances:da,da∗ distances:dh,dh∗ G 1 , G 2: labelled 145 225 185 G 1 , G 3: labelled 204 240 222 G 3 , G 4: labelled 134 146 140 G 1 , G 2: unlabelled 119 163 141 G 1 , G 3: unlabelled 198 216 207 G 3 , G 4: unlabelled 36 60 48There are several observations worth mentioning:(1)
dd∗≥dh∗≥dd∗;(2)
the distance between a full graph and a subgraph is higher than either the distances for full graphs or the subgraphs;(3)
the distance between unlabelled graphs is less than or equal to the one between labelled ones.All these results agree with our theoretical definitions and derivations.


## 4.1. Computations for Labelled Full Graphs

We callG1 and G2 full graphs. Based on the definitions regarding their components of distances, we have the following computations (which correspond to the original definitions, in matrix form): [W1,W2]ind=[W1,W2]outd=037139601125340877111101649810 and dd(G1,G2)=[W1,W2]ind=[W1,W2]outd=145.[ W 1 , W 2 ] i n a = [ W 1 , W 2 ] o u t a = 0 9 7 15 9 6 0 11 10 15 3 12 0 10 7 17 13 11 0 16 12 19 14 9 0 and da(G1,G2)=[W1,W2]ina=[W1,W2]outa=225. Furthermore, dh(G1,G2)=1/2·[145+225]=185.


## 4.2. Computations for Labelled Subgraphs

We callG3 and G4 subgraphs. To begin with, we show how to compute the distance between a full graph and a subgraph. Their interactive components of distances are illustrated in the following matrix form:[ W 1 , W 3 ] i n d = [ W 1 , W 3 ] o u t d = 0 9 7 12 4 7 0 4 10 25 6 20 0 4 12 9 15 7 0 8 10 13 11 11 0 and dd(G1,G3)=W1,W3ind=W1,W3outd=204.[ W 1 , W 3 ] i n a = [ W 1 , W 3 ] o u t a = 0 9 13 20 4 7 0 4 10 25 8 20 0 16 12 17 15 7 0 8 10 13 11 11 0 and da(G1,G3)=W1,W3ina=W1,W3outa=240. Furthermore, dh(G1,G3)=1/2·[204+240]=222.Now we show how to implement the computation of the distance between any two subgraphs via a matrix form and its norm as follows:[ W 3 , W 4 ] i n d = [ W 3 , W 4 ] o u t d = 0 31 39 26 0 7 28 3 0 and dd(G3,G4)=[W3,W4]ind=W3,W4outd=134;[W3,W4]ina=[W3,W4]outa=03139260728150 and da(G3,G4)=[W3,W4]ina=[W3,W4]outa=146. Furthermore, dh(G3,G4)=1/2·[134+146]=140.


## 4.3. Computations for Unlabelled Full Graphs

Suppose the vertices inV1,V2,V3,V4 are all unnamed. To compute the distance between unnamed G1 and G2, according to the definition, we need to pick the smallest distances between G1 and ρG2(k) for 1≤k≤V2!. To implement this, we fix the adjacency matrix of G1 and permutes the adjacency matrix of G2 and compute all the respective distances and then choose the least one and its resulting permutation. Through computation, we have the following result:By settingρG2(k) as follows: ρG2(v1)=v1,ρG2(v2)=v4,ρG2(v3)=v2,ρG2(v4)=v3,ρG2(v5)=v5 for some unique k, one has dd∗(G1,G2)=dd(G1,ρG2(k))=119.Similarly, by settingρG2(k) as follows: ρG2(v1)=v5,ρG2(v2)=v3,ρG2(v3)=v1,ρG2(v4)=v2,ρG2(v5)=v4 for some unique k, one has da∗(G1,G2)=da(G1,ρG2(k))=163. Furthermore, dh∗=1/2×[119+163]=141.


## 4.4. Computations for Unlabelled Subgraphs

As for thedd(G1,G3), after our computations, the optimal corresponding subgraph in G1 is the truncated one with vertex lying in {v1,v3,v4}; i.e., the optimal subgraph with respect to dd∗ is {0}{7,1,9,1}{4,5,4,5,9}{2,1,2}{0}{7,4,9}{6,7}{8,9,5}{0}. Then dd∗(G1,G3)=198. Similarly, the optimal subgraph with respect to da∗ is {0}{5,5}{6,2,8,9}{6,8,1}{0}{2,4,2}{6,6,1}{1,5,5}{0}. Then dd∗(G1,G3)=216. Furthermore, dh∗=1/2×[198+216]=207. By setting ρG4(k) as follows: ρG2(v1)=v3,ρG2(v2)=v1,ρG2(v3)=v2 for some unique k, one has dd∗(G3,G4)=dd(G3,ρG4(k))=36. By setting ρG4(k) as follows: ρG2(v1)=v1,ρG2(v2)=v2,ρG2(v3)=v3 for some unique k, one has da∗(G3,G4)=da(G3,ρG4(k))=60.To sum up all the results regarding different metrics and graphs, we have Table1.Table 1
Implementations of all the metrics.
Distance between distances:dd, dd∗ distances:da,da∗ distances:dh,dh∗ G 1 , G 2: labelled 145 225 185 G 1 , G 3: labelled 204 240 222 G 3 , G 4: labelled 134 146 140 G 1 , G 2: unlabelled 119 163 141 G 1 , G 3: unlabelled 198 216 207 G 3 , G 4: unlabelled 36 60 48There are several observations worth mentioning:(1)
dd∗≥dh∗≥dd∗;(2)
the distance between a full graph and a subgraph is higher than either the distances for full graphs or the subgraphs;(3)
the distance between unlabelled graphs is less than or equal to the one between labelled ones.All these results agree with our theoretical definitions and derivations.


## 5. Real World Application

In this section, we demonstrate how to make a decision via our derived metrics when facing some uncertain situation in the real. Suppose country B’s strategic deployment of air planes depends on country A’s attack force. The degree of attack force ranges from 0 to 100, in which 0 indicates that there is no loss in the combat while 100 indicates the opponent’s airbase is completely wiped out. Suppose A and B both have fives airbases in other countries C1, C2, C3, C4, and C5. Suppose A has 6 types of air planes A1, A2, A3, A4, A5, and A6. The number of each type of planes installed across different countries is listed in Table2. Their respective attack forces are 30, 45, 55, 76, 88, and 97. Suppose B’s observation of A’s planes and air flight of his planes from one base to other bases is recorded in Tables 3 and 4. The potential flights from one base to other bases for A are listed in Table 2. This table could be directly converted into an adjacency matrix (named PAF), in which “none” is replaced by 0 and contents in each Cij is rewritten in the forms of sets. Suppose B has 7 types of air planes: B1, B2, B3, B4, B5, B6, and B7. Their respective attack forces are 28, 41, 46, 52, 61, 70, 86. Suppose B owns e1=6,e2=4,e3=10,e4=7,e5=10,e6=22, and e7=11 planes for each corresponding type. Now the problem for B is how he should send his air planes to counterbalance his opponent. Based on the metrics in this article, we could make a decision toward such uncertain situation. Let aijk,bijk denote the numbers of air flight of A’s and B’s air planes k from airbase Ci to Cj. Define(17)B=B~:B~=B~i,ji,j=15,B~ij=bi,jkk=17,∑i,j=15bi,jk=ek,1≤k≤7The optimal decision for B to counterbalance A is(18)argmin⁡dvPAF,B~:B~∈B,where v∈{d,a,h}. Their individual solutions could be obtained via integer programming. Here we omit the final execution. If there is inconsistency between the choices of v, one could resort to subjective judgement or assigning weights between dd,da and dh to reach a final decision.Table 2
Country A’s installed air force.
C1 C2 C3 C4 C5 subtotal A1 2 0 1 1 3 7 A2 1 4 2 2 2 11 A3 2 3 3 2 0 10 A4 2 1 0 4 1 8 A5 1 1 0 2 0 4 A6 5 1 1 0 3 10  subtotal 13 10 7 11 9 50Table 3
Country A’s potential air flight.
C1 C2 C3 C4 C5 C1 0 A1,A3 A2, A4,A6 A3,A6 A1,A5,A6 C2 None 0 A2,A3,A5,A6 A2 A3,A5 C3 A2,A3 A1,A3,A6 0 A2 None C4 A1,A2,A3,A4 A2 A4 0 A3,A5 C5 A1,A6 None A2,A4,A6 A6 0Table 4
Country A’s potential attack force.
C1 C2 C3 C4 C5 C1 0 30,55 45, 76,76,97 55,97,97,97 30,88,97 C2 None 0 45,55,55,76,97 45,45,45 55,88 C3 45,55,55 30,55,97 0 45 None C4 30,45,55,76 45 76,76,76 0 55,88,88 C5 30,30,30,97 None 45,45,76,97 97 0


## 6. Conclusion

In this article, we have shown how to define distances between graphs over either a set of labelled or unlabelled vertices via a plethora of metrics for graphs. We also give computational approaches to implement the computation of these metrics via the operations on adjacency matrices. This implementation gives an efficient and fast computation of the distance between any two such graphs. We also demonstrate how to apply these metrics in uncertain decision-making. Indeed, these metrics could be further applied in measuring the distance between real networks or tree-like structures.



---

*Source: 7630242-2019-02-03.xml*