# Simple Paths and Cycles of Directed Graph for Stock Trading Network Based on STP

Authors: Xiaolong Liu; Li Ma
Journal: Journal of Mathematics
 (2022)

---

## Abstract

The stock trading relationship of buyers and sellers in the stock market can be characterized by a directed graph. It is an important way to study stock trading network through simple directed paths and cycles. In the present paper, we establish a seeking model of simple directed paths and cycles, and obtain some necessary and sufficient conditions for simple directed path and cycle in the directed graph. The algorithms of finding simple directed path and cycle of any specified length are given. The main approach we used is the semi-tensor product of matrices, which can reduce the search space. An illustrative example is given to show that the theoretical results and algorithms are effective.


---

## Body

## 1. Introduction and Preliminaries

Complex systems are composed of multiple interacting components, and such systems are ubiquitous in social life, such as power grids, social networks, economic organization systems, and so on. Stock market, as a kind of complex system, is an important component in financial system, such as 3000 stocks affect each other and interact with the other in China’s A stock market. It is obvious to study the stock market from the perspective of complex network. The complex network is mathematically processed to form a graph [1, 2]. Although networks are everywhere, any network can be described by graph theory, such as the network of relationships, for example, traffic flow and pipeline transportation are related to the directed graph.An NP-hard problem of graph theory is finding a simple path and cycle [3]. For simple path and cycle finding, an iterative algorithm based on variable adjacency matrix is illustrated in [4]. An improved adjacency matrix is obtained and a modified iteration rule is further given in [5], which develops the calculation speed. Furthermore, an adjacency matrix power algorithm is obtained by using Warshall’s theorem [6] to exhibit the simple path. An backtrack algorithm is presented for listing the whole simple paths in a directed graph [7] and listing the whole cycles in an undirected graph [8]. The search space algorithms are proposed in [9] for looking for every simple cycle of a planar graph. A new algorithm is developed to list approximately the cycle in an undirected graph on the basis of Compute Unified Device Architecture [10]. A new method called semi-tensor product (STP) of matrices is used to find a simple path and simple cycle in the undirected graph [11].In this paper, we investigate the simple directed path and simple directed cycle in directed graph by STP method. STP was first proposed in [12, 13], which is a generalization of the usual matrix multiplication. It is successfully and maturely applied to Boolean control networks expressed as a discrete algebraic system [13–16], and is further applied to a larger range, such as algebra [17], physics [18], and graph theory [19, 20]. The main contribution of the present paper is as follows: (i) we look for the simple directed paths and cycles by STP method after modeling the stock trading network as a directed graph, which has the mathematical formulation advantage by comparing the existing methods of finding the simple directed path and cycle. (ii) A new algorithm is derived to list the simple directed path and simple directed cycle in the directed graph, which can reduce the search space and is confirmed by an example.The rest of this paper is organized as follows. The modeling of stock trading relationship and the analysis of finding simple directed path and cycle by STP method are given in Section2. In Section 3, a new algorithm is illustrated based on the results in Section 2, and an illustrative example is presented to verify the effectiveness of the theoretical results and algorithms.


## 2. Modeling and Analysis

