Abstract
Stress is a centrality measure determined by the shortest paths passing through the given vertex. Noting that adjacency matrix playing an important role in finding the distance and the number of shortest paths between given pair of vertices, an interesting expression and also an algorithm are presented to find stress using adjacency matrix. The results and algorithm are suitably adopted to obtain betweenness centrality measure. Further results are extended to the cases of Cartesian product of graphs, corona graph and their special cases.
1 Introduction
Centrality measures are among essential tools in network analysis. Depending on the given context, one can quantify the importance of a node or an edge in a network and hence one can identify crucial vertices or edges. In general, one can define centrality measure as a function f which assigns a real value to every vertex v of a graph G. Many important centrality measures such as degree centrality, betweenness centrality, closeness centrality, eigenvector centrality are studied and used in the analysis of various networks. Readers are referred to [Citation1, Citation6, Citation7, Citation12] for the details.
Stress is an important centrality measure introduced by Alfonso Shimbel; see [Citation13]. Stress of a vertex in a graph is the number of shortest paths passing through that vertex. In spite of its significance in the applications (like in understanding responsible protein causing cancer in the protein-signaling network), studying its mathematical properties is not given a considerable attention. The articles [Citation2, Citation8, Citation9] are few among the articles in recent days in which the properties of stress have been studied in the context of different graphs. Rather than counting the number of shortest paths passing through the vertex to find the stress, as done in these references, we consider the adjacency matrix to be an effective tool to compute the stress and present the algorithm for the same. Further, using the adjacency matrices of the graphs G and H, we compute the stress of the vertices in the Cartesian product and the corona graph . In Section 4, we provide algorithms to find the stress of vertices in the graphs using the results discussed in the Section 3.
2 Preliminaries
Throughout this paper, the graphs considered are simple, finite, undirected and connected graphs. The length of a shortest path is called the distance between the vertices u and v, and the same is denoted by or simply , if the graph under discussion is clear. In a path given by , the vertex is called origin and the vertex is terminus, and the vertices are called the internal vertices of the path P. The set of shortest paths between the vertices u and v is denoted by and the set of shortest paths between u and v having w as an interior vertex is denoted by . Further, we denote by and by .
Definition 2.1 (Stress of a vertex, Stress of a graph)
Let G be a graph with . The stress of a vertex v, denoted by , is the number of shortest paths in G having v as an internal vertex. The stress of a graph G, denoted by , is given by .
Every vertex sends information to every other vertex through shortest paths and stress is a centrality measure which measures the ability of a vertex in holding together the communicating vertices. Higher the number of shortest paths passing through a vertex, higher will be its stress. After Alfonso Shimbel introduced this notion of stress, not much theoretical investigation was done in this particular area. But, the articles [Citation10, Citation11, Citation12] are a few evidences in which stress is used in the analysis of some biological networks. In the recent developments (see, [Citation2, Citation8, Citation9]) some important properties of stress are explored. The expressions for the stress of vertices from some standard graphs such as paths, trees, cycles, wheels, complete bipartite etc., are discussed. Among the trees of order n, path graph is seen with maximum stress and star graph with minimum stress. It is found that stress of a block graph is the sum of the stress at the cut vertices. A graph is k-stress regular if stress of each of its vertices is k. Characterization of k-stress regular graphs can also be seen in the literature.
In the current paper we make use of the adjacency matrix of the graph to compute the stress of a vertex. For a graph G with n vertices , the adjacency matrix is an matrix, in which if is adjacent with and otherwise. For the same graph, the distance matrix is the matrix where . Whenever the graph under discussion is clear from the context, we write A and D instead of and , respectively, to denote the adjacency and distance matrices. Now, we introduce a notion of shortest path matrix of graph G as in thefollowing.
Definition 2.2 (Shortest path matrix)
Given a connected graph G, the shortest path matrix of G denoted by is an matrix in which the iith entry is 1 and ijth entry represents the number of shortest paths between and (), i.e., .
The notations and used in the above definition are replaced by N and , respectively, when the graph under discussion is clear from the context. It may be noted that for , we have . Further, writing in the above definition is for our computational convenience (representing the number of paths/walks of length zero from a vertex to itself!).
Other centrality measure which is computationally closer to stress is betweenness centrality measure.
Definition 2.3 (Betweenness Centrality)
Betweenness centrality measure of a vertex , denoted by , is given by (1) (1)
In Section 3, we give an expression for computing betweenness centrality using the properties of adjacency matrix. Then using the same result, in the Section 4, we present an algorithm to compute this measure.
3 Computation of stress using adjacency matrix
Note that by joining any two paths having one common terminus vertex need not result in a shortest path. In fact, a path is a shortest path between u and w if and only if . The following lemma relates the stress of any vertex of graph G with the entries of .
Lemma 3.1.
If G is a connected graph with , then for any vertex (2) (2)
Proof.
For any two vertices , it may be noted that a shortest path will pass through a vertex if and only if (3) (3)
In the above case, any shortest path passing through is obtained by joining a shortest path with a shortest path, and vice versa. In other words, we have one-one correspondence between shortest paths -paths passing through and pairs of shortest and paths. Therefore, if and denotes the number of shortest paths and paths, respectively, then the number of shortest paths between and passing through is given by the product . In other words, we have (4) (4) or simply, . Now by referring to the Definition 2.1, the stress of is given by the sum of the products , where the summation is taken over all pair of vertices satisfying EquationEq. (3)(3) (3) , proving EquationEq. (2)(2) (2) . Hence the lemma. ▪
It is well known that the entries of provide the number of walks of length p between the distinct vertices and the readers are referred to any standard text books like [Citation4]. The following theorem follows immediately.
Theorem 3.2.
If G is a connected graph, then , the distance between and for is the least integer p for which the entry of is nonzero. In such a case, .
In view of the above theorem the shortest path matrix could be redefined as the matrix such that , where p is the least integer for which the entry of is nonzero. Now the following corollary is immediate.
Corollary 3.3.
If G is a graph with the adjacency matrix A, then for any vertex (5) (5) where and p is the least integer for which the ijth entry of is nonzero.
In the following theorem, we present an expression to compute betweeness centrality of a vertex in G using the shortest path matrix of G. The proof is immediate from the definition of betweenness centrality and the EquationEq. (4)(4) (4) .
Theorem 3.4.
If G is a graph with the adjacency matrix A, then for any vertex the betweenness centrality of is given by (6) (6) where and p is the least integer for which the ijth entry of is nonzero.
We next discuss on how the adjacency matrices of the graphs G and H are useful in determining the stress of verticesin .
3.1 Stress of vertices in the Cartesian product
Definition 3.5 (Cartesian product of graphs).
The Cartesian product of two graphs G and H, denoted by , is a graph with vertex set , where two vertices and are adjacent if and or and
It may be noted that in the case of Cartesian product , the corresponding adjacency matrix, distance matrix and shortest path matrix are written by considering the pairs of vertices in the lexicographical ordering as column and row indices. The number of shortest paths between any two vertices and in the Cartesian product is studied in literature [Citation3, Citation5] and given by (7) (7)
For the convenience of the reader, we provide a detailed but independent explanation on computing the number of shortest paths between the vertices of Cartesian product of twographs.
To start with, consider a tridiagonal matrix of the form and the matrices to observe the following:
for all and
The highest power of x in term of is with the coefficient (8) (8)
By taking and for , we observe that generates the Pascal’s triangle
the coefficient of in the binomial expansion of .
Now by considering path graphs and of length and , we observe that the adjacency matrix of the Cartesian product is the block matrix of size given by (10) (10)
Since the vertices of are arranged in the lexicographical ordering, referring to Theorem 3.2, the distance between and is given by the least positive integer k for which th entry of is nonzero. This is possible when appears in block of . From the observations (i)–(iii), we get that k must be and th entry of is the coefficient of in the block and given by (12) (12)
If is the length of a path graph and is the length of a path graph , then referring to EquationEq. (12)(12) (12) we have number of paths between and in the .
Noting that each pair of shortest paths in the factor graphs produce as many number of shortest paths as mentioned in EquationEq. (12)(12) (12) in the Cartesian product, the total number of shortest paths between any two vertices in the Cartesian product is as given in EquationEq. (7)(7) (7) .
In the following theorem, we will present an expression to find the stress of a vertex in the Cartesian product with reference to the details from the factor graphs.
Theorem 3.6.
For any connected graphs G and H, the stress of a vertex in is given by (13) (13)
where the summation is taken over all the pairs of vertices and different from in satisfying and
Proof.
Referring to EquationEq. (3)(3) (3) , note that any vertex denoted by x is an internal vertex in the shortest paths between the vertices and if and only if (14) (14) equivalently, (15) (15)
Now referring to EquationEq. (4)(4) (4) in the Lemma 3.1, when the EquationEqs. (14)(14) (14) and Equation(15)(15) (15) are satisfied, it follows that the product equals to , the number of shortest paths in having x as an internal vertex. By EquationEq. (7)(7) (7) , we have that the number of shortest paths in is given by (16) (16) and the number of shortest paths in is given by (17) (17)
Now, EquationEq. (13)(13) (13) follows by substituting EquationEqs. (16)(16) (16) and Equation(17)(17) (17) in EquationEq. (2)(2) (2) of Lemma 3.1 in the context of . ▪
Since the ladder graph is the Cartesian product of path graphs, the following corollary is immediate from Theorem 3.6.
Theorem 3.7.
If and are two paths of length two and , respectively, then the stress of any vertex in the ladder graph is given by, (18) (18)
Proof.
By symmetry of , we first note that for . So, we shall find the stress of vertex of . Since there exists a unique path between any two pair of vertices from a path, we have for and . Substituting the same in EquationEq. (13)(13) (13) , we get (19) (19) where the summation is extended over all ordered pairs and other than satisfying (20) (20)
and (21) (21)
The summation in EquationEq. (19)(19) (19) could be split into the following three cases to satisfy the conditions given in EquationEqs. (20)(20) (20) and Equation(21)(21) (21) . The first is Case 1: , in which case or , the second is Case 2: , in which case or , and the third is Case 3: , in which case or . In the Case 1, terms in the summation are equal to 1 as and the part of summation appearing in EquationEq. (19)(19) (19) reduces to (22) (22)
In the Case 2, the terms in the summation appearing in EquationEq. (19)(19) (19) are equal to for . The summation in this case reduces to (23) (23)
Similarly in the Case 3, the summation reduces to (24) (24)
Now, adding the terms obtained in EquationEqs. (22)–(24), and substituting the same in EquationEq. (19)(19) (19) , we get EquationEq. (18)(18) (18) proving the theorem. ▪
3.2 Stress of vertices in corona of graphs
In this subsection, we will consider corona of connected graphs G and H to find the stress of vertices therein.
Definition 3.8 (Corona graph).
The corona of two graphs G and H is defined as the graph obtained by taking one copy of G and copies of H, and joining by an edge each vertex of ith copy of H with the ith vertex of G.
Throughout our discussion in this subsection, G is a connected graph with vertices and H is a connected graph with n vertices . We denote the vertices in the copy of H in by . Before proceeding further, we shall describe some notions used in the following discussion. For a matrix M, represents the ith column of M, indicates the column matrix of order m of all 1s, J is a matrix of all 1s. Given a graph H, the join graph is a graph obtained by adding a vertex u adjacent to all the vertices of H.
If A is the adjacency matrix of H, then the adjacency matrix of i.e., is the matrix, say B, is in the form of and
It is clear that the above is completely nonzero matrix and therefore, we have shortest path matrix of given by
The block in the matrix is playing an important role in understanding shortest path matrix of corona of graphs and, in fact, ijth entry of is given by (25) (25)
The ijth entry of gives the number of shortest paths between the ith and jth vertices of H in .
Though we derive the stress of any vertex from the corona in terms of stress of vertices in the factor graph or a smaller graph, we discuss adjacency matrix, shortest path matrix, and distance matrix of corona in the following for the purpose of academic interest. The adjacency matrix of is a block matrix of size . Concentrating on th blocks, for the entries in the block correspond to the vertices of G. As the adjacency among the vertices of G remains unaltered in , the th block for of is . For , the entries of th block represents the adjacency between the pair of vertices from th copy of H in . From the definition of corona graph, it is evident that if a pair of vertices is adjacent in H, then the corresponding pair will be adjacent in every copy of H in and vice versa. Therefore, th block of , for , is given by . Further, for , the th blocks, correspond to the vertices of G and the vertices of H in the th copy of H. Since, is adjacent to all the vertices from the th copy and nonadjacent with the vertices from remaining copies of H, this block is given by an matrix with 1’s in the jth row and 0 in the rest of the rows. For , no vertex of ith copy is adjacent to no vertex in the jth copy of H in . So, the th block for is a zero matrix of order .
Further, we note that the distance matrix is block matrix. For , the th block of is , as the distance between a pair of vertices of G is preserved in . Since every vertex of H in the ith copy is adjacent to in , the th block() of is given by . For , distance between and vertices in the copy of H is and since is adjacent to all the vertices in the copy of H, the block of is given by . For , the distance between the vertices from the copy of H and the copy of H is . Therefore for , the block is given by .
Similarly by looking at the structure of the corona graph, the shortest path matrix can be constructed easily with the help of and . The shortest path matrix is a block matrix of order The blocks of are given as follows:
For , the block of corresponds to the number of shortest paths among the vertices of G in . As the number of shortest paths between a pair of vertices of G remains the same in , this block is given by shortest path matrix of G i.e, .
For , the block corresponds to the number of shortest paths among the vertices in the copy of H in , which is given by the matrix . Therefore the blocks are for all .
For , the block denotes the number of shortest paths between the vertices of G and the vertices in different copies of H in . These blocks are given by .
For , the block corresponds to the vertices from copy and copy of H. As the number of shortest paths between the vertices in the and copy of H is same as the number of shortest paths between the vertices and , this block is given by , where J is matrix of all 1s.
Based on the above observations, is a block matrix given by
In the following theorem, we shall find the stress of vertices in the corona graph using the matrices and .
Theorem 3.9.
Let G be a graph with vertices and let be the vertices in the copy of the graph H in . Then (26) (26) (27) (27) where is the entry of the shortest path matrix of G and is the join graph obtained by adding a vertex u adjacent to all the vertices of H.
Proof.
For any vertex in the copy of H in , the possible shortest paths having as an internal vertex are the ones of length two passing through within the same copy of H. So, the number of such shortest paths in is same as the number of shortest paths in having as an internal vertex. Therefore, proving EquationEq. (26)(26) (26) .
Next we shall find the stress of a vertex from G in . For any pair of vertices and from G, note that any shortest path in G having as internal vertex preserves its character of shortest length in , vice versa. Therefore, (28) (28)
For any pair of nonadjacent vertices and , there is unique shortest path in having as an internal vertex. Therefore, (29) (29)
For each and (), any shortest path between them is the join of and shortest path and therefore, we have . Further, (30) (30)
With the same argument, we have , for , and for . Therefore, we have the following: (31) (31) (32) (32)
and (33) (33)
Now we get EquationEq. (27)(27) (27) , by substituting EquationEqs. (28)–(33) in the expression for stress of in , proving the theorem. ▪
From the above theorem, it may be noted that the computation of stress in the corona is reduced to the exercise of finding the stress of vertices in the factor graph G and the join graph using the respective D and N matrices.
4 Algorithms to find stress and betweenness measure
In this section, we present a few algorithms for computing the stress of a vertex in a general graph and in some special cases using adjacency matrices. Since betweenness measure is closely related to stress, we obtain the same by using the functions obtained during stress computation.
4.1 Shortest path matrix
We begin with the first algorithm for a function which will return the shortest path matrix N for a given graph. The inputs for this algorithm to find the shortest path matrix are the adjacency matrix A and the order n of the graph G.
The loops together in the steps 3 and 4 require iterations. Matrix multiplication, is of and the time required to execute the loop in step 13 is at most , which is executed only if the list L is non empty. Considering the maximum possible iterations, i.e, considering the path graph, which requires iterations to make L an empty set, the total time required is less than . So it follows that the time complexity of Algorithm 1 is .
4.2 Stress of a vertex in general graph
The following Algorithm 2 returns the stress s of a given vertex of the graph.
Initially to find the shortest path matrix in Step 2, we use the Algorithm 1. For m values of the loop in Step 4 of Algorithm 2, the loops in Step 6 and 7, will be executed in iterations. Total time required to execute these for loops will be . So the time complexity of Algorithm 2 will be .
4.3 Betweenness centrality of a vertex in general graph
With a slight variation in step 7 of Algorithm 2, here we present an algorithm to compute the betweenness centrality of a vertex.
To find the shortest path matrix in step 2, we use the Algorithm 1 with complexity . Further, it requires iterations to run the loops in step 4 and step 5. So the time complexity of Algorithm 2 will be .
4.4 Stress in Cartesian product
In the following Algorithm 3, we compute the stress of vertices in the Cartesian product of two graphs G and H. Algorithm 1 is used to get the shortest path matrix of G and H.
In the Algorithm 3, to find the matrices N and M in Steps 4 and 5, we use Algorithm 1 with complexity . Further to execute the loops in Steps 9 and 11, we require iterations. Complexity will be . So the time complexity of Algorithm 3 will be . Without loss of generality, if we assume that , then the time complexity of Algorithm 3 will be
4.5 Stress of vertices in a corona graph
In the following algorithm, we find the stress of vertices of using the adjacency matrices of G and H.
To find shortest path matrix of G in step 4, we use Algorithm 1 with complexity . In step 7, for n values, we use Algorithm 2 to find the stress of vertices in . The complexity will be (where is the size of B). Algorithm 2 is used again in step 10 with complexity . Further, for m values in the loop in step 11, Algorithm 2 of complexity will be used to calculate stress of vertex in G and the loop in step 13 is executed m times. It follows that the complexity of this algorithm is .
Acknowledgments
We thank Professor Bapat for bringing our attention toward number of paths between any two points on the chess board and its relation with binomial coefficient.
Disclosure statement
No potential conflict of interest was reported by the author(s).
Additional information
Funding
References
- Borgatti, S. P., Everett, M. G. (2006). A graph-theoretic perspective on centrality. Soc. Netw. 28(4): 466–484.
- Bhargava, K., Dattatreya, N. N., Rajendra, R. (2020). On stress of a vertex in a graph. arXiv preprint arXiv:2208.13493.
- Camby, E., Caporossi, G., Paiva, M. H. M., Ribeiro, M. R. M., Segatto, M. E. V. (2018). On the number of shortest paths in Cartesian product graphs and its robustness. Les Cahiers du GERAD, GERAD, HEC Montreal, Canada.
- Harary, F. (1988). Graph Theory. Reading, AM: Addison-Wesley Publishing Company.
- Kumar, S., Kannan, B. (2020). Betweenness centrality in Cartesian product of graphs. AKCE Int. J. Graphs Comb. 17(1): 571–583.
- Lopez, R., Worrell, J., Wickus H., Florez, R., Darren, N. A. (2017). Towards a characterization of graphs with distinct betweeness centralities. Australas. J. Combin. 68(2): 285–303.
- Newman, M. (2018). Networks. Oxford: Oxford University Press.
- Poojary, R., Bhat, A. K., Subramanian, A., Karantha, M. P. (2023). The stress of a graph. Commun. Comb. Optim. 8(1): 53–65.
- Poojary, R., Bhat, A. K., Subramanian, A., Karantha, M. P. (2022). Stress of wheel related graphs. Natl. Acad. Sci. Lett. 45: 427–431.
- Scardoni, G., Laudanna, C. (2012). Centralities Based Analysis of Complex Networks. London: IntechOpen.
- Scardoni, G., Tosadori, G., Faizan, M., Spoto, F., Fabbri, F., Laudanna, C. (2015). Biological network analysis with CentiScaPe: Centralities and experimental dataset integration. F1000Research 3: 139.
- Shannon, P., Markiel, A., Ozier, O., Baliga, N. S., Wang, J. T., Ramage, D., Amin, N., Schwikowski, B., Ideker, T. (2003). Cytoscape: A software environment for integrated models of biomolecular interaction networks. Genome Res. 13(11): 2498–2504.
- Shimbel, A. (1953). Structural parameters of communication networks. Bull. Math. Biophys. 15(4): 501–507.