# A Force-Directed Algorithm for Drawing Directed Graphs Symmetrically

Authors: Taihua Xu; Jie Yang; Guanglei Gou
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Symmetry is one of the most important aesthetic criteria on graph drawing. It is quite necessary to measure the extent to which the drawings can be considered symmetric. For this purpose, a symmetric metric based on vertex coordinate calculation is proposed in this paper. It is proven theoretically and experimentally that the proposed metric is robust to contraction, expansion, and rotation of drawings. This robustness conforms to human perception of symmetry. Star-subgraphs and cycles are two common structures in digraphs. Both of them have inherent symmetry which should be displayed in drawings. For this purpose, a force-directed algorithm named FDS is proposed which can draw star-subgraphs and cycles as symmetrically as possible. FDS algorithm draws cycles as circles whose positions are fixed to provide a scaffolding for overall layout, renders non-leaf vertices by a standard force-directed layout, and places leaf vertices on concentric circles via a deterministic strategy. A series of experiments are carried out to test FDS algorithm. The results show that FDS algorithm draws digraphs more symmetrically than the existing state-of-the-art algorithms and performs efficiency comparable toO(nlog⁡n) YFHu algorithm.


---

## Body

## 1. Introduction

Graph drawing is the research on how to communicate knowledge visually through drawings of graphs. The main purpose of graph drawing is to produce understandable drawings from graphs within bearable time. The understandability of drawings is a highly subjective matter and affected by not only intrinsic data characteristics [1], but also drawings themselves. The understandability affected by intrinsic data characteristics can be interpreted as whether the important structures, e.g., star-subgraphs and cycles, are drawn to be eye-catching in drawings. The understandability affected by drawings is specified as aesthetics. Bhanji et al. [2] summed up three common aesthetics: maximized symmetry, minimized edge crossings, and minimized bends. With the development of research on aesthetics, the number of common aesthetics increases to seven [3]. Furthermore, Ware et al. [4] believed that continuity (i.e., keeping multiedge paths as straight as possible) is also an important aesthetic. It is commonly accepted that a drawing would be understandable if it conforms to these aesthetics.Indubitably, symmetry is one of the most important aesthetic criteria that represents the structure and properties of a graph visually. The importance of symmetry on graph drawing has been pointed out by Lipton et al. [5]. Even Eades and Hong discussed symmetric graph drawing in a chapter of the book “Handbook of Graph Drawing and Visualization” [6]. Existing studies explored the issues of symmetry by combining with isomorphisms [7] and automorphisms [5, 8–10]. In addition, there also is an interesting research topic on symmetry in layouts sketched by participants [11–14]. However, symmetry is on the basis of human intuition and subjective judgement of researchers. In other words, symmetry would remain subjective if there is no quantified metric to measure it. There have been some objective metrics proposed for symmetry. A model for measuring the symmetry of straight line drawing was given by Lipton et al. [5]. But this model is associated with automorphisms which is computational hardly. Purchase [3] presented a formal metric to measure the extent to which the drawing can be considered symmetric by returning an objective real number between 0 and 1 inclusive. Although Purchase’s method is applicable to any drawing of any size, it ignored rotational symmetry. And the ignorance is in contradiction with human perception of symmetry. Thus, it is very necessary to develop an objective symmetric metric which is easy to compute and in accord with human perception of symmetry.Then the first contribution of this paper is that an objective symmetric metric is proposed to measure the extent to which the drawings produced by graph drawing algorithms can be considered symmetric, which is based on vertex coordinate calculation. Locally, this metric works out a value for every vertex, which can measure the extent to which neighbors can be considered to be distributed symmetrically around the vertex. Globally, expected value and variance of all local values are used to measure the extent to which the drawing can be considered symmetric. Compared to these existing symmetry metrics, the proposed symmetric metric in this paper is not only applicable to any drawing of any size, but also robust to contraction, expansion, and rotation of drawings. In addition, it can return metric values within few time because it is based on vertex coordinate calculation.As two common structures in digraphs, a star-subgraph contains a star vertex and several leaf vertices connecting the star vertex, and a cycle is defined as a closed path with no repetitions of vertices and edges. From viewpoint of knowledge visualization, star-subgraphs and cycles are worthy of being visualized since the two structures from digraphs are originally two kinds of knowledge. It should be noted that there is inherent symmetry in star-subgraphs and cycles, so these two structures should be displayed symmetrically in overall drawings. For drawing cycles, Becker and Rojas [15] once tried to draw cycles by circular layout algorithm. Although circular layout algorithm can display cycles as circles which is the most symmetrical geometric figure, it can not highlight circles. As a result, the circles can not be easily distinguished from overall drawings. On the other hand, the task of drawing star-subgraphs is essentially how to distribute leaf vertices around star vertices. There are already some works which involve leaf vertices. In multilevel force-directed approaches [16], they deal with leaf vertices by deletion. However, it is inappropriate from the viewpoint of knowledge discovery because removing of leaf vertices would cause loss of knowledge. The problem of drawing star-subgraphs symmetrically is actually the problem of drawing leaf vertices. Some multilevel force-directed approaches can display leaf vertices via coarsening phase [17]. However, displaying of these leaf vertices still takes noticeable time and does not exhibit sufficient inherent symmetry of star-subgraphs. RINGs [18], Circular [19], and Radial [20] layouts can also deal with leaf vertices. RINGs algorithm [18] places successors in concentric rings around the center of the predecessor circle for any digraphs. However, overlapping between vertices would be induced when other structures exist except for star-subgraphs. In the drawing of star-subgraphs, produced by Circular algorithm [19], vertices are placed on the same circle leading to insufficient space utilization. Star-subgraphs can be drawn with the shape of fan by Radial algorithm [20], which did not exhibit sufficient inherent symmetry of star-subgraphs. Thus, there is an urgent need for an algorithm which can draw digraphs containing star-subgraphs and cycles symmetrically conspicuously.In consideration of the demand for displaying star-subgraphs and cycles symmetrically, and based on above discussions, the second contribution of this paper is that a force-directed algorithm named FDS is proposed by using scaffolding strategy, which can solve the problems encountered in drawing star-subgraphs and cycles. The reason for taking scaffolding strategy is that the positions of cycle vertices should be fixed once the coordinates of them are acquired so that the symmetry displayed are not changed in the process of drawing other vertices. Similar scaffolding strategy has been used in [21, 22]. In [21], authors took spanning trees and planar graphs to provide a scaffolding for drawing so that structure and follow path can be discerned. Unlike [21], in this paper, we take the found cycles to provide the scaffolding for overall drawing so that cycles can be discerned from overall drawing. The basic idea of FDS is as follows: firstly, use HL-DPC algorithm [23] to discover cycles of digraphs, and a cycle drawing algorithm based on circle placement (CD-CP) is proposed as a subalgorithm of FDS. CD-CP algorithm can fix the cycle vertices on equal amount of highlighted circles which provide a fixed scaffolding to overall drawings. Secondly, a standard force-directed algorithm, FR algorithm [24], is taken to deal with non-leaf vertices. Thirdly, a leaf vertices distribution algorithm (LD) is proposed as a subalgorithm of FDS. LD algorithm can distribute leaf vertices evenly around the centers of star-subgraphs and star vertices, so that the drawing of star-subgraphs is symmetrical. Compared to existing methods, our FDS algorithm solves the problems when drawing cycles and star-subgraphs. For cycles, as FDS’s subalgorithm, CD-CP algorithm can not only distribute cycle as circles but also highlight them so that cycles are displayed symmetrically and conspicuously. For star-subgraphs, as FDS’s subalgorithm, LD algorithm can distribute leaf vertices belonging to star-subgraphs most symmetrically by cost of few time.It can be seen that a standard force-directed algorithm, FR, is used as a subalgorithm of proposed FDS algorithm. The reason for utilizing FR algorithm is that force-directed algorithms are the most widely used tools for graph drawing and famous for ability of producing pleasing layouts having balanced aesthetics. The basic idea of force-directed algorithm is that a graph is simulated by a physical system of attractive spring forces along edges and repulsive forces emanating from vertices. Then vertices will move along the direction of the combined force. These movements are repeated until the force system reaches equilibrium. There are already various force-directed algorithms. In 1984, Eades [26] proposed a landmark force-directed algorithm. However, Eades’s implementation does not follow Hook law but the spring force formula built by himself. Kamada and Kawai (KK) [27] proposed an energy model which made improvement on Eades’s spring model. KK algorithm uses spring forces proportional to the graph theoretic distances. Appealing drawing can be obtained by decreasing the system total energy until minimum. Fruchterman and Reingold (FR) [24] referenced the works of Eades [26] and Quinn [28]. They used a spring-electrical system, which is based on Coulomb’s law, to take the place of Eades’s spring physical system. Although FR is a very simple algorithm, it provides quite excellent results. Even today, it is still one of the most popular algorithms for graph drawing. Jacomy [29] proposed the well-known forceatlas2 algorithm by reference of LinLog model. Forceatlas2 algorithm can produce good quality with few iterations for most graphs [30]. An important improvement on force-directed algorithms is the multilevel technique. There are some famous multilevel graph algorithms, such as FMS [31], GRIP [32], Walshaw’s [33], FM3 [16], and YifanHu [17] algorithms. YifanHu algorithm is both efficient and high quality, which is proposed based on combining a multilevel approach with the Barnes and Hut [34] octree technique. There are other outstanding algorithms, such as Gansner’s stress majorization [35], Landmark MDS [36], PivotMDS [37], and MaxEnt [38].This paper is organized as follows. In Section2, related definitions and works are given. In Section 3, a symmetric metric based on vertex coordinate calculation is proposed to measure the extent to which the drawings produced by various algorithms can be considered symmetric. In Section 4, the proposed FDS algorithm is described in detail. In Section 5, a Gephi layout plugin is developed in NetBeans that is a software development platform written in Java. Related experiments are performed to compare the efficiency and quality of FDS algorithm with existing methods, including FR algorithm [24], YifanHu algorithm [17], and ForceAtlas2 algorithm [29]. Finally, in Section 6 a conclusion is given.


