# Network Similarity Measure and Ediz Eccentric Connectivity Index

Authors: Guihai Yu; Xinzhuang Chen
Journal: Complexity
 (2020)

---

## Abstract

Network similarity measures have proven essential in the field of network analysis. Also, topological indices have been used to quantify the topology of networks and have been well studied. In this paper, we employ a new topological index which we call the Ediz eccentric connectivity index. We use this quantity to define network similarity measures as well. First, we determine the extremal value of the Ediz eccentric connectivity index on some network classes. Second, we compare the network similarity measure based on the Ediz eccentric connectivity index with other well-known topological indices such as Wiener index, graph energy, Randić index, the largest eigenvalue, the largest Laplacian eigenvalue, and connectivity eccentric index. Numerical results underpin the usefulness of the chosen measures. They show that our new measure outperforms all others, except the one based on Wiener index. This means that the measure based on Wiener index is still the best, but the new one has certain advantage to some extent.


---

## Body

## 1. Introduction

Similarity measures for networks have been studied extensively. Up to now, exploring methods to measure the similarity/distance between networks has been a current research item [1]. However, not every measure is generally applicable as these methods rely on different concepts, e.g., graph ismomorphism. Also, different measure methods may be used for different kind of networks.In this paper, we employ a distance measure [1, 2]:(1)dx,y=1−e−x−y/σ2,for x,y∈ℝ, which leads to a graph distance measure based on topological indices [1, 3]:(2)dIG,H≔dIG,IH=1−e−IG−IH/σ2,where GandH are two networks and IGandIH are topological indices applied to both G and H. In this paper, we set σ=1. Dehmer et al. [1, 3–6] explored the interrelations between the graph similarity measures based on some well-known topological indices such as Wiener index, Randić index, graph entropy, and eigenvalue-based quantities. Triggered by this, we continue to investigate the network similarity measure dI by employing a new topological graph measures, namely, the Ediz eccentric connectivity index [7]. Furthermore, we compare the similarity measures based on different topological indices.


## 2. Topological Indices

A topological index [8] is a network/graph invariant, which maps networks to the reals. Topological indices for graphs have been well studied. They have been used for examining quantitative structure-activity relationships (QSARs) [9]. Also, they have been applied in ecology [10], biology [11], and network physics [12, 13]. In the following, we list several topological indices which will be used.Wiener indexWG of a graph G=V,E is defined as WG=∑x,y∈VDx,y, where Dx,y is the distance between two vertices x and y of G, which is introduced by Wiener [14]. Some properties of Wiener index were discussed, see [15, 16] and the references cited therein.Randić indexRG of a graph G is defined as RG=∑x,y∈E1/dxdy, where dx is the degree of the vertex v∈V, which was proposed by Randić [17]. Some properties of Randić index were discussed, see [18, 19] and the references cited therein.Graph energyℰG of a graph G on n vertices is defined as ℰG=∑i=1nλi, where λi (1≤i≤n) is the eigenvalues of the adjacency matrix of G, which is introduced by Gutman [20]. Some properties of graph energy were discussed, see [21] and the references cited therein.Connective eccentricity indexξceG of a graph G [22] is defined as ξceG=∑v∈VGdv/εv, where dx and εv are the degree and the eccentricity of the vertex v∈V, respectively. Some properties of the connective eccentricity index were discussed, see [23] and the references cited therein.The Ediz eccentric connectivity indexξEecG of a graph [7] G is defined by ξEecG=∑v∈VGSv/εv, where Sv is the sum of the degrees of the vertices adjacent to the vertex v and εv is the eccentricity of the vertex v. Some mathematical properties of Ediz eccentric connectivity index are discussed in [7]. The physico-chemical properties of certain molecular structures were investigated by computing the Ediz eccentric connectivity index [24]. In [25], the Ediz eccentric connectivity index for Circumcoronene Series of Benzenoid by Ring-Cut method.


## 3. Main Results

### 3.1. Extremal Values of Ediz Eccentric Connectivity Index