In this section, we introduce the modeling of stock trading relationship and investigate the simple directed path and cycle of the directed graph by using STP method.For stock trading, the typical method is to regard every trader in the stock market as a node and the trading relationship between two investors as an edge. If there is no edge connection between two nodes, then there is no trade between the corresponding traders. In this network, the traders form the node set of a graph, and the trading relationships among all the investors form the edge set of a graph. Since there are buyers and sellers in stock trading, the trading relationship is directional. Therefore, the stock trading network can be characterized as a directed graph by assembling nodes and edges.Consider a graphG=V,E with a vertex (node) set V=v1,v2,⋯,vn and an edge set E⊂V×V. A graph G is called a directed graph if each edge of V, denoted by eij=vi,vj, is an ordered pair of two vertices. In a directed graph G, a directed path consists of the ordered edges ei1i2,ei2i3,⋯. A directed cycle is a directed path with some first vertex and last vertex. Simple directed path (cycle) refers to a path (cycle) with distinct vertices. The k-simple directed path (cycle) is a simple directed path (cycle) with k vertices, for example, v1⟶v2⟶v4⟶v5 and v1⟶v2⟶v4⟶v1 are 4-simple directed path and 3-simple directed cycle in Figure 1, respectively.Figure 1
The 4-simple directed pathv1⟶v2⟶v4⟶v5 and 3-simple directed cycle v1⟶v2⟶v4⟶v1 in a directed graph.For the vertexvi, the neighbor vertex set Ni is given by
(1)Ni=vj∣eij=vi,vj∈E.Then the adjacency matrixA=aij of G is described as
(2)aij=1,vj∈Ni,0,vj∉Ni.For the vertex subsetS⊆V with S=vi1,vi2,⋯,vik,i1,i2,⋯,ik∈1,2,⋯,n, the characteristic logical vector of S is given as VS=x1,x2,⋯,xn, where
(3)xi=1,vi∈S,0,vi∉S.Then we have the following results.Theorem 1.
Assume thatS⊆V, S=vi1,vi2,⋯,vik,k⩾5. Then the directed subgraph GS induced by vertex set S is a k-simple directed path if and only if the following assumptions hold.
(i)
One element of the matrixBS is 0 and the other elements are 1, where BS is given by(4)BS=bSi1,bSi2,⋯,bSik,bSim=∑j=1naimjximxj,m=1,2,⋯,k.(ii)
Ifaps=aqt=1 for p≠q with p,q,s,t∈1,2,⋯,k, then s≠t.(iii)
The subsetS¯=vj1,vj2,⋯,vjl⊂S,3⩽l⩽k−2 satisfies(5)LS¯=∑i=1n∑j=1naijx¯ix¯j⩽l−1,where
(6)x¯i=1,vi∈S¯,0,vi∉S¯.Proof (Necessity).
IfGS is a k-simple directed path, then the connection relationship of vertices and edges in GS can be described in Figure 2.Figure 2
The connection relationship of 6-simple directed path.In the directed graph in Figure2, we find that the end vertex has no adjacent vertex and the remaining vertices have one adjacent vertex in set S. Then, one element of S satisfies ∑j=1naimjximxj=0 and the other elements of S satisfy ∑j=1naimjximxj=1. That is to say, one element of the matrix BS is 0 and the other elements are 1.Assume thataps=aqt=1 for p≠q with p,q,s,t∈1,2,⋯,k. Suppose s=t, then it contradicts the definition of a simple directed path, and so we have s≠t.For any subsetS¯=vj1,vj2,⋯,vjl,3⩽l⩽k−2 with l elements, it is obvious that
(7)LS¯=∑i=1n∑j=1naijx¯ix¯j⩽l−1.(Sufficiency) If one element of the matrixBS is 0 and the remaining elements are 1, then one element of S meets ∑j=1naimjximxj=0, and k−1 elements of S meet ∑j=1naimjximxj=1. Thus, one vertex of S has no adjacent vertex described by type I, and the remaining vertices of S have one adjacent vertex described by type II (see Figure 3). Hence, the vertex of type I is the end vertex in the directed graph.Figure 3
A directed graph with vertices of type I and type II.In what follows, we prove that all vertices of type II can be described in Figure3, which shows that GS is a k-simple directed path.Suppose, there exist some vertices with type II not described in Figure3. Then, either there are two vertices satisfying aps=aqs=1 for p≠q, or there is a subset S¯=vj1,vj2,⋯,vjl,3⩽l⩽k−2 such that
(8)LS¯=∑i=1n∑j=1naijx¯ix¯j=l.The above results have contradiction with conditions (ii) and (iii). Therefore, all vertices with type II are described in Figure3.Remark 2.
If3⩽k<5, then GS is a k-simple directed path if and only if S satisfies conditions (i) and (ii) in Theorem 1.Corollary 3.
Assume thatS⊆V, S=vi1,vi2,⋯,vik,k⩾6. Then the directed subgraph GS induced by vertex set S is a k-simple directed cycle if and only if the following assumptions hold.
(i)
bSim=∑j=1naimjximxj=1,m=1,2,⋯,k.(ii)
Ifaps=aqt=1 for p≠q with p,q,s,t∈1,2,⋯,k, then s≠t.(iii)
The subsetS¯=vj1,vj2,⋯,vjl⊂S,3⩽l⩽k−3 satisfies(9)LS¯=∑i=1n∑j=1naijx¯ix¯j⩽l−1,where
(10)x¯i=1,vi∈S¯,0,vi∉S¯.Remark 4.
If3⩽k<6, then GS is the k-simple directed cycle if and only if S satisfies conditions (i) and (ii) of Corollary 3.
For further discussion, the structure matrices for the Boolean operators are given as follows (see [19]). The structure matrices of conjunction operator and dummy operator are Mc=δ21222 and Ed=δ21212, respectively.Proposition 5.
Eduv=v holds for logical variables u,v∈Δ2.Proposition 6.
Wm,nXY=YX,Wn,mYX=XY, where X∈ℝm, Y∈ℝn, and the element of the swap matrix Wm,n, denoted by wI,Ji,j, is given by
(11)wI,Ji,j=1,I=iandJ=j,0,otherwise.Theorem 7.
Assume thatS=vi1,vi2,⋯,vik⊆V and YS=⋉i=1nyi=δ2ns with yi≔xi,1−xi. If GS is a k-simple directed path, then the sth component of the first row in matrix TS is k−1, where
(12)TS=∑i=1n∑j=1naijTij,Tij=Tji=McEdn−2W2j,2n−jW2i,2j−i−1.Proof.
WhenGS is the k-simple directed path, we have
(13)∑i=1n∑j=1naijxixj=k−1.
Due toxixj=xjxi, without loss of generality, in this paper we can assume that i<j. From Propositions 5 and 6, we have
(14)yiyj=Edn−2yj+1⋯ynyi+1⋯yj−1y1⋯yi−1yiyj=Edn−2W2j,2n−jyi+1⋯yj−1y1⋯yi−1yiyjyj+1⋯yn=Edn−2W2j,2n−jW2j,2n−jW2i,2j−i−1y1⋯yi−1yiyi+1⋯yj−1yjyj+1⋯yn=Edn−2W2j,2n−jW2j,2n−jW2i,2j−i−1YS.
From (14), we obtain
(15)xixj=xi∧xj=JMcyiyj=JMcEdn−2W2j,2n−jW2j,2n−jW2i,2j−i−1YS,
whereJ=1,0. Thus, it follows from (15) that
(16)k−1=∑i=1n∑j=1naijxixj=∑i=1n∑j=1naijJMcEdn−2W2j,2n−jW2j,2n−jW2i,2j−i−1YS=JTSYS.
It follows fromYS=δ2ns that the sth component of the first row of matrix TS is k−1.Corollary 8.
Assume thatS=vi1,vi2,⋯,vik⊆V and YS=⋉i=1nyi=δ2ns. If GS is a k-simple directed cycle, then the sth component of the first row of matrix TS is k, where
(17)TS=∑i=1n∑j=1naijTij,Tij=Tji=McEdn−2W2j,2n−jW2i,2j−i−1.