## 2. Related Work

In this section, firstly, we briefly review several related graph definitions; secondly, HL-DPC algorithms [23] should be reviewed shortly because it is used to compute cycles of digraphs; thirdly, FR algorithm [24], a standard force-directed algorithm, also should be introduced briefly because we take it to draw non-leaf vertices of digraphs.


### 2.1. Related Graph Definitions

In order to facilitate the descriptions in this paper, related definitions of graph theory are introduced here. A graph may be either directed or undirected. A digraph is a pairD={V,E}, where V represents the set of vertices and E the set of directed edges. Aleaf vertex  is a vertex with degree one. Auniversal vertex  is a vertex that is adjacent to every other vertex in the graph. Astar vertex  is a vertex that is adjacent to severalleaf vertices. Astar vertex  and its adjacent leaf vertices can derive astar-subgraph. If a closed path is with no repetitions of vertices and edges, then the path is called a directedcycle. As the two notions,leaf vertices  and subgraphs, are involved in this work, related definitions are also introduced as follows.Definition 1 (see [39]).
LetD={V,E} be a simple graph. The subgraph induced by a subset W of the vertex set V is the graph {W,F}, where the edge set F contains an edge in E if and only if both endpoints of this edge are in W.Definition 2.
LetD={V,E} be a digraph, with V the set of vertices and E the set of edges, where V={v1,v2,…,vn-1,vn}. The number ofleaf vertices associated with vi is denoted by leaf_number(i).Definition 3.
LetD={V,E} be a digraph. The number ofleaf vertices in D is denoted by nleaf(D). Then the proportion ofleaf vertices in D is denoted by pleaf(D), which is calculated by(1)pleafD=nleafDV.


### 2.2. HL-DPC Algorithms [23]

One of the purposes of this paper is to draw cycles as symmetric as possible. The precondition of drawing cycles is finding cycles. In [23], HL-DPC algorithm is proposed to find cycles from strongly connected components (SCCs) with 3 vertices at least which is proven to contain cycles certainly. The main idea of the HL-DPC algorithm is to conduct heuristic DFS to a given SCC which is found from a digraph via Tarjan’s algorithm [40]. There are two pieces of heuristic information to decide whether DFS is forward or backward and control the process of DFS on choosing vertices. A stack S is used for recording the vertices visited by heuristic DFS. If a vertex u belonging to S is visited again but the size of S does not meet the experimental threshold, then u would be removed from S. DFS continues to run from the top vertex in S until visiting vertex is visited again and the size of S meets an experimental threshold. Then a cycle is asserted to be found.The two pieces of heuristic information used in HL-DPC algorithm are introduced as follows. Firstly, a direction parameter is introduced to decide whether DFS is forward or backward.Definition 4 (see [23]).
LetD={V,E} be a digraph. Dscc3={Vscc3,Escc3} is a SCC of D with 3 vertices at least. A direction parameter, ratio, is defined by(2)ratio=∏v∈Vscc3Sdeg+v∏v∈Vscc3Sdeg-v.In (2), Sdeg+(v) and Sdeg-(v) are the number of outgoing edges and incoming edges adjacent to vertex v in the SCC, respectively. Then according to the value of ratio, the direction of DFS can be determined by the corresponding formula in [23]. The experiments in [23] also show that the proposed parameter is necessary and useful.Secondly, DFS will visit neighbor vertex with maximumSdeg+(v) and Sdeg-(v) of visited vertex v. The second heuristic information is also proved to be necessary by corresponding experiments in [23].


### 2.3. FR Algorithm [24]

In this paper, we take a standard force-directed algorithm as a part of our methods. It is necessary to review it briefly. Force-directed algorithms model the graph drawing problem by calculating attractive and repulsive forces between vertices. Optimal drawing would be achieved when the energy of system descends to the minimum. Force-directed algorithms can produce appealing drawings for most graphs and display isomorphic and symmetric substructures. Although there is a drawback of high runtime compared to other graph drawing algorithms, force-directed algorithms still dominate the algorithms of graph drawing. FR algorithm which requiresO(n2) time is one of the most famous force-directed algorithms. It was proposed by Fruchterman and Reingold [24] based on the famous Eades’s spring force-directed [26] model. Although FR is a very simple algorithm, it provides quite excellent results. Even today, after years of its creation, it is still one of the most popular algorithms for graph drawing. In this work, FR algorithm will be used to calculate repulsive and attractive forces between vertices.Fruchterman and Reingold represented the graph drawing problem by a system of electrically charged vertices connected by some springs. There are only two criteria demanded for a good graph drawing.(1) Connected vertices should be close to each other. (2) Vertices should not be drawn too close to each other.Certainly FR model also moves vertices according to the attractive and repulsive forces. When the total energy of the system decreases to a minimum, the movement will stop and the best drawing will be achieved. The repulsive force,fr, exists between any different two vertices vi and vj. fr is inversely proportional to the distance between vi and vj. The attractive force, fa, just exists between linked vertices. fa is proportional to the square of the distance:(3)fr=k2du2k-d,fa=d2k,where u(x)=1,ifx>0;0,otherwise.In (3), k is optimal length [24], or natural spring length [33]. It is calculated by k=Carea/V. The constant C is found experimentally and area restricts the field of moving vertices. And d is the distance between vertices vi and vj.Then combined force on a vertexvi and the total energy of the system are given in (4) and (5), respectively.(4)fi,k=∑i≠j-k2cj-ci2cj-ci+∑i↔jcj-cikcj-ci,wherei↔j means vertices vi and vj are neighboring vertices.(5)Energysysk=∑i∈Vf2i,k.In [17], the author has proved theoretically that changing of parameters k does not actually change the minimal energy drawing of the graph but merely scales the drawing from a mathematical point of view.


## 2.1. Related Graph Definitions

In order to facilitate the descriptions in this paper, related definitions of graph theory are introduced here. A graph may be either directed or undirected. A digraph is a pairD={V,E}, where V represents the set of vertices and E the set of directed edges. Aleaf vertex  is a vertex with degree one. Auniversal vertex  is a vertex that is adjacent to every other vertex in the graph. Astar vertex  is a vertex that is adjacent to severalleaf vertices. Astar vertex  and its adjacent leaf vertices can derive astar-subgraph. If a closed path is with no repetitions of vertices and edges, then the path is called a directedcycle. As the two notions,leaf vertices  and subgraphs, are involved in this work, related definitions are also introduced as follows.Definition 1 (see [39]).
LetD={V,E} be a simple graph. The subgraph induced by a subset W of the vertex set V is the graph {W,F}, where the edge set F contains an edge in E if and only if both endpoints of this edge are in W.Definition 2.
LetD={V,E} be a digraph, with V the set of vertices and E the set of edges, where V={v1,v2,…,vn-1,vn}. The number ofleaf vertices associated with vi is denoted by leaf_number(i).Definition 3.
LetD={V,E} be a digraph. The number ofleaf vertices in D is denoted by nleaf(D). Then the proportion ofleaf vertices in D is denoted by pleaf(D), which is calculated by(1)pleafD=nleafDV.


## 2.2. HL-DPC Algorithms [23]