LetG be an unweighted, undirected graph with vertex set VG. For vertices u,v∈VG, the distance du,v is defined as the length of the shortest path between u and v in G. The eccentricity εv of a vertex v is the maximum distance from v to any other vertex. Obviously, εv≥1, for any vertex v∈VG.Theorem 1.
LetG be a graph on n vertices with the decreasing degree sequence d1,d2,…,dn. Then,(3)ξEceG≤∑i=1ndi2,with equality if and only if G is a complete graph.Proof.
Sinceεv≥1 for any v∈VG, then(4)ξEceG≤∑v∈VGSv1=∑v∈VGSv=∑v∈VG∑u∼vdu=∑i=1ndi2,where u∼v means that u is adjacent to v. The above equalities hold if and only if εv=1 for any v∈VG, i.e., G is a complete graph.Remark 1.
Since the first Zagreb index [26] of a graph G is defined as M1G=∑u∈VGdu2, the result ξEceG≤M1G holds. The equality holds if and only if G is a complete graph.
Average eccentricity of a graphG on n vertices is defined as ζG=1/n∑v∈VGεv. A relation between Ediz eccentric connectivity index and average eccentricity is present as follows.Theorem 2.
LetG be a graph on n vertices. Then,(5)ξEceG≤nn−12ζG,with equality if and only if G is a complete graph.Proof.
Sinceεv≥1 for any vertex v∈VG, then 1/εv≤εv with equality if and only if εv=1. Moreover, dv≤n−1. Therefore,(6)ξEceG=∑v∈VGSvεv≤∑v∈VGεvSv≤∑v∈VGn−12εv=nn−12ζG.
The first equality holds if and only if1/εv=εv, i.e., G is a complete graph. The second equality holds if and only if dv=n−1 for any v∈VG, i.e., G is a complete graph.Theorem 3.
LetG be a graph on n vertices with independence number α. Then,(7)ξEceG≤n−αn−1n+α−1+n−αα,with equality if and only if G≅Kn−α∨Kα¯.Proof.
LetG be the set of graphs on n vertices with independence number α. Assume that G0∈G has the maximal Ediz eccentric connectivity index. Let VG0 be the vertex set of G0 and S=v1,v2,…,vα be the maximal independence set. Let G∗ be the subgraph, induced by VG0/S, of G0. Since adding an edge shall increase the Ediz eccentric connectivity index, G∗ is complete. Moreover, there must exit an edge joining any two vertices between S and VG0/S in G0. So, G0≅Kn−α∨Kα¯. By directed computation, we have ξEceKn−α∨Kα¯=n−αn−1n+α−1+n−αα.
LetγG be the covering number of a graph G. It is well known that αG+γG=n. From Theorem 3, the following holds.Corollary 1.
LetG be a connected graph on n vertices with covering number γ. Then,(8)ξEceG≤γn−12n−γ−1+γn−γ,with equality if and only if G≅Kγ∨Kn−γ¯.In [23, 27], authors investigated the eccentric distance sum and connective eccentricity index of graphs with vertex connectivity, respectively. By modifying their methods, we have the following.Theorem 4.
LetG be a connected graph on n vertices with the vertex connectivity κ. Then, ξEceG≤κκ−12n−κ−1+3/2κ−1n−κ2−2n−κ−1+1/2κn−1n−κ+1/2n−κ3−3n−κn−κ−1 with equality if and only if G≅Kκ∨K1∪Kn−κ−1.Proof.
LetG0 be a graph having the maximal Ediz eccentric connectivity index among all connected graphs on n vertices with vertex connectivity κ. Then, there exists a vertex cut C⊂VG0 with C=κ such that G0−C=G1∪G2∪⋯∪Gt, where G1,G2,…,Gt are t≥2 connected components of G0−C. Since adding an edge shall increase Ediz eccentric connectivity index, t=2 and G1,G2 and GC are complete graphs, any vertex of G1 and G2 is adjacent to any vertex in C. So, G0≅Kκ∨Kn1∪Kn2 and n1+n2=n−κ for ni=Gi (i=1,2). By directly computing, we have(9)ξEceKκ∨Kn1∪Kn2=32κ−1n−κ2−2n1n2+12n−κ3−3n−κn1n2.
Note thatn1n2=n1n−κ−n1≥n−k−1 with equality if and only if n1=1, n2=n−κ−1, or n2=1, n1=n−κ−1. Then, ξEceG≤κκ−12n−κ−1+3/2κ−1n−κ2−2n−κ−1+1/2κn−1n−κ+1/2n−κ3−3n−κn−κ−1, with equality if and only if G≅Kκ∨K1∪Kn−κ−1.
Tk,n, which is called Turán graph, is the complete k-partite graph on n vertices in which all parts are as equal in size as possible.Lemma 1.
(see [28]). Let G be a graph which contains no Kk (k≥2). Then, EG|≤|ETk−1,n with equality if and only if G≅Tk−1,n.
The following is immediate from Lemma1.Lemma 2.
A graphG is connected with EG>1/4VG2, and then G contains at least one triangle.Theorem 5.
LetG be a triangle-free connected graph on n vertices. Then, ξEceG≤n2n−2/4 if εu>1 for any vertex v∈VG, with equality if and only if G≅K2,2. Otherwise, ξEceG≤n2−1/2, with equality if and only if G≅K1,n−1.Proof.
LetG be a triangle-free graph with the maximal Ediz eccentric connectivity index. If there exists a vertex u∈VG such that εu=1, then du=n−1. Hence, G≅K1,n−1 since G is triangle-free. Assume that εv>1 for v∈VG. Then, dv≤n−2 and(10)ξEceG=∑v∈VGSvεv≤12∑v∈VGSv≤12∑v∈VGn−2dv=n−2|EG|≤n2n−24,by Lemma2.
The above equalities holds if and only ifεv=2, dv=n−2 for all v∈VG and EG=n2/4, i.e., G≅K2,2. By computing, ξEceK1,n−1=n2−1/2.Theorem 6.
LetG be a connected graph on n vertices with k pendent vertices. Then,(11)ξEceG≤n−122+n−kn−k−122+k,with equality if and only if G≅Knk, where Knk is a graph obtained from Kn−k by attaching k pendent edges to one vertex of Kn−k.Proof.
LetG0 be the graph on n vertices with k pendent vertices and the maximal Ediz eccentric connectivity index. Assume that v1,v2,…,vk be the set of pendent vertices in G0. The subgraph G0′ induced by VG0/v1,v2,…,vk is a complete graph. In what follows, we would prove that G0≅Knk.
Suppose that there exist at least two vertices ofG0′ such that their degrees are more than n−k−1. Set vi,vj∈VG0′ and dvi≥dvj>n−k−1. Let G1 be the new graph obtained from G0 by removing all pendent vertices attached to vj and attaching them to vi. Let V1 (V2) be the set of pendent vertices attached to vi (vj) in G0′. Let V3 be the set of pendent vertices not in V1 or V2.
Note thatεG0vi=εG1vi=2, εG0vj=εG1vj=2, and εG0v=εG1v=2 for v∈VG0′/vi and εG0v=εG1v=3 for v∈V1∪V2∪V3. The degree of vertex in VG0/vi,vj does not change, but the degree of vi increases by V2 and the one of vj decreases by V2. Let C be the sum of the degrees of vertices in VG0′/vi,vj. Note that C is a constant under G0 and G1. By the definition of Ediz eccentric connectivity index, we have(12)ξEceG0=∑v∈VG0′/vi,vjC+dG0vi+dG0vj2+∑v∈V1dG0vi3+∑v∈V2dG0vj3+∑v∈V3SG0v3+SG0vi2+SG0vj2,ξEceG1=∑v∈VG1′/vi,vjC+dG1vi+dG1vj2+∑v∈V1dG1vi3+∑v∈V2dG1vj3+∑v∈V3SG1v3+SG1vi2+SG1vj2=∑v∈VG0′/vi,vjC+dG0vi+dG0vj2+∑v∈V1dG0+V23+∑v∈V2dG0+V23+∑v∈V3SG0v3+SG0vi2+SG0vj2.
Then,(13)ξEceG0−ξEceG1=−∑v∈V1V23+∑v∈V2dG0vj−dG0vi−V23<0,and this is a contradiction. So, G0≅Knk.
By computing, it follows thatξEceKnk=n−12/2+n−kn−k−12/2+k.Lemma 3.
LetH1 and H2 be two disjoint connected graphs on at least 2 vertices with u∈VH1 and v∈VH2. G1 is the graph obtained from H1∪H2 by adding an edge uv. G2 is the graph obtained from H1∪H2 by identifying u and v (to be a new vertex, say, u) and adding a pendent edge, say uv without confusion. Then, ξEceG1<ξEceG2.Proof.
LetV1 be the set of neighbors of u in H1 and C1 be the sum of degrees of vertices in V1. Let V2 be the set of neighbors of v in H2 and C2 be the sum of degrees of vertices in V2. Note that εG1x≥εG2x for all x∈VH1∪VH2/u,v and SG1x=SG2s for x∈VH1∪VH2/V1∪V2∪u,v. So, we have(14)ξEceG1=∑x∈VH1/V1∪uSG1xεG1x+∑x∈VH2/V2∪vSG1xεG1x+∑x∈V1SG1xεG1x+∑x∈V2SG1xεG1x+SG1uεG1u+SG1vεG1v=∑x∈VH1/V1∪uSG1xεG1x+∑x∈VH2/V2∪vSG1xεG1x+∑x∈V1SG1xεG1x+∑x∈V2SG1xεG1x+C1+dG1vεG1u+C2+dG1uεG1v.Case 1.εH1u≥1+εH2vIn this case,εG1u=εH1u=εG2u and εG1v=1+εH1u=εG2v. It follows that(15)ξEceG2=∑x∈VH1/V1∪uSG2xεG2x+∑x∈VH2/V2∪vSG2xεG2x+∑x∈V1SG1x+dG1v−1εG2x+∑x∈V2SG1x+dG1u−1εG2x+C1+C2+1εG2u+dG1u+dG1v−1εG2v.Then,(16)ξEceG2−ξEceG1≥∑x∈VH1/V1∪uSG2x−SG1xεG1x+∑x∈VH2/V2∪vSG2x−SG1xεG1x+∑x∈V1dG1v−1εG1x+∑x∈V2dG1u−1εG1x+C1+C2+1εG1u−C1+dG1vεG1u+dG1u+dG1v−1εG1v−C2+dG1uεG1v>1+C2−dG1vεG1u+dG1v−1−C2εG1v>1+C2−dG1vεG1u+dG1v−1−C2εG1u=0,Case 2.εH1u=εH2vIn this case,εG1u=1+εH1u, εG2u=εH1u, εG1v=1+εH2v, and εG2v=1+εH1v. It follows that(17)ξEceG2−ξEceG1>C1+C2+1εG2u−C1+dG1vεG1u+dG1u+dG1v−1εG2v−C2+dG1uεG1v=C1+C2+1εH1u−C1+dG1v1+εH1u+dG1u+dG1v−11+εH1u−C2+dG1u1+εH1u=1+C1+C21εH1u−11+εH1u>0.Case 3.εH1u<εH2v.In this case,εG1u=1+εH2v, εG2u=εH2v, εG1v=εH2v, and εG2v=1+εH2v. It follows that(18)ξEceG2−ξEceG1>C1+C2+1εG2u−C1+dG1vεG1u+dG1u+dG1v−1εG2v−C2+dG1uεG1v=C1+C2+1εH2v−C1+dG1v1+εH1v+dG1u+dG1v−11+εH2v−C2+dG1uεH2v=1+C1+C21εH2v−11+εH2v>0.
This completes the proof.Theorem 7.
LetG be a connected graph on n vertices with k≥1 cut edges. Then,(19)ξEceG2≤n−122+n−kn−k−122+k,with equality if and only if G≅Knk.Proof.
Suppose thatG0 is a connected graph on n vertices with k≥1 cut edges and the maximal Ediz eccentric connectivity index. By Lemma 3, all cut edges in G0 must be pendent edges. From the proof of Theorem 6, the proof is completed.