## 3. Algorithm and Validity

In this section, we give the algorithm for finding thek-simple directed path (cycle) in the directed graph based on the above section.Step 1.
It is easy to deriveTS by (12). The first row of TS is obtained by using J=1,0, described as β=JTS=b1,b2,⋯,b2n. When bi≠k−1 for all i∈1,2,⋯,2n, there exist no k-simple directed paths and the program is terminated. When bi=k−1 for some i, the position numbers where the element is k−1 are given by c1,c2,⋯,ct.Step 2.
Eachcj,j=1,2,⋯,t corresponds to a YS=δ2ncj. From [13], we know that
(18)S1n=δ21⋯1⏟2n−12⋯2⏟2n−1,S2n=δ21⋯1⏟2n−22⋯2⏟2n−21⋯1⏟2n−22⋯2⏟2n−2,···Snn=δ212⏟2⋯12⏟2⏟2n−1.
Then we obtain(19)yi=SinYS=Sinδ2ncj,i=1,2,⋯,n,Scj=vi∣yi=δ21,1⩽i⩽n.
WhenScj≠k, there is not k-simple directed path, and the program is terminated. Otherwise, only the sets with k vertices are considered.Step 3.
Test whether the above setsScj with k vertices satisfy the condition of Theorem 1. The directed subgraphs that meet the condition of Theorem 1 are all k-simple directed paths.Remark 9.
In combination with Corollary3, the algorithm of looking for all the k-simple directed cycles can be derived in the same way.In what follows, we give an example to verify the validity of algorithm. The given directed graph is shown in Figure4, and the MATLAB software is used to search for the simple directed path and simple directed cycle in the directed graph. An example with 8-simple directed path is given to verify that the algorithm above is efficient and reliable.Figure 4
A directed graph with connection relationship.The adjacency matrix of the directed graph in Figure4 is denoted as
(20)A=010000000000001000100001100010100000001000001001000000000100000010000010000001001000100000100000001001000000000100000000000010010000000000010000.TS is easily obtained according to Step 1 of the above algorithm, and the columns whose element is 7 are denoted by c1,c2,⋯,c345, which are all elements that may form 8-simple directed paths. According to Step 2 of the algorithm, there are only 25 sets Scj with 8 elements. By Step 3, there is only one 8-simple directed path in the complex directed graph, which is shown in Table 1, and there is no 9-simple directed cycle.Table 1
One 8-simple directed path of directed graph in Figure4.
Path number8-simple directed path1v10⟶v4⟶v9⟶v6⟶v11⟶v8⟶v1⟶v2



---

*Source: 5453363-2022-10-06.xml*