One of the purposes of this paper is to draw cycles as symmetric as possible. The precondition of drawing cycles is finding cycles. In [23], HL-DPC algorithm is proposed to find cycles from strongly connected components (SCCs) with 3 vertices at least which is proven to contain cycles certainly. The main idea of the HL-DPC algorithm is to conduct heuristic DFS to a given SCC which is found from a digraph via Tarjan’s algorithm [40]. There are two pieces of heuristic information to decide whether DFS is forward or backward and control the process of DFS on choosing vertices. A stack S is used for recording the vertices visited by heuristic DFS. If a vertex u belonging to S is visited again but the size of S does not meet the experimental threshold, then u would be removed from S. DFS continues to run from the top vertex in S until visiting vertex is visited again and the size of S meets an experimental threshold. Then a cycle is asserted to be found.The two pieces of heuristic information used in HL-DPC algorithm are introduced as follows. Firstly, a direction parameter is introduced to decide whether DFS is forward or backward.Definition 4 (see [23]).
LetD={V,E} be a digraph. Dscc3={Vscc3,Escc3} is a SCC of D with 3 vertices at least. A direction parameter, ratio, is defined by(2)ratio=∏v∈Vscc3Sdeg+v∏v∈Vscc3Sdeg-v.In (2), Sdeg+(v) and Sdeg-(v) are the number of outgoing edges and incoming edges adjacent to vertex v in the SCC, respectively. Then according to the value of ratio, the direction of DFS can be determined by the corresponding formula in [23]. The experiments in [23] also show that the proposed parameter is necessary and useful.Secondly, DFS will visit neighbor vertex with maximumSdeg+(v) and Sdeg-(v) of visited vertex v. The second heuristic information is also proved to be necessary by corresponding experiments in [23].


## 2.3. FR Algorithm [24]

In this paper, we take a standard force-directed algorithm as a part of our methods. It is necessary to review it briefly. Force-directed algorithms model the graph drawing problem by calculating attractive and repulsive forces between vertices. Optimal drawing would be achieved when the energy of system descends to the minimum. Force-directed algorithms can produce appealing drawings for most graphs and display isomorphic and symmetric substructures. Although there is a drawback of high runtime compared to other graph drawing algorithms, force-directed algorithms still dominate the algorithms of graph drawing. FR algorithm which requiresO(n2) time is one of the most famous force-directed algorithms. It was proposed by Fruchterman and Reingold [24] based on the famous Eades’s spring force-directed [26] model. Although FR is a very simple algorithm, it provides quite excellent results. Even today, after years of its creation, it is still one of the most popular algorithms for graph drawing. In this work, FR algorithm will be used to calculate repulsive and attractive forces between vertices.Fruchterman and Reingold represented the graph drawing problem by a system of electrically charged vertices connected by some springs. There are only two criteria demanded for a good graph drawing.(1) Connected vertices should be close to each other. (2) Vertices should not be drawn too close to each other.Certainly FR model also moves vertices according to the attractive and repulsive forces. When the total energy of the system decreases to a minimum, the movement will stop and the best drawing will be achieved. The repulsive force,fr, exists between any different two vertices vi and vj. fr is inversely proportional to the distance between vi and vj. The attractive force, fa, just exists between linked vertices. fa is proportional to the square of the distance:(3)fr=k2du2k-d,fa=d2k,where u(x)=1,ifx>0;0,otherwise.In (3), k is optimal length [24], or natural spring length [33]. It is calculated by k=Carea/V. The constant C is found experimentally and area restricts the field of moving vertices. And d is the distance between vertices vi and vj.Then combined force on a vertexvi and the total energy of the system are given in (4) and (5), respectively.(4)fi,k=∑i≠j-k2cj-ci2cj-ci+∑i↔jcj-cikcj-ci,wherei↔j means vertices vi and vj are neighboring vertices.(5)Energysysk=∑i∈Vf2i,k.In [17], the author has proved theoretically that changing of parameters k does not actually change the minimal energy drawing of the graph but merely scales the drawing from a mathematical point of view.


## 3. A Symmetric Metric for Graph Drawing

In this section, a new objective symmetric metric based on vertex coordinate calculation is proposed to measure the extent to which the drawings produced by graph drawing algorithms can be considered symmetrical.Definition 5.
LetD={V,E} be a digraph, with V the set of vertices and E the set of edges, where V={v1,v2,…,vn-1,vn}. In the drawing of D, the coordinate of vertex vi(i=1,2,…,n) is denoted as (vix,viy). Vertex vi and its neighbors Ni={vi1,vi2,…,vim} can be grouped into a subset Wi={vi,vi1,vi2,…,vim} of V. The barycenter of Wi is denoted as G(Wi). The center of minimum circumscribed circle, min-circumcenter, of Wi is denoted as OMCC(Wi). The radius of minimum circumscribed circle, min-circumradius, of Wi is denoted as rMCC(Wi). Locally, the metric σ(i) in (6) is used to measure the extent to which the drawing of Wi related to vertex vi can be considered symmetrical. Note that smaller σ(i) is better. Globally, the metrics Eσ and Dσ in (7) are used to measure the extent to which overall drawing can be considered symmetrical. Note that Eσ is the primary metric in contrast to Dσ. For Eσ and Dσ, the smaller values are better.(6)σi=disGWi,OMCCWirMCCWi.(7)Eσ=1n∑i=1nσi,Dσ=1n∑i=1nEσ-σi2.In (6), disa,b is the Euclidean distance between a and b which is easy to be obtained. Firstly, it is needed to explain how the minimum circumscribed circle of a set of several vertices can be determined. The convex hull of the drawing of Wi is found by Graham’s scan [25]. Then three vertices on convex hull are chosen via exhaustive search to determine the minimum circumscribed circle of the drawing of Wi. For the three chosen vertices A,B,C, the coordinate of min-circumcenter (OMCC(Wi)x,OMCC(Wi)y) and the size of min-circumradius rMCC(Wi) of Wi can be determined by(8)Δ=2Ax-BxCy-By-2Ay-ByCx-Bx,OMCCWix=Cy-ByAx2+Ay2-Bx2-By2-Ay-ByCx2+Cy2-Bx2-By2Δ,OMCCWiy=Ax-BxCx2+Cy2-Bx2-By2-Cx-BxAx2+Ay2-Bx2-By2Δ,rMCCWi=disA,OMCCWi.Example6 is designed to explain how (6) and (7) measure the symmetry of every vertex and overall drawing.Example 6.
Given a digraphD={V,E}, with V={v1,v2,…,v7} and E={(v1,v2), (v1,v3),…,(v1,v7)}, two different drawings of D are shown in Figure 1. And coordinates of vertices in the drawings are also shown.
For vertexv1, its neighbors N1={v2,v3,…,v7} and v1 itself can be grouped into a subset W1={v1,v2,…,v7} of V. In drawing 1 (Figure 1(a)) of D, one can use σ(1) computed by (6) to measure the symmetry of vertex v1. In fact, the computing of σ(1) is based on the computing of barycenter and the determination of the minimum circumscribed circles. The two operations for drawings 1 and 2 are also shown in Figure 2.
The barycenter ofWi, (G(W1)x,G(W1)y), is calculated by(9)GW1x=1+0.25+0.5+0.875+1+1.25+1.57=0.911,GW1y=0.4+0.2+0.4+0.8+1+0.8+0.47=0.571.Figure 1
Two different drawings of digraphD.
(a)
Drawing 1 (b)
Drawing 2Figure 2
Determining the minimum circumscribed circle of the vertex set ofW1 corresponding to vertex v1 in two drawings of D. Firstly, the convex hull (green lines) of W1 is found by using of Graham’s scan [25]. Secondly, three vertices (v2,v5,v7 in drawing 1 and v2,v6,v7 in drawing 2) on the convex hull are chosen via exhaustive search to determine the minimum circumscribed circle (red circle) of W1. It is noted that determining a circle is essentially of determining its center (red dot) and radius. In addition, the barycenter of green dot is also marked there.
(a)
Drawing 1 (b)
Drawing 2By exhaustive search,v2,v5,v7 are chosen to determine the minimum circumscribed circles of Wi. Then according to (8), the coordinate of OMCC(Wi) and the size of rMCC(Wi) are calculated by(10)Δ=1.7,OMCCWix=0.863,OMCCWiy=0.377,rMCCWi=0.638.By (6), one can get σ(1)=0.313. σ(i) (i=2,2,…,n) can also be calculated in a similar way. As vertex vi(i=2,2,…,n) has only one neighbor, the minimum circumscribed circle of Wi is the circle with diameter of the line segment between vi and its only neighbor. Thus for Wi, the coordinate of its min-circumcenter is identical to the coordinate of its barycenter. As a result, σ(2)=σ(3)=σ(4)=σ(5)=σ(6)=σ(7)=0. Finally, one can get that Eσ=4.47E-2 and Dσ=1.2E-2 by (7).In drawing 2 (Figure1(b)) of D, σ(1)=0 because the coordinate of min-circumcenter is identical to the coordinate of barycenter for Wi. Similarly, σ(2)=σ(3)=σ(4)=σ(5)=σ(6)=σ(7)=0. Finally, one can get Eσ=0 and Dσ=0 for drawing 2.The comparison ofEσ indicates that drawing 2 (Figure 1(b)) can be considered more symmetric than drawing 1 (Figure 1(a)). This result is in accord with human intuition.According to Example6, the proposed metric seems to be effective for measuring the symmetry displayed in different drawings. For a drawing, if a metric is used to measure how symmetric the drawing is, then how do the metric values change with drawing’s rotation and scaling up or down? An example of drawing named X is shown in Figure 3(a). Then the rotated and scaled up X are shown in Figures 3(b) and 3(c), respectively. From the viewpoint of human intuitive impression on the three drawings in Figure 3, the values of symmetric metric on them should be identical. By computing, the values of Eσ and Dσ for three drawings in Figure 3 are listed in Table 1. It can be seen that the values of Eσ and Dσ for three drawings are equal. Furthermore, Proposition 7 proves theoretically that the proposed symmetric metric is robust for rotation and scaled change of drawings.Table 1
Symmetric measurement on the three drawings in Figure3 by the proposed metric.
Drawings X Rotated X Scaled up X Eσ 1.45E-1 1.45E-1 1.45E-1  Dσ 2.67E-1 2.67E-1 2.67E-1Figure 3
An example drawing named X (a) and its rotated version (b) and its scaled up version (c).
(a)
Original X (b)
Rotated X (c)
Scaled up XProposition 7.
LetD={V,E} be a digraph and X be a drawing of D. For an arbitrary vertex vi in D, σ(i) (6) is used to measure the extent to which neighbors of vi can be considered to be distributed symmetrically around vi. And Eσ and Dσ (7) are used to measure the extent to which X can be considered symmetrically. Then, (1)
Eσ and Dσ for X would not change if X is scaled up or down.(2)
Eσ and Dσ for X would not change if X is rotated at any angle.Proof.
For arbitrary vertexvi, its coordinate in X is (vix,viy). vi and its neighbors Ni={vi1,vi2,…,vim} can be grouped into a subset Wi={vi,vi1,vi2,…,vim} of V. Then σ(i)=disGWi,OMCCWi/rMCC(Wi). (1)
AfterX is scaled up (k>1) or down (k<1) k times, the coordinate of vi in the scaled X changes to be (k∗vix,k∗viy). By algebraic simplification, the coordinates of all vertices and auxiliary points (barycenter and min-circumcenter) change in the same way. Let us calculate the value of σ′(i) for vi in the scaled X according to (6) and (8). It is straightforward that disG′(Wi),OMCC′(Wi)=k∗disG(Wi),OMCC(Wi) and rMCC′(Wi)=k∗rMCC(Wi). Thus, (11)σ′i=disG′Wi,OMCC′WirMCC′Wi=k∗disGWi,OMCCWik∗rMCCWi=disGWi,OMCCWirMCCWi=σi.This indicates thatσ(i) is robust for scaled drawings. Finally, according to (7), robustness of σ(i) decides the robustness of Eσ and Dσ. In a word, Eσ and Dσ for X would not change if X is scaled up or down.(2)
AfterX is rotated at angle θ, the coordinate of vi in the rotated X changes to be (vix∗cosθ-viy∗sinθ),vix∗sinθ+viy∗cosθ). By algebraic simplification, the coordinates of all vertices and auxiliary points (barycenter and min-circumcenter) change in the same way. Let us calculate the value of σ′′(i) for vi in the rotated X according to (6) and (8). By algebraic simplification again, it can be got that disG′′(Wi),OMCC′′(Wi)=disG(Wi),OMCC(Wi) and rMCC′′(Wi)=rMCC(Wi). Thus, (12)σ′′i=disG′′Wi,OMCC′′WirMCC′′Wi=disGWi,OMCCWirMCCWi=σi.This means thatσ(i) is robust for drawing’s rotation at any angle. Globally, robustness of σ(i) decides the robustness of Eσ and Dσ. In a word, Eσ and Dσ for X would not change if X is rotated at any angle.