### 3.2. Numerical Result and Analysis

As we know, infinitely many topological indices exist. The number of similarity measures like the ones employed in this paper is infinite too. So, finding a suitable topological index to obtain a better measure is an interesting question. This section contributes to the results obtained by comparing the similarity measures based on topological indices by means of two different perspectives. We shall discuss numerical results to underpin our analytical findings.The first method is to comparing the similarity measures based on topological indices and graph edit distance. Graph edit distance serves as a benchmark similarity measure, but it is generally NP-hard. Here, we shall compare how close the similarity measures based on topological indices (Wiener index, graph energy, Randić, the largest adjacent eigenvalue, the largest Laplacian eigenvalue, connective eccentricity index, and Ediz eccentric connectivity index) and graph edit distance are. We choose all nonisomorphic trees whose number of vertices is from 6 to 9, respectively. To ensure the comparability of the two measures, we revise the graph edit distance for trees as(20)gedT1,T2=1−12n−6GEDT1,T2,where GEDT1,T2 is the graph edit distance of trees T1,T2. The number 1/2n−6 is the standardization coefficient which is used to standardize the value of graph edit distance into the interval 0,1. This revised graph edit distance is still a benchmark similarity measure. To compare the similarity measure with the graph edit distance, we employ the least square method as follows to compute the error between each similarity measure and revised graph edit distance:(21)∑Ti,TjdITi,Tj−gedTi,Tj2,where the summation is over all pairs of the different nonisomorphic trees with the same number of vertices.Numerical results are shown in Figure1. It shows that the similarity measure based on Wiener index has more advantage than the one based on Ediz eccentric connectivity index, but the measure based on Ediz eccentric connectivity index has more advantage than the ones based on other topological indices (graph energy, Randić index, the largest adjacent eigenvalue, the largest Laplacian eigenvalue, and connective eccentricity index).Figure 1
Errors between graph edit distance and similarity measures based on Wiener index (Wiener), graph energy (Energy), Randić index (Randic), the largest adjacent eigenvalue (lambda), the largest Laplacian eigenvalue (mu), connective eccentricity index (CEI), and Ediz eccentric connectivity index (EECI). TheX-axis represents different topological indices. The Y-axis represents the distributions of error values between graph edit distance and similarity measures.Distribution of the ranked values of the similarity measure based on Wiener index (W), graph energy (ℰ), Randić index (R), the largest adjacent eigenvalue (λ), the largest Laplacian eigenvalue (μ), connective eccentricity index (CEI), and Ediz eccentric connectivity index (EECI). The X-axis represents the values of the distance measure. The Y-axis represents the percentage rate of all graph pairs studied.The second method is to compare the values of different similarity measures on the set of 14-vertex trees. The number of trees with 14 vertices is 3159 and the number of pairs is 4988061, see [29]. Here, we compare the measures based on the seven topological indices. From the plots shown by Figure 2, some inequalities are demonstrated as follows:(22)dWT1,T2≥dξEecT1,T2,dξEecT1,T2≥dRT1,T2,dξEecT1,T2≥dℰT1,T2,dξEecT1,T2≥dλT1,T2,dξEecT1,T2≥dμT1,T2,dξEecT1,T2≥dξceT1,T2,where the subscripts W, R, ℰ, λ, μ, ξce, and ξEec are the abbreviations of Wiener index, graph energy, Randić index, the largest adjacent eigenvalue , the largest Laplacian eigenvalue, connective eccentricity index, and Ediz eccentric connectivity index, respectively. These inequalities reveal the same result as the one obtained from the first method. So, the similarity measure based on Ediz eccentric connectivity index has certain advantage to some extent.Figure 2
Nonisomorphic tree with 14 vertices.In fact, we derive the same result by employing two other datasets. One dataset is random regular graphs on 100 vertices with degree 3, another is Watts–Strogatz small-world graphs on 100 vertices withk=4 and p=0.2. The results are shown in Figures 3 and 4.Figure 3
Random regular graph withN=100 and d=3.Figure 4
Watts–Strogatz small-world graph withN=100, k=4, and p=0.2.Next, we shall present an upper bound for the similarity measure based on Ediz eccentric connectivity index among all connected graphs onn vertices.Theorem 8.
LetG1andG2 be two connected graphs on n vertices. Then, we have(23)dξEecG1,G2≤dξEecKn,Pn,with equality if and only if G1andG2 are KnandPn, respectively. Moreover, ξEecKn=nn−12 and(24)ξEecPn=22n−1+3n−2+4n−3+4n−4+⋯+4n+1/2+4n−1/2for n is odd,22n−1+3n−2+4n−3+4n−4+⋯+4n/2for n is even.Proof.
From the definition of Ediz eccentric connectivity index, one hasξEecG<ξEecG+e for a noncomplete graph G and e∈EG¯ since adding an edge should increase the degree of some vertex. This means that adding an edge will increase the Ediz eccentric connectivity index. So, the complete graph Kn has the maximal Ediz eccentric connectivity index among all connected graphs with n vertices. On the contrary, the graph with minimal Ediz eccentric connectivity index among all connected graphs on n vertices must be a tree. We recall that the path Pn has the minimal Ediz eccentric connectivity index among all trees with n vertices [7]. Therefore, the path Pn has the minimal Ediz eccentric connectivity index among all connected graphs with n vertices. So, the following holds.
Note that the functionfx=1−e−x2 is an increasing function when x≥0. So, among all connected graphs on n vertices dξEecG,H attains the maximal value which are KnandPn, respectively. From the definition of Ediz eccentric connectivity index, we can directly compute the values ξEecKn and ξEecPn.


