Closed trail distance in a biconnected graph

RESEARCH ARTICLE Closed trail distance in a biconnected graph Vaclav Snasel, Pavla Drazdilova, Jan Platos* Department of Computer Science, Faculty of Electrical Engineering and Computer Science, VS ˇB - Technical University of Ostrava, 17. listopadu 15/2172, 708 33 Ostrava, Czech Republic *[email protected] Abstract Graphs describe and represent many complex structures in the field of social networks, biological, chemical, industrial and transport systems, and others. These graphs are not only connected but often also k-connected (or at least part of them). Different metrics are used to determine the distance between two nodes in the graph. In this article, we propose a novel metric that takes into account the higher degree of connectivity on the part of the graph (for example, biconnected fullerene graphs and fulleroids). Designed metric reflects the cyclical interdependencies among the nodes of the graph. Moreover, a new component model is derived, and the examples of various types of graphs are presented. Introduction More interconnected parts of graphs play an essential role in the social and natural sciences. The formalization of the term “more connected part” can be defined in many ways. In this article, we focus on generalizing biconnected components of a graph and we define a novel metric that considers higher degree of connectivity on the part of the graph. Biconnected components of the graph do not allow good scalability, and their definition is complicated for weighted graphs. Our approach is based on the cycle length limit in the definition of biconnected components. The first work devoted to the study of cycles of limited length is [1,2]. Topological data analysis often uses tools developed in algebraic topology [3–5]. Cycles play a significant role in algebraic topology. For example, Poincare ´’s theorem of duality [6] shows that the homology group H n (M,Z 2 ) is a space with the inner product above the field Z 2 where the inner product is defined as an intersection index. In the case that Mis a continuous manifold, then any homology class x2H 1 (M,Z 2 ) can be represented by a closed curve γM. In this case, the intersection index xxbecomes zero when and only when a small surrounding of the curve γis orientable. Cycles with limited length play an essential role in the application of algebraic topology [3, 4]. When calculating the topological properties of data, it is necessary to look for cycles of limited length [7,8]. Cyclical structures are also very often found in materials research. For example, fullerenes form long cycles [9], in which topological properties play an important role. Complex and social networks are another field in which cyclic structures appear [10]. The partitioning of large complex networks is a challenging task. Such networks are used as a representation of proteins, chemical compounds, co-author networks, social networks, etc. PLOS ONE | https://doi.org/10.1371/journal.pone.0202181 August 31, 2018 1 / 12 a1111111111 a1111111111 a1111111111 a1111111111 a1111111111 OPEN ACCESS Citation: Snasel V, Drazdilova P, Platos J (2018) Closed trail distance in a biconnected graph. PLoS ONE 13(8): e0202181. https://doi.org/10.1371/ journal.pone.0202181 Editor: Baruch Barzel, Bar-Ilan University, ISRAEL Received: October 17, 2017 Accepted: July 30, 2018 Published: August 31, 2018 Copyright: ©2018 Snasel et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Data Availability Statement: The data for this study are third-party data from Zachary’s Karate Club network. The minimal data set for this study can be accessed via http://konect.uni-koblenz.de/ networks/ucidata-zachary. The authors accessed the data in the same way as the instructions provided and they did not have any special access privileges that others would not have. Funding: This work was supported by the project SP2018/126 "Parallel processing of Big Data V" received by P. Drazdilova of the Student Grant System, VSB-Technical University of Ostrava. Competing interests: The authors have declared that no competing interests exist. The classical partitioning methods have problems with densely connected subgraphs that cannot be partitioned easily. A list of the largest biconnected component in the selected network was published by Leskovec [11]. In the case of protein interaction networks in computational biology, the authors in [12] found vertices that are articulation points (determined by the computing of biconnected components), but they have a low degree and, therefore, they are unlikely to be essential to the network. In [13] the authors found the biconnected components that enabled further analysis. Molecular topology [14] is another area where topological and metric distances are used in graphs representing molecules. The fullerenes are cage-like, hollow molecules of pseudospherical symmetry consisting of pentagons and hexagons only, resulting in a trivalent polyhedron with precisely three edges (bonds) joining every vertex occupied by carbon [9]. In graph theoretical terms, fullerenes belong to the class of cubic, planar, three-connected, and simple graphs, see Fig 1. The authors of [15] give an overview of some graph invariants that can possibly correlate with the stability of a fullerene molecule. Fullerenes have been the subject of intense research for their unique physical, chemical, and biological properties and for their technological applications, especially in materials science, electronics, nanotechnology, and medicine [16–19]. The measuring of the distances between two nodes in a graph is a difficult task. The standard measure for this distance is the shortest path between two nodes in a graph [20,21]. Another way is the expected lengths of random walks on the graph, which can be used to derive the commute time distance [22]. The authors of [23] examine generalized distances on graphs that interpolate, depending on a defined parameter, between the shortest path distance and the commute time or resistance distance. Variants of node distances are described in detail in [24–27]. In addition to the node distance measure, the quality of the components (partitions) is also measured by means of several approaches. In 2014, a metric that measured the quality of communities according to the number of 3-cycles split across the communities was published [28]. The idea is based on the four types of directed triangles that contain cycles. These triangles are used to identify communities in directed networks. In [29], a measure that integrates both the concept of closed walks and clustering coefficients to replace the edge betweenness in the divisive hierarchical clustering algorithm (the Girvan and Newman method) was published. Levoranto et al. [30] used the strongly p-connected components for community detection in oriented networks. Community detection in undirected graphs is different. One of the major and well-known approaches uses the union of cliques to define a community [31]. Edaschery et al. [32] defined distance-k clique of a graph G= (V,E) as a subgraph of Gwith a diameter k. The authors use these distance-k cliques for a clustering. Our approach defines a new type of metric in a graph based on “cyclical distances“. This metric is based on the definition of a biconnected component. The distance between two vertices in the graph is defined as the length of the shortest closed trail that contains these two vertices. The distance defined in this way allows straightforward generalization for weighted graphs and also allows scalability. In this article, we define a new measure on an undirected connected graph without bridges for the measurement of distances using cyclic subgraphs. This measure satisfies the metric properties. Our innovative measure may be used to define a new type of components that highlight the locally connected subgraphs. Moreover, these components are not based on the biconnectivity property and, therefore, are able to partition densely connected biconnected components easily. We will first introduce the terminology and the notation which we use in the article. In the next section, we define the new distance in biconnected undirected graphs, and we describe Closed trail distance in a biconnected graph PLOS ONE | https://doi.org/10.1371/journal.pone.0202181 August 31, 2018 2 / 12 some properties of this distance. In conclusion, we discuss the advantages and limitations of the defined distance. Terminology and notation In this section, knowledge of graph theory will be required. The definitions of the following terms were taken from [33]: Aloop is an edge (directed or undirected) that joins a single endpoint to itself. A walk on a graph is an alternating series of vertices and edges Wðvð0Þ;vðkÞÞ ¼ vð0Þeð1Þvð1Þeð2Þ. . . vðk1ÞeðkÞvðkÞ such that for j= 1, . . .,kthe vertices v (j−1) and v (j) are the end points of the edge e (j) . A closed walk is a walk where the initial vertex is also the final vertex. The length of a walk is the number of edges in this walk. We will denote the length of a walk W(u,v) as |W(u,v)|. A trail is a walk in which no edge occurs more than once. A closed trail (circuit) is a closed walk with no repeating edges. We will denote a closed trail which contains the vertices u,vas CTðu;vÞ ¼ ueð1Þvð1Þeð2Þ. . . v...eðkÞu: Fig 1. Graph of a fulleroid C 260 −I[5, 7] (The image was provided by Peter Schwerdtfeger, Lukas N. Wirz and James Avery under a CC BY license). https://doi.org/10.1371/journal.pone.0202181.g001 Closed trail distance in a biconnected graph PLOS ONE | https://doi.org/10.1371/journal.pone.0202181 August 31, 2018 3 / 12 Apath is a walk in which no edge or internal vertex occurs more than once (a trail in which all the internal vertices are distinct). We will denote a path with an initial vertex uand a final vertex vas P(u,v). A cycle is a closed path with a length at least one. We will denote the closed path containing u,vas CP(u,v). A clique is a subgraph where each node is adjacent to every other node. A planar graph is a graph that can be drawn on a sphere or a plane with no edge crossings. Aconnected graph is a graph such that between every pair of vertices there exists a walk. A graph is called k-connected if the removal of fewer than kvertices leaves neither a non-connected graph nor a trivial one. A component of a graph is a maximal connected subgraph. An edge eis a bridge of the connected graph Gif {e} is a disconnecting edge-set of G. An articulation is a vertex of a graph whose removal increases the number of components. A biconnected graph is a connected and “nonseparable” graph, meaning that if any vertex were to be removed, the graph would remain connected. Therefore a biconnected graph has no articulation vertices. The property of being 2-connected is equivalent to biconnectivity, with the caveat that the complete graph of two vertices is sometimes regarded as biconnected but not 2-connected. This property is especially useful in maintaining a graph with a two-fold redundancy, to prevent disconnection upon the removal of a single edge (or connection). Abiconnected component (or 2-connected component) is a maximal biconnected subgraph. Equivalent characterizations of biconnectivity Let G= (V,E) be a simple undirected graph (loop-less, no multiple edges) that contains at least three points. Each of the following statements is equivalent to that G is biconnected 1. for every v 1 ,v 2 2Vthere is a circuit of G containing v 1 and v 2 , 2. E6¼;and for every v2Vand e2Ethere is a cycle of G containing vand e, 3. Ghas no isolated vertices and for every e 1 ,e 2 2Ethere is a cycle containing e 1 and e 2 , 4. for every v 1 ,v 2 ,v 3 2Vthere is a path from v 1 to v 2 containing v 3 , 5. for every v 1 ,v 2 ,v 3 2Vthere is a path from v 1 to v 2 not containing v 3 , 6. E6¼;and for every v 1 ,v 2 2Vand e2Ethere is a path from v 1 to v 2 containing e. The shortest path metric (d sp ) [25] is the one most commonly used to determine the distance between vertices of the graph. It is a metric on the vertex-set Vof a connected graph G= (V,E), defined, 8u,v2V, as the length of the shortest path (P(u,v)) in G. This metric does not affect greater coherence between vertices in the biconnected graph. Our goals in this article are to define a new metric on the undirected biconnected graph for the measurement of distances using cyclic subgraphs and to use higher connectivity among the vertices in the biconnected graph. Closed trail distance in a biconnected graph without loops In this section, a metric between the vertices in a biconnected graph without loops via a closed trail (circuit) will be defined. Closed trail distance in a undirected graph Definition 1.A graph is a k-closed trail connected graph (k-CT)if everytwo vertices lie on the closed trail (circuit) with a length k. A k-CT component of the graph is a maximal k-CT subgraph. Closed trail distance in a biconnected graph PLOS ONE | https://doi.org/10.1371/journal.pone.0202181 August 31, 2018 4 / 12 Definition 2.A1-CT graph is a graph where everytwo verticeslie on a closed trail of any length. Definition 3.Let G = (V,E)be a graph. Let dct :VV!Rþ 0be defined by the equation dctðu;vÞ ¼ minCTðu;vÞGjCTðu;vÞj; where CT(u,v)is a closed trail that contains the vertices u, v. Then the function d ct is called the closed trail distance (CT-distance). Theorem 1.The CT-distance is a metric on the set V. Proof. We verify the properties of the metrics. From Definition 3 it follows that d ct (v,v) = min CT(v,v)2G |CT(v,v)|. The length of the shortest closed trail that started in a vertex vand ended in the same vertex is equal to 0. Then 8v2V d ct (v,v) = 0. And from the definition it follows that 8u,v2V d ct (u,v)0 because the distance between uand vis the number of edges in the closed trail containing uand v. Symmetry of the distance is obvious: 8u,v2V d ct (u,v) = min CT(u,v)2G |CT(u,v)| = d ct (v,u) because G= (V,E) is a undirected graph. The triangle inequality: 8u,v,z2V d ct (u,v) + d ct (v,z)d ct (u,z) is proved in a constructive way. Let CT(u,v) and CT(v,z) exist and let |CT(u,v)| = d ct (u,v) and |CT(v,z)| = d ct (v,z). In the biconnected graph 8u,v2Va closed path (CP(u,v)) exists. Then we have two possibilities for the closed trail which satisfy |CT(u,z)| = d ct (u,z). First: d ct (u,v) + d ct (v,z) = |CP(u,v)| + |CP(v, z)| |CP(u,z)| = d ct (u,z) which does not violate the triangle inequality. Second: if |CP(u,v)| + |CP(v,z)| <|CP(u,z)| then we can join CP(u,v) and CP(v,z) in the vertex vto one a closed trail CT(u,z) and d ct (u,v) + d ct (v,z) = |CP(u,v)| + |CP(v,z)| = |CT(u,z)| d ct (u,z) which does not violate the triangle inequality either. Example 1.Let graph G be defined as shown in Fig 2. Let d sc (u,v)be the length of the shortest closed cycle in the biconnected graph that goes through the nodes u and v. The d sc (u,v)is not a metric, because it does not satisfy the triangle inequality: dscðu;yÞþdscðy;vÞ<dscðu;vÞ: For the graph in Fig 2 it is true that d sc (u,y) = 4, d sc (y,v) = 4 and d sc (u,v) = 9. Fig 2. Example of biconnected graph where d sc (u,y) + d sc (y,v)<d sc (u,v). https://doi.org/10.1371/journal.pone.0202181.g002 Closed trail distance in a biconnected graph PLOS ONE | https://doi.org/10.1371/journal.pone.0202181 August 31, 2018 5 / 12 The violation of the triangle inequality by the cycles (d sc )may be solved using the closed trails (d ct ). In a similar way to that in which we defined the k-CT component, a k-SC component may be defined using cycles of a length up to k. The graph is a k-shortest cycle connected graph (kSC) if every two vertices lie on a cycle of the length k. The k-SC component of the graph is a maximal k-SC subgraph. Example 2.Figs 3and 4demonstrate maximal and different k-CT components in the undirected biconnected graph without loops. Lemma 1.Every 3-CT component is a clique. Proof. Let Co3 be a 3-CT component. According to Definition 3: 8u,v2Co3 |CT(u,v)| 3. It is obvious that this CT(u,v) contains only three vertices and three edges and there exists the edge (u,v). Therefore, all the vertices in Co3 are adjacent and create a clique. Example 3.Fig 5 shows the differences between the closed trail distance and the shortest path distance. We chose a subgraph of the fullerene graph for the comparison between distances. Lemma 2.Every closed trail with a length4 or 5 is a cyclewith the same length. Proof. Proof by contradiction. Let there exist a closed trail with a length of 4 (CT4) or a closed trail with a length of 5 (CT5) which is not a cycle. Let CP3 be a cycle (closed path) with a length of 3. It is obvious that it is not possible to create CT4 (CT5) on the set with one, two or three vertices because CT4 (CT5) contains four (five) different edges. We have at least four vertices and CT4 (CT5) has to contain the vertex uwhich appears at least three times in the sequence of the trail (the initial, final and inner vertex of the closed trail). Vertex uis initial and inner vertex of the trail if CT4 (CT5) contain CP3. When we add one (two) edge(s) to the CP3 we have a trail with a length of 4 (5) but it not possible to create a closed trail because the edge between the last—but—one vertex and initial (final) vertex is already on the trail (Fig 6). The only closed trails with a length of 4 (5) are therefore cycles with a length of 4 (5). Fig 3. 3-CT and 4-CT components of the graph. https://doi.org/10.1371/journal.pone.0202181.g003 Fig 4. 5-CT and 7-CT components of the graph. https://doi.org/10.1371/journal.pone.0202181.g004 Closed trail distance in a biconnected graph PLOS ONE | https://doi.org/10.1371/journal.pone.0202181 August 31, 2018 6 / 12 The demonstration of the impossibility of creating a CT4 or CT5 which is not a cycle and the vertex uis the initial, inner but not final vertex of the closed trail with a length 4 (5): CT4¼ue1xe2ye3ue4z;CT5¼ue1xe2ye3ue4ze5xðyÞ: The first closed trail that is not a cycle is CT6 (Fig 6, third picture). Theorem 2.The 3,4,5-CTcomponents are biconnected. They are the same as the 3,4,5-SC (shortest cycle)components. Proof. It is obvious for 3-CT components. The proof follows from Lemma 1. 3-CT components are cliques and therefore 3-CT components are biconnected. We suppose that for 4(5)-CT components it is not true. There exists a connected 4(5)-CT component which is not biconnected. Then the component contains the articulation x—see Fig 7. Then there exist vertices u,v, where d ct (u,v) = 4(5). From Definition 3 it follows that there exist CT(u,v) and |CT(u,v)| = 4(5) (CT(u,v) is blue in Fig 7). From Lemma 2 it follows that all closed trails with a length of 4(5) are cycles and then the vertex xis not an articulation. This is a contradiction. Example 4.The k-CT component is not sometime a biconnected subgraph for k 6. The 6-CT component can be the smallest closed trail-connected component which is not biconnected (Fig 6). Lemma 3.d ct (u,v)is a metric in any connected graph without bridges and defines the distances between two nodes u and v. Proof. The graph is connected without bridges. There is a path between any pair of nodes u and v. Let P 1 (u,v) = ue (1) . . . e (i) xe (i+1) . . . e (k) vbe a path between any pair of nodes uand v. Because the graph has no bridges (it is not 1-edge connected), a path P 2 (u,v) that has no common edge with P 1 (u,v) exists (see Fig 8). The joining of P 1 (u,v) and P 2 (u,v) creates a closed trail on which the nodes uand vlie (CT(u,v)). Therefore, a closed trail between any two nodes Fig 5. Selected vertices with the shortest path distance and the closed trail distance. https://doi.org/10.1371/journal.pone.0202181.g005 Fig 6. uis an initial and inner vertex in the trails T4 and T5. For the last closed trail CT6 is the vertex uinitial, inner and final. https://doi.org/10.1371/journal.pone.0202181.g006 Closed trail distance in a biconnected graph PLOS ONE | https://doi.org/10.1371/journal.pone.0202181 August 31, 2018 7 / 12 uand vwith a length of d ct (u,v) may be created in any connected graph without bridges. The connected graph without bridges is a 1−CT component. Corollary 1.Graph and component hierarchy is defined as follows: biconnected graph connected graph without bridges ¼ 1 CT component: Corollary 2.The ordering of type of components according to its cardinality is defined as follows: 3CT 4CT 5CT    1 CT: Example 5.Fig 9 shows the biggest 4-CTcomponent (blue vertices) in the biconnected subgraph (in the blue ellipse) of the Zachary’s karate club graph (Fig 9). This 4-CTcomponent is biconnected. The Table 1 contains numbers of k-CT components which are maximal for selected k. The Fig 10 shows the sample of k-CT components on the graph of fulleroid C 260 −I[5, 7]. Closed trail distance in a weighted undirected graph The definition of the CT-distance may be extended for the weighted graph G= (V,E,w) where wis a mapping w:E!R + . Definition 4.Let G = (V,E,w)be a weighted graph and let the mapping dwct:VV!Rþ 0 be defined by the equation dwctðu;vÞ ¼ minCTðu;vÞGX 8e2CTðu;vÞ 1 wðeÞ !: Then the function d wct is called the weighted closed trail distance (wCT-distance). Theorem 3.The wCT-distance is a metric on the set V. Proof. We verify the properties of the metrics. Fig 7. k-CT components. The first picture: x=2CT(u,v) and the component is biconnected. The second picture: x2 CT(u,v) where |CT(u,v)| = 3(4, 5) and the component is biconnected. The third picture: x2CT(u,v) where this CT is the shortest closed trail which is not a cycle and the component is not biconnected. https://doi.org/10.1371/journal.pone.0202181.g007 Fig 8. Path P 1 ,P 2 between vertices u,v.First graph is biconnected (P 1 \P 2 = {u,v}), second graph is connected with articulation and without bridge (P 1 \P 2 = {u,v,x}) and third graph is connected with bridge (P 1 \P 2 = {u,v,x, (x,v)}). https://doi.org/10.1371/journal.pone.0202181.g008 Closed trail distance in a biconnected graph PLOS ONE | https://doi.org/10.1371/journal.pone.0202181 August 31, 2018 8 / 12 From Definition 4 it follows that 8v2V dwctðv;vÞ ¼ minCTðv;vÞ2GðP8e2CTðv;vÞ 1 wðeÞÞ ¼ 0and 8u,v2V dtwðu;vÞ ¼ minCTðu;vÞ2GðP8e2CTðu;vÞ 1 wðeÞÞ  0. Symmetry of the distance is obvious: dwctðu;vÞ ¼ min8CTðu;vÞ2GðP8e2CTðu;vÞ 1 wðeÞÞ ¼ dwctðv;uÞbecause G= (V,E) is an undirected graph. A triangle inequality 8u,v,z2V d wct (u,v) + d wct (v,z)d wct (u,z), is proved in a constructive way. Let CT(u,v) be a closed trail with the property that P8e2CTðu;vÞ 1 wðeÞ¼dwctðu;vÞand let CT(v,z) be a closed trail with the property that P8e2CTðv;zÞ 1 wðeÞ¼dwctðv;zÞ. Suppose that a closed trail CT(u,v,z) formed by the merged closed trail CT(u,v) and CT(v,z) exists. This closed trail has a weight of wðCTðu;v;zÞÞ ¼ P8e2CTðu;vÞ 1 wðeÞþP8e2CTðv;zÞ 1 wðeÞ. This equality implies that d wct (u,z)d wct (u,v)+d wct (v,z) Definition 5.The k-wCT component is a maximal subgraph H which satisfies 8u,v2V d wct (u,v)k. Example 6.Fig 11 demonstrate a different wCT components. A closed trail marked in blue CT =v 1 −(v 1 ,v 2 )−v 2 −(v 2 ,v 4 )−v 4 −(v 4 ,v 3 )−v 3 −(v 3 ,v 1 )−v 1 has the weight 1 2þ1 10 þ1 1þ1 1¼13 5¼2:6.It is the 4-CT component with the biggest weight. There exist 4-CT or 5-CT components with smaller weight (red—{v 4 ,v 5 ,v 6 ,v 7 }and olive—{v 4 ,v 2 ,v 5 ,v 6 ,v 7 }).The red marked closed trail contains edges with bigger weight than a blue marked closed trail. The value of the wCTcomponent is useful for better scaling of components. Conclusion In this article, we defined a new metric for measuring the distance between two nodes of a biconnected graph. Moreover, the defined method holds the properties of a metric on the Fig 9. The largest 4-CT component (blue vertices) in the biconnected subgraph (in the blue ellipse) of Zachary’s karate club graph. https://doi.org/10.1371/journal.pone.0202181.g009 Table 1. The number of different k-CT components in the largest biconnected subgraph of Zachary’s karate club graph. 3-CT 4-CT 5-CT 6-CT 7-CT 8-CT 9-CT no. of components 20 17 10 6 3 2 1 https://doi.org/10.1371/journal.pone.0202181.t001 Closed trail distance in a biconnected graph PLOS ONE | https://doi.org/10.1371/journal.pone.0202181 August 31, 2018 9 / 12