## 4. Proposed Approach

In this section, a force-directed algorithm called FDS is proposed to draw digraphs containing cycles and subgraphs symmetrically and conspicuously. The key term of FDS algorithm is “circle” which is the most symmetrical geometric figure and can be eye-catching from overall drawings. Thus FDS algorithm tries to draw cycle vertices and leaf vertices belonging to star-subgraphs as various kinds of circles which can display most of symmetry from the two structures. The basic idea of FDS is as follows: firstly, use HL-DPC algorithm [23] to discover cycles of digraphs, and a cycle drawing algorithm based on circle placement (CD-CP) is proposed as a subalgorithm of FDS. CD-CP algorithm can fix the cycle vertices on equal amount of highlighted circles which provide a fixed scaffolding to overall drawings. Secondly, a standard force-directed algorithm, FR algorithm [24], is taken to deal with non-leaf vertices. Thirdly, a leaf vertices distribution algorithm (LD) is proposed as a subalgorithm of FDS. LD algorithm can distribute leaf vertices evenly around the centers of star-subgraphs, star vertices, so that the drawings of star-subgraphs are symmetrical. The advantages of FDS algorithm on drawing cycles and star-subgraphs symmetrically are mainly from three aspects: (1) CD-CP algorithm can not only distribute cycle as circles but also highlight them so that cycles are displayed symmetrically and conspicuously; (2) the scaffolding strategy is utilized in FDS algorithm for maintaining the symmetry of cycles displayed in overall drawings; (3) LD algorithm can distribute leaf vertices belonging star-subgraphs most symmetrically by cost of few time.


### 4.1. A Cycle Drawing Algorithm Based on Circle Placement (CD-CP)

In Table2, two different drawings of a cycle are listed. By comparing Eσ and Dσ of one drawing with that of another drawing, it is found that the drawing in which four cycle vertices are arranged on a circle displays more symmetry of the cycle and is more appealing than another. Therefore, in this paper, all cycle vertices are fixed on the same amount as circles with cycle edges being highlighted.Table 2
Comparisons ofEσ and Dσ of one drawing with that of another for a cycle.
A random drawing of a cycle Circle drawing of the cycle Cycle drawings  Eσ 4.15E-1 3.33E-1 Dσ 5.92E-2 0Cycles must be detected before displaying. Thus HL-DPC algorithm [23] is used to detect cycles in digraphs. In the next, it should be elaborated how to place cycle vertices on circles and determined what sizes and location of circles are. (1) If there is only one cycle c, vertices belonging to c are placed evenly on a circle centered at coordinate (0,0), e.g., the cycle in Figure 4(a). (2) If there are x (x>1) cycles, x points are selected evenly on the circle centered at coordinate (0,0), then cycle vertices are placed evenly on the circle centered at points selected, e.g., the three cycles in Figure 4(b). It is noteworthy that all of cycle edges are set to be 3 times thick of original size so that cycle can be distinguished easily from overall drawing. According to the above description, CD-CP algorithm is proposed as Algorithm 1.Algorithm 1:A cycle drawing algorithm based on circle placement (CD-CP algorithm).
Input: Cycle sets C  // elements of C are cycles and every cycle consists of several cycle vertices Output: set of coordinates of cycle vertices 1:Set Rc and R empirically;//  R is the radius of circle. 2:If  size(C)=1  then 3:c← only cycle in C;   i←0; 4:for  each v in c  do 5:vx=Rc∗cos(2πi/size(c)); vy=Rc∗sin(2πi/size(c)); 6:i←i+1; 7:end for 8:Size of every cycle edge corresponding to c is set to be 3 times thick of original size; 9:end if 10:if  size(C)>1  then 11:i←0, j←0; 12:for  each c in C  do  //  c is a cycle, denote the center of circle for c by O(c) 13:O(c)x=R∗cos(2πi/size(C)); O(c)y=R∗sin(2πi/size(C)); 14:i←i+1; 15:for  each v in c  do 16:vx=O(c)x+Rc∗cos(2πj/size(c)); vy=O(c)y+Rc∗sin(2πj/size(c)); 17:j←j+1; 18:end for 19:Size of every cycle edge corresponding to c is set to be 3 times thick of original size; 20:end for 21:end ifFigure 4
Placement of cycle vertices on circles.
(a)
To draw a digraph containing 1 cycle by placing cycle vertices on a circle (b)
To draw a digraph containing 3 cycles by placing cycle vertices on 3 circles. Blue circle and dots are aides for understanding the placement


### 4.2. Leaf Vertices Distribution Algorithm (LD)