## 3.1. Extremal Values of Ediz Eccentric Connectivity Index

LetG be an unweighted, undirected graph with vertex set VG. For vertices u,v∈VG, the distance du,v is defined as the length of the shortest path between u and v in G. The eccentricity εv of a vertex v is the maximum distance from v to any other vertex. Obviously, εv≥1, for any vertex v∈VG.Theorem 1.
LetG be a graph on n vertices with the decreasing degree sequence d1,d2,…,dn. Then,(3)ξEceG≤∑i=1ndi2,with equality if and only if G is a complete graph.Proof.
Sinceεv≥1 for any v∈VG, then(4)ξEceG≤∑v∈VGSv1=∑v∈VGSv=∑v∈VG∑u∼vdu=∑i=1ndi2,where u∼v means that u is adjacent to v. The above equalities hold if and only if εv=1 for any v∈VG, i.e., G is a complete graph.Remark 1.
Since the first Zagreb index [26] of a graph G is defined as M1G=∑u∈VGdu2, the result ξEceG≤M1G holds. The equality holds if and only if G is a complete graph.
Average eccentricity of a graphG on n vertices is defined as ζG=1/n∑v∈VGεv. A relation between Ediz eccentric connectivity index and average eccentricity is present as follows.Theorem 2.
LetG be a graph on n vertices. Then,(5)ξEceG≤nn−12ζG,with equality if and only if G is a complete graph.Proof.
Sinceεv≥1 for any vertex v∈VG, then 1/εv≤εv with equality if and only if εv=1. Moreover, dv≤n−1. Therefore,(6)ξEceG=∑v∈VGSvεv≤∑v∈VGεvSv≤∑v∈VGn−12εv=nn−12ζG.
The first equality holds if and only if1/εv=εv, i.e., G is a complete graph. The second equality holds if and only if dv=n−1 for any v∈VG, i.e., G is a complete graph.Theorem 3.
LetG be a graph on n vertices with independence number α. Then,(7)ξEceG≤n−αn−1n+α−1+n−αα,with equality if and only if G≅Kn−α∨Kα¯.Proof.
LetG be the set of graphs on n vertices with independence number α. Assume that G0∈G has the maximal Ediz eccentric connectivity index. Let VG0 be the vertex set of G0 and S=v1,v2,…,vα be the maximal independence set. Let G∗ be the subgraph, induced by VG0/S, of G0. Since adding an edge shall increase the Ediz eccentric connectivity index, G∗ is complete. Moreover, there must exit an edge joining any two vertices between S and VG0/S in G0. So, G0≅Kn−α∨Kα¯. By directed computation, we have ξEceKn−α∨Kα¯=n−αn−1n+α−1+n−αα.
LetγG be the covering number of a graph G. It is well known that αG+γG=n. From Theorem 3, the following holds.Corollary 1.
LetG be a connected graph on n vertices with covering number γ. Then,(8)ξEceG≤γn−12n−γ−1+γn−γ,with equality if and only if G≅Kγ∨Kn−γ¯.In [23, 27], authors investigated the eccentric distance sum and connective eccentricity index of graphs with vertex connectivity, respectively. By modifying their methods, we have the following.Theorem 4.
LetG be a connected graph on n vertices with the vertex connectivity κ. Then, ξEceG≤κκ−12n−κ−1+3/2κ−1n−κ2−2n−κ−1+1/2κn−1n−κ+1/2n−κ3−3n−κn−κ−1 with equality if and only if G≅Kκ∨K1∪Kn−κ−1.Proof.
LetG0 be a graph having the maximal Ediz eccentric connectivity index among all connected graphs on n vertices with vertex connectivity κ. Then, there exists a vertex cut C⊂VG0 with C=κ such that G0−C=G1∪G2∪⋯∪Gt, where G1,G2,…,Gt are t≥2 connected components of G0−C. Since adding an edge shall increase Ediz eccentric connectivity index, t=2 and G1,G2 and GC are complete graphs, any vertex of G1 and G2 is adjacent to any vertex in C. So, G0≅Kκ∨Kn1∪Kn2 and n1+n2=n−κ for ni=Gi (i=1,2). By directly computing, we have(9)ξEceKκ∨Kn1∪Kn2=32κ−1n−κ2−2n1n2+12n−κ3−3n−κn1n2.
Note thatn1n2=n1n−κ−n1≥n−k−1 with equality if and only if n1=1, n2=n−κ−1, or n2=1, n1=n−κ−1. Then, ξEceG≤κκ−12n−κ−1+3/2κ−1n−κ2−2n−κ−1+1/2κn−1n−κ+1/2n−κ3−3n−κn−κ−1, with equality if and only if G≅Kκ∨K1∪Kn−κ−1.
Tk,n, which is called Turán graph, is the complete k-partite graph on n vertices in which all parts are as equal in size as possible.Lemma 1.
(see [28]). Let G be a graph which contains no Kk (k≥2). Then, EG|≤|ETk−1,n with equality if and only if G≅Tk−1,n.
The following is immediate from Lemma1.Lemma 2.
A graphG is connected with EG>1/4VG2, and then G contains at least one triangle.Theorem 5.
LetG be a triangle-free connected graph on n vertices. Then, ξEceG≤n2n−2/4 if εu>1 for any vertex v∈VG, with equality if and only if G≅K2,2. Otherwise, ξEceG≤n2−1/2, with equality if and only if G≅K1,n−1.Proof.
LetG be a triangle-free graph with the maximal Ediz eccentric connectivity index. If there exists a vertex u∈VG such that εu=1, then du=n−1. Hence, G≅K1,n−1 since G is triangle-free. Assume that εv>1 for v∈VG. Then, dv≤n−2 and(10)ξEceG=∑v∈VGSvεv≤12∑v∈VGSv≤12∑v∈VGn−2dv=n−2|EG|≤n2n−24,by Lemma2.
The above equalities holds if and only ifεv=2, dv=n−2 for all v∈VG and EG=n2/4, i.e., G≅K2,2. By computing, ξEceK1,n−1=n2−1/2.Theorem 6.
LetG be a connected graph on n vertices with k pendent vertices. Then,(11)ξEceG≤n−122+n−kn−k−122+k,with equality if and only if G≅Knk, where Knk is a graph obtained from Kn−k by attaching k pendent edges to one vertex of Kn−k.Proof.
LetG0 be the graph on n vertices with k pendent vertices and the maximal Ediz eccentric connectivity index. Assume that v1,v2,…,vk be the set of pendent vertices in G0. The subgraph G0′ induced by VG0/v1,v2,…,vk is a complete graph. In what follows, we would prove that G0≅Knk.
Suppose that there exist at least two vertices ofG0′ such that their degrees are more than n−k−1. Set vi,vj∈VG0′ and dvi≥dvj>n−k−1. Let G1 be the new graph obtained from G0 by removing all pendent vertices attached to vj and attaching them to vi. Let V1 (V2) be the set of pendent vertices attached to vi (vj) in G0′. Let V3 be the set of pendent vertices not in V1 or V2.
Note thatεG0vi=εG1vi=2, εG0vj=εG1vj=2, and εG0v=εG1v=2 for v∈VG0′/vi and εG0v=εG1v=3 for v∈V1∪V2∪V3. The degree of vertex in VG0/vi,vj does not change, but the degree of vi increases by V2 and the one of vj decreases by V2. Let C be the sum of the degrees of vertices in VG0′/vi,vj. Note that C is a constant under G0 and G1. By the definition of Ediz eccentric connectivity index, we have(12)ξEceG0=∑v∈VG0′/vi,vjC+dG0vi+dG0vj2+∑v∈V1dG0vi3+∑v∈V2dG0vj3+∑v∈V3SG0v3+SG0vi2+SG0vj2,ξEceG1=∑v∈VG1′/vi,vjC+dG1vi+dG1vj2+∑v∈V1dG1vi3+∑v∈V2dG1vj3+∑v∈V3SG1v3+SG1vi2+SG1vj2=∑v∈VG0′/vi,vjC+dG0vi+dG0vj2+∑v∈V1dG0+V23+∑v∈V2dG0+V23+∑v∈V3SG0v3+SG0vi2+SG0vj2.
Then,(13)ξEceG0−ξEceG1=−∑v∈V1V23+∑v∈V2dG0vj−dG0vi−V23<0,and this is a contradiction. So, G0≅Knk.
By computing, it follows thatξEceKnk=n−12/2+n−kn−k−12/2+k.Lemma 3.
LetH1 and H2 be two disjoint connected graphs on at least 2 vertices with u∈VH1 and v∈VH2. G1 is the graph obtained from H1∪H2 by adding an edge uv. G2 is the graph obtained from H1∪H2 by identifying u and v (to be a new vertex, say, u) and adding a pendent edge, say uv without confusion. Then, ξEceG1<ξEceG2.Proof.
LetV1 be the set of neighbors of u in H1 and C1 be the sum of degrees of vertices in V1. Let V2 be the set of neighbors of v in H2 and C2 be the sum of degrees of vertices in V2. Note that εG1x≥εG2x for all x∈VH1∪VH2/u,v and SG1x=SG2s for x∈VH1∪VH2/V1∪V2∪u,v. So, we have(14)ξEceG1=∑x∈VH1/V1∪uSG1xεG1x+∑x∈VH2/V2∪vSG1xεG1x+∑x∈V1SG1xεG1x+∑x∈V2SG1xεG1x+SG1uεG1u+SG1vεG1v=∑x∈VH1/V1∪uSG1xεG1x+∑x∈VH2/V2∪vSG1xεG1x+∑x∈V1SG1xεG1x+∑x∈V2SG1xεG1x+C1+dG1vεG1u+C2+dG1uεG1v.Case 1.εH1u≥1+εH2vIn this case,εG1u=εH1u=εG2u and εG1v=1+εH1u=εG2v. It follows that(15)ξEceG2=∑x∈VH1/V1∪uSG2xεG2x+∑x∈VH2/V2∪vSG2xεG2x+∑x∈V1SG1x+dG1v−1εG2x+∑x∈V2SG1x+dG1u−1εG2x+C1+C2+1εG2u+dG1u+dG1v−1εG2v.Then,(16)ξEceG2−ξEceG1≥∑x∈VH1/V1∪uSG2x−SG1xεG1x+∑x∈VH2/V2∪vSG2x−SG1xεG1x+∑x∈V1dG1v−1εG1x+∑x∈V2dG1u−1εG1x+C1+C2+1εG1u−C1+dG1vεG1u+dG1u+dG1v−1εG1v−C2+dG1uεG1v>1+C2−dG1vεG1u+dG1v−1−C2εG1v>1+C2−dG1vεG1u+dG1v−1−C2εG1u=0,Case 2.εH1u=εH2vIn this case,εG1u=1+εH1u, εG2u=εH1u, εG1v=1+εH2v, and εG2v=1+εH1v. It follows that(17)ξEceG2−ξEceG1>C1+C2+1εG2u−C1+dG1vεG1u+dG1u+dG1v−1εG2v−C2+dG1uεG1v=C1+C2+1εH1u−C1+dG1v1+εH1u+dG1u+dG1v−11+εH1u−C2+dG1u1+εH1u=1+C1+C21εH1u−11+εH1u>0.Case 3.εH1u<εH2v.In this case,εG1u=1+εH2v, εG2u=εH2v, εG1v=εH2v, and εG2v=1+εH2v. It follows that(18)ξEceG2−ξEceG1>C1+C2+1εG2u−C1+dG1vεG1u+dG1u+dG1v−1εG2v−C2+dG1uεG1v=C1+C2+1εH2v−C1+dG1v1+εH1v+dG1u+dG1v−11+εH2v−C2+dG1uεH2v=1+C1+C21εH2v−11+εH2v>0.
This completes the proof.Theorem 7.
LetG be a connected graph on n vertices with k≥1 cut edges. Then,(19)ξEceG2≤n−122+n−kn−k−122+k,with equality if and only if G≅Knk.Proof.
Suppose thatG0 is a connected graph on n vertices with k≥1 cut edges and the maximal Ediz eccentric connectivity index. By Lemma 3, all cut edges in G0 must be pendent edges. From the proof of Theorem 6, the proof is completed.