In order to display star-subgraphs symmetrically, a leaf vertices distribution algorithm (LD) is designed to provide concentric circles on whichleaf vertices belonging to star-subgraphs can be placed. LD algorithm is proposed based on three calculation steps.Given astar vertex  vi connecting severalleaf vertices, then,(1)
count the number ofleaf vertices for vi;(2)
calculate the number ofleaf vertices that can be placed on every layer of concentric circle around vi;(3)
calculate the number of concentric circles needed byvi.The first step is to count the number ofleaf vertices  for  vi:  that is, leaf_number(i).The second step is to calculate the number ofleaf vertices  thatcan be placed on every layer of concentric circle around  vi.At first, three notations are introduced. In a drawing, every vertex is drawn to be a solid circle. The radius of the solid circle ofvi is denoted as rcenter(i). The radius of everyleaf vertex is rleaf. The distance between borders ofleaf vertex and vi is dcircle. Generally, the values of rleaf and rcenter(i) are known already. And dcircle can be set artificially to be equal to rleaf. Consequently, the radius of 1st layer circle is 2rleaf+rcenter(i).In Figure5(a), it can be seen that oneleaf vertex occupies angle of 2α in vi. Then the number ofleaf vertices that can be placed on the 1st layer circle around vi, a1(i), can be calculated by (13a). Analogously, the radius of the 2nd layer circle is rcenter(i)+5rleaf as Figure 5(b). And the number ofleaf vertices that can be placed on 2nd layer circle around vi is a2(i)=π/arcsinrleaf/5rleaf+rcenteri. Thus, it can be induced that al(i) (l is a positive integer)leaf vertices can be placed on thelth circle. And al(i) can be calculated by (13b). Generally, rcenter(i) is an integer multiple of rleaf in practical drawings. Therefore, a more simplified (13c) is proposed to replace (13b).(13a)a1i=2π2α=πarcsinrleaf/2rleaf+rcenteri,(13b)ali=πarcsinrleaf/3l-1rleaf+rcenteri,(13c)ali=a1i+9l-1,where ∙ is the largest integer not greater than ∙.Figure 5
The number ofleaf vertices that can be placed on the 1st and 2nd layer of concentric circles around vi.
(a)
The number ofleaf vertices can be placed on 1st layer circle around vi (b)
The number ofleaf vertices can be placed on 2nd layer circle around viThe third step is to calculate the number of concentric circles needed by  vi.The number of concentric circles needed byvi is actually the maximum value of l, denoted as L. Considering the condition of known a1(i) andleaf_number(i), and the fact that the number ofleaf vertices  on every concentric circle can form an arithmetic sequence, L can be calculated by (14) based on the fact that leaf_number(i) is less than or equal to the total number ofleaf vertices  that can be placed on concentric circles.(14)L=9-2a1i+2a1i-92+72leaf_numberi18,where ⌈∙⌉ is the least integer greater than ∙.It is noteworthy that the number ofleaf vertices needed to be placed on the last layer circle may not be equal to the numberleaf vertices that can be placed on the last layer circle. After placement ofleaf vertices on the (L-1)th layer circle, the number ofleaf vertices not placed yet can be calculated by(15)arest_at_L=leaf_numberi-∑j=1L-1aji=leaf_numberi-L-1a1i-9L-1L-2.These three calculation steps bring up LD algorithm as Algorithm2.Algorithm 2:LD algorithm.
Input:   A digraph D={V,E} Output:  set of coordinates of  leaf vertices 1:for  each v∈V  do 2:leaf_number=0; 3:for  each w∈V  do 4:if  w is neighbor of v and degree(w)=1  then 5:leaf_number=leaf_number+1; 6:end if 7:end for 8:if  leaf_number>0  then 9:i=l=1; 10: Calculate a1 by Eq.(13a), L by Eq.(14) and arest_at_L by Eq.(15); 11:for  each w∈V  do 12:if  w is neighbor of v and w is a leaf vertex  then 13:a=a1+(l-1)∗9; 14:If  i>a  then 15:i=1;l=l+1;a=a+9; 16:end if 17:if  l=L  then 18:a=arest_at_L; 19:end if 20:r=rv+(3l-1)rleaf;//  r: radius of the lth layer concentric circle. rv: radius of v. 21:wx=vx+r∗cos(2πi/a);//  vx and wx: x-coordinates of vertices v and w 22:wy=vy+r∗sin(2πi/a);//  vy and wy: y-coordinates of vertices v and w 23:i=i+1; 24:end if 25:end for 26:end if 27:end for


### 4.3. Proposed FDS Algorithm

The proposed CD-CP and LD algorithms can draw cycles and star-subgraphs symmetrically locally. However, there are probably other vertices which are neither cycle vertices nor leaf vertices in practical datasets. For these vertices, FR [24] algorithm is taken as its good performance on aesthetics balance. Finally, HL-DPC [23], CD-CP, FR, and LD algorithms are integrated into a whole algorithm called FDS which can draw digraphs symmetrically globally.Related definitions and propositions needed for introducing FDS algorithm are given below.Definition 8.
LetD={V,E} be a digraph, with V the set of vertices and E the set of edges. Df={Vf,Ef} is the force-subgraph of D. The mathematical descriptions of Ef and Vf are as (16a) and (16b), respectively. Let pv-force(D) be the proportion of vertices belonging to Df in D and pe-force(D) be the proportion of edges belonging to Df in D. pv-force(D) and pe-force(D) can be calculated by (16c) and (16d), respectively.(16a)Ef=CEe∣e∈E∧dege.s≠1∧dege.t=1∨dege.s=1∧dege.t≠1,(16b)Vf=v∣v∈V∧deg⁡v>1,(16c)pv-forceD=VfV,(16d)pe-forceD=EfE,where deg(∙) is degree of vertex ∙, e.s is source vertex of edge e, and e.t is target vertex of edge e.Proposition 9.
LetD={V,E} be a digraph, with V the set of vertices and E the set of edges. Then pleaf(D)+pv-force(D)=1.Proof.
It is easy to get that|Vf|=|V|-nleaf(D) according to (16b). Then one can also get pleafD=nleafD/V by (1) and pv-force(D)=Vf/V by (16c). Finally, pleaf(D)+pv-force(D)=nleaf(D)/V+Vf/V=nleaf(D)+|Vf|/|V|=|V|/|V|=1.FDS algorithm applies forces only on non-leaf vertices. Note that cycle vertices always hold positions even though they are pulled or pushed by forces as cycle vertices must be non-leaf vertices. Finally, FDS algorithm is shown as Algorithm3.Algorithm 3:FDS algorithm (a force-directed algorithm for drawing digraphs symmetrically).
Input: A digraph D={V,E} Output: set of coordinates of vertices in D. 1:Step1:Run HL-DPC algorithm on D; 2:Step2:Run CD-CP algorithm on found cycles; 3:Step3:Calculate force-subgraph Df from D; 4:Step4:Run FR algorithm on Df; 5:Step5:Run LD algorithm on D;The time complexity of FDS algorithm is contributed by all five steps. For every cycle vertex, its coordinate needs to be calculated only once in Step 2. For every star vertex, its coordinate also needs to be calculated only once in Step 5. The function of Step 3 is to find the force-subgraph according to the vertex degree. Thus, Steps 2, 3, and 5 are linear, and the worst time complexity of them isO(V). According to [23], at best the time complexity of Step 1 (HL-DPC algorithm) would be O(|V|+|E|); at worst it would be O(|V|+|E|+∑i=1|D/DSCC3|Ti(DSCC3)). Ti(DSCC3) is given in (17). In (17), the direction parameter ratio is defined in Definition 4. The time complexity of Step 4 (FR algorithm) would be O(Vf2). Thus, the time complexity of FDS algorithm would be between O(V+E+Vf2) and O(|V|+|E|+Vf2+∑i=1|D/DSCC3|Ti(DSCC3)). For a digraph D, besides the size of D, practical time cost of FDS algorithm is also influenced by three indexes, the proportions of cycle, leaf, and non-leaf vertices.(17)TiDSCC3=∏j=1VSCC3iSdeg+vjifratioi≤0.6orratioi>1.6∏j=1VSCC3iSdeg-vjif0.6<ratioi≤1.6


## 4.1. A Cycle Drawing Algorithm Based on Circle Placement (CD-CP)

In Table2, two different drawings of a cycle are listed. By comparing Eσ and Dσ of one drawing with that of another drawing, it is found that the drawing in which four cycle vertices are arranged on a circle displays more symmetry of the cycle and is more appealing than another. Therefore, in this paper, all cycle vertices are fixed on the same amount as circles with cycle edges being highlighted.Table 2
Comparisons ofEσ and Dσ of one drawing with that of another for a cycle.
A random drawing of a cycle Circle drawing of the cycle Cycle drawings  Eσ 4.15E-1 3.33E-1 Dσ 5.92E-2 0Cycles must be detected before displaying. Thus HL-DPC algorithm [23] is used to detect cycles in digraphs. In the next, it should be elaborated how to place cycle vertices on circles and determined what sizes and location of circles are. (1) If there is only one cycle c, vertices belonging to c are placed evenly on a circle centered at coordinate (0,0), e.g., the cycle in Figure 4(a). (2) If there are x (x>1) cycles, x points are selected evenly on the circle centered at coordinate (0,0), then cycle vertices are placed evenly on the circle centered at points selected, e.g., the three cycles in Figure 4(b). It is noteworthy that all of cycle edges are set to be 3 times thick of original size so that cycle can be distinguished easily from overall drawing. According to the above description, CD-CP algorithm is proposed as Algorithm 1.Algorithm 1:A cycle drawing algorithm based on circle placement (CD-CP algorithm).
Input: Cycle sets C  // elements of C are cycles and every cycle consists of several cycle vertices Output: set of coordinates of cycle vertices 1:Set Rc and R empirically;//  R is the radius of circle. 2:If  size(C)=1  then 3:c← only cycle in C;   i←0; 4:for  each v in c  do 5:vx=Rc∗cos(2πi/size(c)); vy=Rc∗sin(2πi/size(c)); 6:i←i+1; 7:end for 8:Size of every cycle edge corresponding to c is set to be 3 times thick of original size; 9:end if 10:if  size(C)>1  then 11:i←0, j←0; 12:for  each c in C  do  //  c is a cycle, denote the center of circle for c by O(c) 13:O(c)x=R∗cos(2πi/size(C)); O(c)y=R∗sin(2πi/size(C)); 14:i←i+1; 15:for  each v in c  do 16:vx=O(c)x+Rc∗cos(2πj/size(c)); vy=O(c)y+Rc∗sin(2πj/size(c)); 17:j←j+1; 18:end for 19:Size of every cycle edge corresponding to c is set to be 3 times thick of original size; 20:end for 21:end ifFigure 4
Placement of cycle vertices on circles.
(a)
To draw a digraph containing 1 cycle by placing cycle vertices on a circle (b)
To draw a digraph containing 3 cycles by placing cycle vertices on 3 circles. Blue circle and dots are aides for understanding the placement


## 4.2. Leaf Vertices Distribution Algorithm (LD)

In order to display star-subgraphs symmetrically, a leaf vertices distribution algorithm (LD) is designed to provide concentric circles on whichleaf vertices belonging to star-subgraphs can be placed. LD algorithm is proposed based on three calculation steps.Given astar vertex  vi connecting severalleaf vertices, then,(1)
count the number ofleaf vertices for vi;(2)
calculate the number ofleaf vertices that can be placed on every layer of concentric circle around vi;(3)
calculate the number of concentric circles needed byvi.The first step is to count the number ofleaf vertices  for  vi:  that is, leaf_number(i).The second step is to calculate the number ofleaf vertices  thatcan be placed on every layer of concentric circle around  vi.At first, three notations are introduced. In a drawing, every vertex is drawn to be a solid circle. The radius of the solid circle ofvi is denoted as rcenter(i). The radius of everyleaf vertex is rleaf. The distance between borders ofleaf vertex and vi is dcircle. Generally, the values of rleaf and rcenter(i) are known already. And dcircle can be set artificially to be equal to rleaf. Consequently, the radius of 1st layer circle is 2rleaf+rcenter(i).In Figure5(a), it can be seen that oneleaf vertex occupies angle of 2α in vi. Then the number ofleaf vertices that can be placed on the 1st layer circle around vi, a1(i), can be calculated by (13a). Analogously, the radius of the 2nd layer circle is rcenter(i)+5rleaf as Figure 5(b). And the number ofleaf vertices that can be placed on 2nd layer circle around vi is a2(i)=π/arcsinrleaf/5rleaf+rcenteri. Thus, it can be induced that al(i) (l is a positive integer)leaf vertices can be placed on thelth circle. And al(i) can be calculated by (13b). Generally, rcenter(i) is an integer multiple of rleaf in practical drawings. Therefore, a more simplified (13c) is proposed to replace (13b).(13a)a1i=2π2α=πarcsinrleaf/2rleaf+rcenteri,(13b)ali=πarcsinrleaf/3l-1rleaf+rcenteri,(13c)ali=a1i+9l-1,where ∙ is the largest integer not greater than ∙.Figure 5
The number ofleaf vertices that can be placed on the 1st and 2nd layer of concentric circles around vi.
(a)
The number ofleaf vertices can be placed on 1st layer circle around vi (b)
The number ofleaf vertices can be placed on 2nd layer circle around viThe third step is to calculate the number of concentric circles needed by  vi.The number of concentric circles needed byvi is actually the maximum value of l, denoted as L. Considering the condition of known a1(i) andleaf_number(i), and the fact that the number ofleaf vertices  on every concentric circle can form an arithmetic sequence, L can be calculated by (14) based on the fact that leaf_number(i) is less than or equal to the total number ofleaf vertices  that can be placed on concentric circles.(14)L=9-2a1i+2a1i-92+72leaf_numberi18,where ⌈∙⌉ is the least integer greater than ∙.It is noteworthy that the number ofleaf vertices needed to be placed on the last layer circle may not be equal to the numberleaf vertices that can be placed on the last layer circle. After placement ofleaf vertices on the (L-1)th layer circle, the number ofleaf vertices not placed yet can be calculated by(15)arest_at_L=leaf_numberi-∑j=1L-1aji=leaf_numberi-L-1a1i-9L-1L-2.These three calculation steps bring up LD algorithm as Algorithm2.Algorithm 2:LD algorithm.
Input:   A digraph D={V,E} Output:  set of coordinates of  leaf vertices 1:for  each v∈V  do 2:leaf_number=0; 3:for  each w∈V  do 4:if  w is neighbor of v and degree(w)=1  then 5:leaf_number=leaf_number+1; 6:end if 7:end for 8:if  leaf_number>0  then 9:i=l=1; 10: Calculate a1 by Eq.(13a), L by Eq.(14) and arest_at_L by Eq.(15); 11:for  each w∈V  do 12:if  w is neighbor of v and w is a leaf vertex  then 13:a=a1+(l-1)∗9; 14:If  i>a  then 15:i=1;l=l+1;a=a+9; 16:end if 17:if  l=L  then 18:a=arest_at_L; 19:end if 20:r=rv+(3l-1)rleaf;//  r: radius of the lth layer concentric circle. rv: radius of v. 21:wx=vx+r∗cos(2πi/a);//  vx and wx: x-coordinates of vertices v and w 22:wy=vy+r∗sin(2πi/a);//  vy and wy: y-coordinates of vertices v and w 23:i=i+1; 24:end if 25:end for 26:end if 27:end for


## 4.3. Proposed FDS Algorithm

The proposed CD-CP and LD algorithms can draw cycles and star-subgraphs symmetrically locally. However, there are probably other vertices which are neither cycle vertices nor leaf vertices in practical datasets. For these vertices, FR [24] algorithm is taken as its good performance on aesthetics balance. Finally, HL-DPC [23], CD-CP, FR, and LD algorithms are integrated into a whole algorithm called FDS which can draw digraphs symmetrically globally.Related definitions and propositions needed for introducing FDS algorithm are given below.Definition 8.
LetD={V,E} be a digraph, with V the set of vertices and E the set of edges. Df={Vf,Ef} is the force-subgraph of D. The mathematical descriptions of Ef and Vf are as (16a) and (16b), respectively. Let pv-force(D) be the proportion of vertices belonging to Df in D and pe-force(D) be the proportion of edges belonging to Df in D. pv-force(D) and pe-force(D) can be calculated by (16c) and (16d), respectively.(16a)Ef=CEe∣e∈E∧dege.s≠1∧dege.t=1∨dege.s=1∧dege.t≠1,(16b)Vf=v∣v∈V∧deg⁡v>1,(16c)pv-forceD=VfV,(16d)pe-forceD=EfE,where deg(∙) is degree of vertex ∙, e.s is source vertex of edge e, and e.t is target vertex of edge e.Proposition 9.
LetD={V,E} be a digraph, with V the set of vertices and E the set of edges. Then pleaf(D)+pv-force(D)=1.Proof.
It is easy to get that|Vf|=|V|-nleaf(D) according to (16b). Then one can also get pleafD=nleafD/V by (1) and pv-force(D)=Vf/V by (16c). Finally, pleaf(D)+pv-force(D)=nleaf(D)/V+Vf/V=nleaf(D)+|Vf|/|V|=|V|/|V|=1.FDS algorithm applies forces only on non-leaf vertices. Note that cycle vertices always hold positions even though they are pulled or pushed by forces as cycle vertices must be non-leaf vertices. Finally, FDS algorithm is shown as Algorithm3.Algorithm 3:FDS algorithm (a force-directed algorithm for drawing digraphs symmetrically).
Input: A digraph D={V,E} Output: set of coordinates of vertices in D. 1:Step1:Run HL-DPC algorithm on D; 2:Step2:Run CD-CP algorithm on found cycles; 3:Step3:Calculate force-subgraph Df from D; 4:Step4:Run FR algorithm on Df; 5:Step5:Run LD algorithm on D;The time complexity of FDS algorithm is contributed by all five steps. For every cycle vertex, its coordinate needs to be calculated only once in Step 2. For every star vertex, its coordinate also needs to be calculated only once in Step 5. The function of Step 3 is to find the force-subgraph according to the vertex degree. Thus, Steps 2, 3, and 5 are linear, and the worst time complexity of them isO(V). According to [23], at best the time complexity of Step 1 (HL-DPC algorithm) would be O(|V|+|E|); at worst it would be O(|V|+|E|+∑i=1|D/DSCC3|Ti(DSCC3)). Ti(DSCC3) is given in (17). In (17), the direction parameter ratio is defined in Definition 4. The time complexity of Step 4 (FR algorithm) would be O(Vf2). Thus, the time complexity of FDS algorithm would be between O(V+E+Vf2) and O(|V|+|E|+Vf2+∑i=1|D/DSCC3|Ti(DSCC3)). For a digraph D, besides the size of D, practical time cost of FDS algorithm is also influenced by three indexes, the proportions of cycle, leaf, and non-leaf vertices.(17)TiDSCC3=∏j=1VSCC3iSdeg+vjifratioi≤0.6orratioi>1.6∏j=1VSCC3iSdeg-vjif0.6<ratioi≤1.6