## 3.2. Numerical Result and Analysis

As we know, infinitely many topological indices exist. The number of similarity measures like the ones employed in this paper is infinite too. So, finding a suitable topological index to obtain a better measure is an interesting question. This section contributes to the results obtained by comparing the similarity measures based on topological indices by means of two different perspectives. We shall discuss numerical results to underpin our analytical findings.The first method is to comparing the similarity measures based on topological indices and graph edit distance. Graph edit distance serves as a benchmark similarity measure, but it is generally NP-hard. Here, we shall compare how close the similarity measures based on topological indices (Wiener index, graph energy, Randić, the largest adjacent eigenvalue, the largest Laplacian eigenvalue, connective eccentricity index, and Ediz eccentric connectivity index) and graph edit distance are. We choose all nonisomorphic trees whose number of vertices is from 6 to 9, respectively. To ensure the comparability of the two measures, we revise the graph edit distance for trees as(20)gedT1,T2=1−12n−6GEDT1,T2,where GEDT1,T2 is the graph edit distance of trees T1,T2. The number 1/2n−6 is the standardization coefficient which is used to standardize the value of graph edit distance into the interval 0,1. This revised graph edit distance is still a benchmark similarity measure. To compare the similarity measure with the graph edit distance, we employ the least square method as follows to compute the error between each similarity measure and revised graph edit distance:(21)∑Ti,TjdITi,Tj−gedTi,Tj2,where the summation is over all pairs of the different nonisomorphic trees with the same number of vertices.Numerical results are shown in Figure1. It shows that the similarity measure based on Wiener index has more advantage than the one based on Ediz eccentric connectivity index, but the measure based on Ediz eccentric connectivity index has more advantage than the ones based on other topological indices (graph energy, Randić index, the largest adjacent eigenvalue, the largest Laplacian eigenvalue, and connective eccentricity index).Figure 1
Errors between graph edit distance and similarity measures based on Wiener index (Wiener), graph energy (Energy), Randić index (Randic), the largest adjacent eigenvalue (lambda), the largest Laplacian eigenvalue (mu), connective eccentricity index (CEI), and Ediz eccentric connectivity index (EECI). TheX-axis represents different topological indices. The Y-axis represents the distributions of error values between graph edit distance and similarity measures.Distribution of the ranked values of the similarity measure based on Wiener index (W), graph energy (ℰ), Randić index (R), the largest adjacent eigenvalue (λ), the largest Laplacian eigenvalue (μ), connective eccentricity index (CEI), and Ediz eccentric connectivity index (EECI). The X-axis represents the values of the distance measure. The Y-axis represents the percentage rate of all graph pairs studied.The second method is to compare the values of different similarity measures on the set of 14-vertex trees. The number of trees with 14 vertices is 3159 and the number of pairs is 4988061, see [29]. Here, we compare the measures based on the seven topological indices. From the plots shown by Figure 2, some inequalities are demonstrated as follows:(22)dWT1,T2≥dξEecT1,T2,dξEecT1,T2≥dRT1,T2,dξEecT1,T2≥dℰT1,T2,dξEecT1,T2≥dλT1,T2,dξEecT1,T2≥dμT1,T2,dξEecT1,T2≥dξceT1,T2,where the subscripts W, R, ℰ, λ, μ, ξce, and ξEec are the abbreviations of Wiener index, graph energy, Randić index, the largest adjacent eigenvalue , the largest Laplacian eigenvalue, connective eccentricity index, and Ediz eccentric connectivity index, respectively. These inequalities reveal the same result as the one obtained from the first method. So, the similarity measure based on Ediz eccentric connectivity index has certain advantage to some extent.Figure 2
Nonisomorphic tree with 14 vertices.In fact, we derive the same result by employing two other datasets. One dataset is random regular graphs on 100 vertices with degree 3, another is Watts–Strogatz small-world graphs on 100 vertices withk=4 and p=0.2. The results are shown in Figures 3 and 4.Figure 3
Random regular graph withN=100 and d=3.Figure 4
Watts–Strogatz small-world graph withN=100, k=4, and p=0.2.Next, we shall present an upper bound for the similarity measure based on Ediz eccentric connectivity index among all connected graphs onn vertices.Theorem 8.
LetG1andG2 be two connected graphs on n vertices. Then, we have(23)dξEecG1,G2≤dξEecKn,Pn,with equality if and only if G1andG2 are KnandPn, respectively. Moreover, ξEecKn=nn−12 and(24)ξEecPn=22n−1+3n−2+4n−3+4n−4+⋯+4n+1/2+4n−1/2for n is odd,22n−1+3n−2+4n−3+4n−4+⋯+4n/2for n is even.Proof.
From the definition of Ediz eccentric connectivity index, one hasξEecG<ξEecG+e for a noncomplete graph G and e∈EG¯ since adding an edge should increase the degree of some vertex. This means that adding an edge will increase the Ediz eccentric connectivity index. So, the complete graph Kn has the maximal Ediz eccentric connectivity index among all connected graphs with n vertices. On the contrary, the graph with minimal Ediz eccentric connectivity index among all connected graphs on n vertices must be a tree. We recall that the path Pn has the minimal Ediz eccentric connectivity index among all trees with n vertices [7]. Therefore, the path Pn has the minimal Ediz eccentric connectivity index among all connected graphs with n vertices. So, the following holds.
Note that the functionfx=1−e−x2 is an increasing function when x≥0. So, among all connected graphs on n vertices dξEecG,H attains the maximal value which are KnandPn, respectively. From the definition of Ediz eccentric connectivity index, we can directly compute the values ξEecKn and ξEecPn.


## 4. Conclusion

The Ediz eccentric connectivity index of a network is a topological invariant. In this paper, we have investigated some mathematical properties thereof. Furthermore, we explored similarity measures for networks by using the Ediz eccentric connectivity index. We compare the network similarity measures based on the Ediz eccentric connectivity index and other well-known topological indices such as Wiener index, Randić index, graph energy, the largest adjacent eigenvalues, the largest Laplacian eigenvalue, and connectivity eccentric index by means of two different methods. Numerical results show that the similarity measure based on Wiener index has more advantage than the one based on Ediz eccentric connectivity index, but the measure based on Ediz eccentric connectivity index has more advantage than the ones based on other topological indices (graph energy, Randić index, the largest adjacent eigenvalue, the largest Laplacian eigenvalue, and connective eccentricity index). This means that the similarity measure based on Ediz eccentric connectivity index has certain advantage to some extent.Actually, there are many useful topological indices, which are widely investigated, such as Wiener polarity index [30], eccentric connectivity index [31, 32], Estrada index [33], Laplacian Estrada index [34], extended Estrada index [35], and Kirchhoff index [36]. In the future we would like to study the network similarity measure, which is studied in this paper, based on the above indices and explore the relations between them and the one based on Ediz eccentric connectivity index.



---

*Source: 2567570-2020-12-03.xml*