## 5. Experimental Results

In total, 26 different relational datasets containing 6-50001 vertices are chosen to test related algorithms. 14 man-made datasets are used to test the proposed FDS algorithm when it is dominated by LD and CD-CP algorithms, respectively. 2 datasets are from the Gephi Chinese Tutorial [41], labeled as GCT; 1 dataset is collected by us in practical network, labeled as collected; 9 datasets are from the University of Florida Sparse Matrix Collection [42], labeled as sociology, biology, citation, sport, genealogy, response, and voting. Details of 26 datasets are listed in Table 3. The relational data used to support the findings of this study have been deposited in the Figshare repository (https://figshare.com/s/3cc5b3449b334aba2461) and are also available from the corresponding author upon request.Table 3
Details of the 26 datasets used for algorithms test.
Datasets type V E Number of Dscc3 p l e a f ( D ) pv-force(D) B Man-made 6 5 0 83.333% 16.667% C Man-made 11 10 0 90.909% 9.091% D Man-made 21 20 0 95.228% 4.772% E Man-made 51 50 0 98.039% 1.961% F Man-made 101 100 0 99.010% 0.990% G Man-made 201 200 0 99.502% 0.498% H Man-made 501 500 0 99.800% 0.200% I Man-made 1001 1000 0 99.900% 0.100% J Man-made 2001 2000 0 99.950% 0.050% K Man-made 5001 5000 0 99.980% 0.020% L Man-made 50001 50000 0 99.998% 0.002% M Man-made 5 7 1 0% 100% N Man-made 15 24 1 20% 80% O Man-made 30 30 3 0% 100% Ooof-email GCT 119 183 2 69.750% 30.250% Twitter07 GCT 2666 2654 0 99.550% 0.450% 1 collected 278 302 0 82.734% 17.266% Stranke94 sociology 10 90 1 0% 100% Cage3 biology 5 19 1 0% 100% Cage4 biology 9 49 1 0% 100% Tina_DisCal sociology 11 41 1 0% 100% GD01_b citation 18 37 1 0% 100% Ragusa18 sociology 23 64 1 13.043% 86.957% football sport 35 118 0 8.571% 91.429% EPA response 4271 8965 10 47.577% 52.423% EVA genealogy 7252 6726 2 87.743% 12.257%All algorithms are implemented in NetBeans IDE 8.0.1, under the Gephi 0.8.2 development kit. The configuration of experiments is operating system, WIN7, CPU, Intel(R) Core(TM) i5-4590 Quad CPU 3.30GHZ, Memory, 4G. In this section, three algorithms are chosen to compare to the FDS algorithm proposed in this paper, which are the classicalO(n2) FR algorithm (FR) [24], the recent O(nlog⁡n) ForceAtlas2 algorithm (FA2) [29], and O(nlog⁡n) multilevel YifanHu algorithm (YFHu) [17].About the parameter settings, firstly, the parameterδ is used in HL-DPC which is a subalgorithm of FDS algorithm. The parameter δ works only if there exists Dscc3 (SCC with 3 vertices at least) in digraphs. For the digraphs in Table 3, only 12 digraphs of them contain Dscc3 so that it is required to set parameter δ for them experimentally. The values of δ for the 12 datasets are listed in Table 4. The role of parameter δ is to provide the threshold for the procedure of heuristic DFS in HL-DPC algorithm. The threshold is calculated by δ×|Vscc3|. If δ is set too large, then the threshold is larger than the number of vertices belonging to the cycle in Dscc3, which would cause that the cycle can not be found. If δ is set too small, then the threshold is smaller than the number of vertices belonging to the cycle in Dscc3, which might cause that the size of the found cycle is smaller than the size of the cycle in Dscc3. In general, we need to set the value of δ for every Dscc3 because it is nearly impossible that there are two Dscc3 that are isomorphic. For example, there are two Dscc3 in the digraph of dataset Ooof-email, and we set δ to be 0.38 for first Dscc3 and 0.7 for second Dscc3. In Table 4, if the value of δ is ∗, that means the value of δ has no impact on finding cycles of corresponding Dscc3. In addition, FDS algorithm proposed in this paper is a force-directed method, and one part of FDS is FR algorithm. Thus some parameters related to force-directed algorithms also should be considered. In this paper, all algorithms are implemented in the software of Gephi 0.8.2. In order to compare FDS algorithm fairly to other algorithms, default parameter settings in Gephi 0.8.2 are used for FA2, YFHu, and FR algorithms. In particular, FDS takes same value of parameter “speed” as that of other two algorithms (FA2 and FR) because “speed” affects the efficiency of these force-directed algorithms.Table 4
Parameter setting ofδ used in HL-DPC algorithm for datasets.
Datasets Number ofDscc3 Parameterδ Number of cycles M 1 ∗ 1 N 1 0.6 1 O 3 ∗, ∗, ∗ 3 Ooof-email 2 0.38, 0.7 2 Stranke94 1 0.91 1 Cage3 1 0.89 1 Cage4 1 0.89 1 Tina_DisCal 1 0.89 1 GD01_b 1 0.35 1 Ragusa18 1 0.75 1 EPA 10 0.9, 0.7, 0.9, 0.7, 0.7, 0.4, ∗, 0.9, 0.4, 0.5 9 EVA 2 0.8, ∗ 116 drawings of 4 datasets (O, Stranke94, Cage3, and Cage4) are listed in Table5, which are produced by FA2, YFHu, FR, and FDS algorithms, respectively. For the 4 datasets, all vertices belong to cycles. Thus the main goal of drawing these 4 datasets is to display cycles symmetrically. The symmetric measurement and time consumption of these 16 drawings are then listed in Table 6. In Table 6, optimal values of Eσ, Dσ, and time are bold conspicuously. According to human perception and the values of Eσ in Table 6, drawings produced by FDS are more symmetrical than those produced by other 3 algorithms. In addition, FDS spends less time than other 3 algorithms. In a word, FDS can produce more symmetrical drawings with less time consumption than other 3 algorithms for these 4 datasets.Table 5
16 drawings produced by FA2, YFHu, FR, and FDS algorithms for 4 datasets (O, Stranke94, Cage3, and Cage4).
Datasets FA2 YFHu FR FDS O Stranke94 Cage3 Cage4Table 6
The symmetric measurement and time consumption (second) of 16 drawings in Table5.
Datasets FA2 YFHu FR FDS Eσ O 7.89E-1 8.50E-1 8.56E-1 7.73E-1 Stranke94 4.61E-2 2.51E-2 1.17E-1 0 Cage3 3.24E-1 6.10E-1 3.17E-1 3.16E-1 Cage4 4.61E-1 3.80E-1 1.91 2.86E-1  Dσ O 3.21E-2 1.27E-2 7.18E-2 2.41E-15 Stranke94 4.81E-35 1.20E-35 1.93E-34 0 Cage3 2.60E-3 2.15E-1 4.05E-2 4.17E-2 Cage4 4.32E-2 6.02E-2 1.87E1 1.74E-2  time O 1.4 8.1E-2 1.6E-1 3.8E-3 Stranke94 1.8E-1 1.5E-1 1.3E-1 9.9E-3 Cage3 1.1E-1 3.4E-2 1.2E-1 1.7E-3 Cage4 1.2E-1 7.9E-2 1.2E-1 1.0E-312 datasets (Twitter07 and B, C,…, L) are also used to test these four algorithms. There are only two kinds of vertices,leaf andstar vertices, in these 12 datasets. Thus the main goal of drawing these 12 datasets is to display star-subgraphs symmetrically. 4 drawings of the typical dataset Twitter07 are listed in Table 7, which are produced by FA2, YFHu, FR, and FDS algorithms, respectively. The symmetric measurement and time consumption of these 4 drawings are listed in Table 7. In Table 7, optimal values of Eσ, Dσ, and time are bold conspicuously. No matter from the viewpoint of human intuition or according to the values of Eσ, it can be seen that the drawing produced by FDS is most symmetrical. FDS spent so few time that can even be ignored.Table 7
4 drawings produced by FA2, YFHu, FR, and FDS algorithms for dataset Twitter07. In addition, the symmetric measurement and time consumption (second) of them are also listed.
Dataset FA2 YFHu FR FDS Twitter07  Eσ 3.65E-3 3.58E-3 5.06E-2 8.43E-7 Dσ 7.67E-3 4.64E-4 5.61 1.90E-5 time 6E1 1.3E1 7.4E1 1.6E-1Except for dataset Twitter07, changes ofEσ and time consumption of 43 drawings for other 11 datasets (B, C, …, L) are shown in Figures 6(a) and 6(b), respectively. It can be seen that the drawings produced by FDS show their undoubted advantages on displaying symmetry (Eσ) and efficiency (time). In a word, FDS can produce very symmetrical drawings within much less time than other 3 algorithms when datasets contain large proportion ofleaf vertices.Figure 6
Changes ofEσ and time consumption of four algorithms on producing 43 drawings. Notes. (1) It is ‘43’ not ‘44’ because FR can not draw dataset L within bearable time. (2) In order to make Figures 6(a) and 6(b) more readable, the logarithm values of them are taken. Thus x axis stands for lg|V| and y axis lg(time) and lg(Eσ). (3)  Eσ of drawings produced by FDS for four datasets (B,C,D E) are invisible in Figure 6(a) because the values of them are 0.
(a)
Changes ofEσ (b)
Changes of time consumptionUnlike dataset Twitter07 drawn in Table7 and datasets B-L involved in Figure 6, in many practical datasets, not all vertices belong to star-subgraphs. For dataset 1, for example, forces on many vertices have to be calculated although it contains many leaf vertices. 4 drawings produced by FA2, YFHu, FR, and FDS algorithms for dataset 1 are listed in Table 8. The symmetric measurement and time consumption of them are also listed. It can be seen that FDS provided best drawing for dataset 1 within shortest time. Compared to the drawing produced by FDS, the drawings produced by FA2 and YFHu did not display relationships between non-leaf vertices clearly enough although they displayed star-subgraphs symmetrically. And in the drawing produced by FR, star-subgraphs take up oversized area although relationships between vertices are displayed clearly.Table 8
4 drawings produced by FA2, YFHu, FR, and FDS algorithms for dataset 1. In addition, the symmetric measurement and time consumption (second) of them are also listed.
Dataset FA2 YFHu FR FDS 1  Eσ 1.76E-1 3.01E-1 2.18E-1 1.00E-1 Dσ 1.19 3.17 1.26 8.81E-2 time 7.7 7.4E-1 6.8E1 3.4E-1In datasets M, Tina_DisCal, GD01_b, and Ragusa18, there are only a few vertices to which attractive and repulsive forces need to be calculated besides cycle vertices. Their drawings produced by the 4 algorithms are listed in Table9. The symmetric measurement and time spent of the 16 drawings are listed in Table 10. It can be seen that the drawings produced by FDS have displayed cycles conspicuously and symmetrically. In addition, FDS algorithm provides performance comparable to O(nlog⁡n) YFHu algorithm [17] according to time consumption listed in Table 10.Table 9
16 drawings produced by FA2, YFHu, FR, and FDS algorithms for datasets M, Tina_DisCal, GD01_b, and Ragusa18.
Datasets FA2 YFHu FR FDS M Tina_DisCal GD01_b Ragusa18Table 10
The symmetric measurement and time consumption (second) of 16 drawings in Table9.
Datasets FA2 YFHu FR FDS Eσ M 2.28E-1 8.50E-1 2.94E-1 2.00E-1 Tina_DisCal 4.34E-1 1.04 1.17E-1 4.08E-1 GD01_b 8.70E-1 5.37 7.80E-1 7.45E-1 Ragusa18 5.79E-1 5.74E-1 5.14E-1 5.00E-1  Dσ M 1.70E-2 7.47E-2 4.28E-2 1.67E-2 Tina_DisCal 1.17E-1 6.31E-1 1.53E-1 7.81E-2 GD01_b 5.92E-1 1.28E2 9.11E-2 3.34E-1 Ragusa18 2.10E-1 4.82E-1 7.81E-2 2.77E-1  time M 7.9E-2 2.7E-2 7.9E-2 6.2E-2 Tina_DisCal 1.6E-1 2.5E-2 1.7E-1 1.1E-1 GD01_b 4E-1 1.1E-1 1.4E-1 1.1E-1 Ragusa18 1.8E-1 1.6E-1 1.7E-1 1.5E-1In datasets N, Ooof-email, EPA, and EVA, there are both cycles and star-subgraphs. 16 drawings produced by 4 algorithms for the 4 datasets are listed in Table11. The symmetric measurement and time spent of them are listed in Table 12. It can be seen that cycles in the 4 datasets are drawn symmetrically and conspicuously by FDS. As the directed edges are displayed as straight line, thus cycles are displayed as regular polygons. For example, there are two cycles in dataset Ooof-email and one cycle in dataset EVA, which are displayed as the regular triangle, the regular heptagon, and the square in corresponding drawings of Table 11. Compared to other 3 algorithms, star-subgraphs in the 4 datasets are drawn symmetrically by FDS with taking moderate-size area. The values of Eσ listed in Table 12 also show the advantage of FDS on display of symmetry. According to time consumption recorded in Table 12, FDS can produce symmetrical drawings with taking comparable time to YFHu algorithm.Table 11
16 drawings produced by FA2, YFHu, FR, and FDS algorithms for datasets N, Ooof-email, EPA, and EVA.
Datasets FA2 YFHu FR FDS N Ooof-email EPA EVATable 12
The symmetric measurement and time consumption (second) of 16 drawings in Table11.
Datasets FA2 YFHu FR FDS Eσ N 2.87E-1 3.97E-1 2.62E-1 2.61E-1 Ooof-email 5.18E-1 1.45E-1 3.10E-1 1.15E-1 EPA 8.33E-1 9.03E-1 6.30E-1 6.00E-1 EVA 5.68E-1 6.32E-1 4.05E-1 2.26E-1  Dσ N 1.32E-1 3.95E-1 5.84E-2 5.45E-2 Ooof-email 1.79E1 2.67E-1 2.69 1.73E-1 EPA 2.87E1 2.75E2 5.77 1.07E1 EVA 6.93E1 7.12E2 1.24E2 7.82  time N 6.9E-1 7.6E-2 1.1E-1 8.7E-2 Ooof-email 3.5E-1 1.8E-1 7.6 1.1E-1 EPA 2.6E2 7E1 5.3E2 7.4E1 EVA 4.2E2 1.5E2 1.4E3 1.4E2There may be a concern that FDS algorithm would force nonsymmetric digraphs into symmetric drawings. The experiments on dataset football (Table13) can be used to clarify it. There is neither cycles nor star-subgraphs in dataset football so no much symmetry is needed to be drawn. In contrast to earlier experiments, it is the drawing produced by FR not the drawing produced by FDS which achieves the best value of Eσ. Furthermore, the drawing produced by FDS spends least time maybe because there are 3 leaf vertices on which FDS does not have to calculate forces.Table 13
4 drawings produced by FA2, YFHu, FR, and FDS algorithms for dataset football. In addition, the symmetric measurement and time consumption (second) of them are also listed.
Dataset FA2 YFHu FR FDS football  Eσ 5.64E-1 6.70E-1 4.56E-1 4.62E-1 Dσ 5.64E-1 8.22E-1 3.00E-1 2.38E-1 time 3.9E-1 2.2E-1 1.3E-1 8.8E-2Furthermore, the comparisons of time consumption of these 4 algorithms on 12 practical datasets (Cage3, Cage4, Stranke94, Tina_DisCal, GD01_b, Ragusa18, football, Ooof-email, 1, Twitter07, EPA, and EVA) are also shown in Figure7. It can be seen that FDS (blue line) provides performance comparable to YFHu (cyan line) algorithm with time complexity O(nlog⁡n).Figure 7
Comparison of time consumption by 4 algorithms on 12 practical datasets.


## 6. Conclusion and Future Work

In this paper, an objective symmetric metric is proposed based on vertex coordinate calculation to measure the extent to which drawings can be considered symmetric. The results of measurement by the proposed metric are consistent with human intuition. In addition, the metric can measure symmetries rapidly because it does not involve automorphisms which is computational hardly. Furthermore, the metric is proven theoretically and experimentally to be robust for rotation and scaled change of drawings. And the robustness conforms to human perception of symmetry.In order to display star-subgraphs and cycles symmetrically, a force-directed algorithm called FDS is proposed. The ability of FDS algorithm to display symmetry is validated by several groups of experimental tests. FDS algorithm’s time consumption is comparable to YFHu algorithm with time complexityO(nlog⁡n). In some special datasets of which displaying of star-subgraphs is main goal, FDS spends much less time than YFHu algorithm. Note that FDS algorithm can only perform its advantage to the digraphs containing star-subgraphs and cycles because FDS algorithm is committed to display the symmetry of star-subgraphs and cycles in drawings. If one applies FDS algorithm to the digraphs which do not contain star-subgraphs and cycles, FDS algorithm would degenerate into FR algorithm without negative impact, which means FDS algorithm would not force nonsymmetric digraphs into symmetric drawings. Corresponding experimental results also verified this conclusion. Thus, the applicable conditions of FDS algorithm are the existence of star-subgraphs or cycles in digraphs.In future, we may try to use other methods (e.g., distribution entropy) to construct another objective metric on symmetry. Although the FDS algorithm proposed in this paper only focus on drawing two structures, cycles and star-subgraphs, symmetrically, FDS algorithm has impossible impact. It can provide reference and guidance for designing other similar methods for drawing other graph structures, having inherent symmetry, symmetrically. Besides, it should be noted that FR algorithm is used in FDS algorithm because its good performance on aesthetics balance, though it requiresO(n2) calculations. One may speed up FDS algorithm by replacing FR with other methods without sacrifice of aesthetics.



---

*Source: 6208509-2018-11-19.xml*