# Characterization of 2-Path Signed Network

Authors: Deepa Sinha; Deepakshi Sharma
Journal: Complexity
 (2020)

---

## Abstract

Asigned network is a network where each edge receives a sign: positive or negative. In this paper, we report our investigation on 2-path signed network of a given signed network Σ, which is defined as the signed network whose vertex set is that of Σ and two vertices in Σ2 are adjacent if there exist a path of length two between them in Σ. An edge ab in Σ2 receives a negative sign if all the paths of length two between them are negative, otherwise it receives a positive sign. A signed network is said to be if clusterable its vertex set can be partitioned into pairwise disjoint subsets, called clusters, such that every negative edge joins vertices in different clusters and every positive edge joins vertices in the same clusters. A signed network is balanced if it is clusterable with exactly two clusters. A signed network is sign-regular if the number of positive (negative) edges incident to each vertex is the same for all the vertices. We characterize the 2-path signed graphs as balanced, clusterable, and sign-regular along with their respective algorithms. The 2-path network along with these characterizations is used to develop a theoretic model for the study and control of interference of frequency in wireless communication networks.


---

## Body

## 1. Introduction

Theintersection graphs or networks [1, 2] form a large family of structures which include many important network such as interval [3, 4], permutation [5, 6], chordal [7, 8], circular-arc [9, 10], circle [11], string [12], line [13, 14], and path [15, 16]. Most of these networks are of great significance not only theoretically but because of their applicability in the fields such as transportation [17], wireless networking [18], scheduling problem [19], molecular biology [20], circuit routing [21], and sociology. The 2-path network is an intersection graph of open neighborhoods [22]. Formally, a 2-path network for a given network is obtained by joining the pair of vertices which form a path of length two in the original network.Signed networks are the network where each edge receives a sign: positive or negative (ref. Figure 1, the edges 13, 32,24, and 25 are negative in (b)). The concept stemmed from psychologist Heider [23, 24] who used the concept of balanced theory to model relations between individuals and society using triads. Harary formulated and restructured the signed networks by introducing structural balance theory [25] for social balance and was used for portfolio management [26], where they used signed graphs to analyse the extent of hedging in a portfolio. These networks are widely used in data clustering [27–29]. Signed networks of some intersection networks have been already studied [30–33]. Also path graphs of signed graphs are discussed in [34–38]. In this paper, we try and establish the results for signed networks defined on 2-path networks.Figure 1
(a) Given network. (b) Its signed network.
(a)(b)The study of networks has come a long way with its applicability in many fields [39–43]. One such application is in wireless networks and frequency allocation problem. The frequency allocation [44] in a wireless network [45] or radio frequency allocation [46] is one of the typical problems that we still face. The interference takes place in a network when the transmission from one station interacts with the transmission from another station. There are three dimensions to the frequency spectrum first being the space in which the emission is radiated, second is the frequency bandwidth, and third is the time. If these three dimensions occur simultaneously for a channel receiving transmission, then interference takes place. Many methods and models such as dipole-moment models [47], Kurtosis detection algorithm and its versions [48], and decomposition method based on reciprocity [49] have been studied for this problem. We, on the other hand, bring a model with a very different approach using the theoretic aspects of signed networks and 2-path networks.We aim at detecting and reducing the interference by assuming the stations/channels as vertices and transmission between them as edges. Furthermore, we assume that two channels (vertices) are joined by a positive edge if and only if they are in different time or frequency bandwidth (assuming that space is always same) and by a negative edge if both are the same in time and frequency bandwidth. IfΣ is the given signed network representing a channel network, then its 2-path signed network Σ2 provides with the interference pattern of different channels at a specific channel. In the 2-path signed network the edge uw is given a negative sign if and only if there exist all-negative two paths in Σ say uv and vw between them, that is, they are the same in time as well as frequency and thus the interference takes place at v because of the vertices u and w.


### 1.1. Definitions and Preliminaries

For standard terminology and notation in network theory, one can refer Harary [50] and West [51], and for signed networks literature, one can refer [52]. Throughout the text, we consider finite, undirected network with no loops or multiple edges. A signed network is an ordered pair Σ=Σu,σ, where Σu is a network G=V,E, called the underlying network of Σ, and σ:E⟶+,− is a function from the edge set E of Σu into the set +,−, called the signature (or sign in short) of Σ. A signed network is all-positive (or all-negative) if all its edges are positive (negative). Furthermore, it is said to be homogeneous if it is either all-positive or all-negative and heterogeneous otherwise. A signed network Σ is said to be sign-regular if the number of positive edges (negative edges), d+vd−v incident at a vertex v in Σ, is independent of the choice of v in Σ, that is, Σ is i,j-sign-regular, where i = d+v is the positive degree of every vertex v in Σ and j = d−v is the negative degree of every vertex v in Σ.Anegative section of a cycle or a path Z is a maximal set D of vertices of Z such that the subsigned network consisting of the edges of Z joining vertices in D is all-negative and connected. A marked signed network is an ordered pair Σμ=Σ,μ, where Σ=Σu,σ is a signed network and μ:VΣu⟶+,− is a function from the vertex set VΣu of Σu into the set +,−, called a marking of Σ. We define VΣμ=vi+,vi−:∀vi∈VΣ. Let v be an arbitrary vertex of a network Σ. We denote the set consisting of all the vertices of Σ adjacent with v by Nv. This set is called the neighborhood set of v and sometimes we call it as neighborhood of v. Next, we define two marked neighborhoods as N∗t=vμ∈VΣμ:tvis an edge with signμ and N∗−t=v−∈VΣμ:tvis an edge. For each Nt of Σu, there exist N∗t in Σ and vice versa. It is important to note that the vertex marking for each vertex is neighborhood dependent, i.e., if a vertex vi forms a negative edge with vj and a positive edge with vk in Σ, then vi− belongs to the marked neighborhood of vj, N∗vj and vi+∈N∗vk. Also, each vertex in Nt appears with exactly one mark in N∗t.Theclique of a network Σu is a subset of vertices such that every two vertices in the subset are connected by an edge. δNt is a clique generated by vertices in Nt. A cycle in a signed network Σ is said to be positive if the product of the signs of its edges is positive or, equivalently, if the number of negative edges in it is even. A cycle which is not positive is said to be negative. A signed network is balanced if all its cycles are positive. A signed network is said to be clusterable if its vertex set can be partitioned into pairwise disjoint subsets, called clusters, such that every negative edge joins vertices in different clusters and every positive edge joins vertices in the same clusters. A common neighbor of vertices vi and vj is a vertex v such that v∈Nvi∩Nvj.Property 1.
Ifvi,vj,vk∈VΣ, then by property Pvi,vj;vk, we mean vi−,vj−⊆N∗vk.Property 2.
By propertyP:=Pvi,vj, we mean that if property Pvi,vj;v holds for one common neighbor v of vi and vj, then it holds for every common neighbor v of vi and vj.
The2-path signed network [34] Σ2=V,E′,σ′ of a signed network Σ=V,E,σ is defined as follows. The vertex set is the same as the original signed network Σ, and two vertices u,v∈VΣ2 are adjacent if and only if there exist a path of length two in Σ. The edge uv∈VΣ2 is negative if and only if all the edges in all the two paths in Σ between them are negative otherwise the edge is positive. The definition of 2-path signed network was used [53], to bring out some basic results, which was further extended and shaped in the present paper. The 2 subsets vi,vj having property P are named as Ppairs and the set of all P pairs is denoted by P∗. A negative section v1,v2,…,vk in cycle or path is said to be Psection if every alternate vertices forms P pair. If vk=v1 in the P section, then such a P section is called Pcycle.Remark 1.
An edgevivj is negative in 2-path signed network Σ2 if and only if vi,vj a neighborhood of a vertex vk has property P.
Consider the signed network (a) of Figure2; clearly, by definition of 2-path signed network, 14 and 23 are the only negative edges as there exist an all-negative path between 1 and 4 and 2 and 3 of length two in Σ. Let us consider the marked neighborhood for each of the vertices 1 to 4:(1)N∗1=2−,N∗2=1−,3+,4−,N∗3=2+,4−,N∗4=2−,3−.
One can note that there are following pairs in each neighborhood:1−,3+, 3+,4−, and 1−,4− in N∗2, 2+,4− in N∗3, and 2−,3− in N∗4. These pairs give rise to the edges in Σ2, where the edge 24, 34, and 13 get positive signs as atleast one of the vertices in each set is positively marked (thus does not form a P pair).
The pairs1−,4− and 2−,3− are the only P pairs, then by Remark 2.1 these pairs give rise to the negative edges 14 and 23.Figure 2
(a) Given signed network. (b) Its 2-path signed network.
(a)(b)Figure 3
Interference atB due to A and C.


### 1.2. Model and Assumptions

Consider the vertices in a network system as channels or stations and edges as the signals or transmissions. Now, the problem of interference between stationsa,b,c arise when the transmissions from a and c reaching at b are in the same space, at the same frequency and time. We assume that the two parameters space and frequency are the same for all transmissions but the time is the variation parameter. So, a positive edge between two channels represents that they always have a fixed time of transmission (which is different from the adjoining transmission) and a negative edge means a variable transmission (which is different from the fixed time transmission). The problem arises when two of the negative edges are incident to a station as here there is a high risk of interference in the network. This network pattern can be observed using 2-path networks. The 2-path network Σ2 of the network Σ gives the possible interference pattern so a negative edge ab in the 2-path signed network means that there exist a vertex c such that ac and cb are the transmissions which could possibly interfere with each other at c. Thus, by analyzing 2-path networks, we can study and correct this problem of interference.We thus study the theoretic Properties 2-path networks keeping our problem of interference in the background. In Section1, we characterize the 2-path signed network, some of the results of which were presented in [35], give algorithms to construct 2-path signed network, detect if a network is isomorphic to a 2-path signed network, and collect P pairs. Section 2 is on the balancedness of 2-path signed networks where we characterize signed network whose 2-path signed networks are balanced. The property of balanced network is used to identify and categorize all the channels in 2-path in exactly two groups such that the negative edges are across the groups and positive are in the same class. We also provide an algorithm for the same. Section 3 is dedicated to another property of signed network known as clusterability, where we check whether we can categorize our vertices in more that two clusters so that the negative edges are across the group. We follow the property of sign-regularity in Section 4.


## 1.1. Definitions and Preliminaries

For standard terminology and notation in network theory, one can refer Harary [50] and West [51], and for signed networks literature, one can refer [52]. Throughout the text, we consider finite, undirected network with no loops or multiple edges. A signed network is an ordered pair Σ=Σu,σ, where Σu is a network G=V,E, called the underlying network of Σ, and σ:E⟶+,− is a function from the edge set E of Σu into the set +,−, called the signature (or sign in short) of Σ. A signed network is all-positive (or all-negative) if all its edges are positive (negative). Furthermore, it is said to be homogeneous if it is either all-positive or all-negative and heterogeneous otherwise. A signed network Σ is said to be sign-regular if the number of positive edges (negative edges), d+vd−v incident at a vertex v in Σ, is independent of the choice of v in Σ, that is, Σ is i,j-sign-regular, where i = d+v is the positive degree of every vertex v in Σ and j = d−v is the negative degree of every vertex v in Σ.Anegative section of a cycle or a path Z is a maximal set D of vertices of Z such that the subsigned network consisting of the edges of Z joining vertices in D is all-negative and connected. A marked signed network is an ordered pair Σμ=Σ,μ, where Σ=Σu,σ is a signed network and μ:VΣu⟶+,− is a function from the vertex set VΣu of Σu into the set +,−, called a marking of Σ. We define VΣμ=vi+,vi−:∀vi∈VΣ. Let v be an arbitrary vertex of a network Σ. We denote the set consisting of all the vertices of Σ adjacent with v by Nv. This set is called the neighborhood set of v and sometimes we call it as neighborhood of v. Next, we define two marked neighborhoods as N∗t=vμ∈VΣμ:tvis an edge with signμ and N∗−t=v−∈VΣμ:tvis an edge. For each Nt of Σu, there exist N∗t in Σ and vice versa. It is important to note that the vertex marking for each vertex is neighborhood dependent, i.e., if a vertex vi forms a negative edge with vj and a positive edge with vk in Σ, then vi− belongs to the marked neighborhood of vj, N∗vj and vi+∈N∗vk. Also, each vertex in Nt appears with exactly one mark in N∗t.Theclique of a network Σu is a subset of vertices such that every two vertices in the subset are connected by an edge. δNt is a clique generated by vertices in Nt. A cycle in a signed network Σ is said to be positive if the product of the signs of its edges is positive or, equivalently, if the number of negative edges in it is even. A cycle which is not positive is said to be negative. A signed network is balanced if all its cycles are positive. A signed network is said to be clusterable if its vertex set can be partitioned into pairwise disjoint subsets, called clusters, such that every negative edge joins vertices in different clusters and every positive edge joins vertices in the same clusters. A common neighbor of vertices vi and vj is a vertex v such that v∈Nvi∩Nvj.Property 1.
Ifvi,vj,vk∈VΣ, then by property Pvi,vj;vk, we mean vi−,vj−⊆N∗vk.Property 2.
By propertyP:=Pvi,vj, we mean that if property Pvi,vj;v holds for one common neighbor v of vi and vj, then it holds for every common neighbor v of vi and vj.
The2-path signed network [34] Σ2=V,E′,σ′ of a signed network Σ=V,E,σ is defined as follows. The vertex set is the same as the original signed network Σ, and two vertices u,v∈VΣ2 are adjacent if and only if there exist a path of length two in Σ. The edge uv∈VΣ2 is negative if and only if all the edges in all the two paths in Σ between them are negative otherwise the edge is positive. The definition of 2-path signed network was used [53], to bring out some basic results, which was further extended and shaped in the present paper. The 2 subsets vi,vj having property P are named as Ppairs and the set of all P pairs is denoted by P∗. A negative section v1,v2,…,vk in cycle or path is said to be Psection if every alternate vertices forms P pair. If vk=v1 in the P section, then such a P section is called Pcycle.Remark 1.
An edgevivj is negative in 2-path signed network Σ2 if and only if vi,vj a neighborhood of a vertex vk has property P.
Consider the signed network (a) of Figure2; clearly, by definition of 2-path signed network, 14 and 23 are the only negative edges as there exist an all-negative path between 1 and 4 and 2 and 3 of length two in Σ. Let us consider the marked neighborhood for each of the vertices 1 to 4:(1)N∗1=2−,N∗2=1−,3+,4−,N∗3=2+,4−,N∗4=2−,3−.
One can note that there are following pairs in each neighborhood:1−,3+, 3+,4−, and 1−,4− in N∗2, 2+,4− in N∗3, and 2−,3− in N∗4. These pairs give rise to the edges in Σ2, where the edge 24, 34, and 13 get positive signs as atleast one of the vertices in each set is positively marked (thus does not form a P pair).
The pairs1−,4− and 2−,3− are the only P pairs, then by Remark 2.1 these pairs give rise to the negative edges 14 and 23.Figure 2
(a) Given signed network. (b) Its 2-path signed network.
(a)(b)Figure 3
Interference atB due to A and C.


## 1.2. Model and Assumptions

Consider the vertices in a network system as channels or stations and edges as the signals or transmissions. Now, the problem of interference between stationsa,b,c arise when the transmissions from a and c reaching at b are in the same space, at the same frequency and time. We assume that the two parameters space and frequency are the same for all transmissions but the time is the variation parameter. So, a positive edge between two channels represents that they always have a fixed time of transmission (which is different from the adjoining transmission) and a negative edge means a variable transmission (which is different from the fixed time transmission). The problem arises when two of the negative edges are incident to a station as here there is a high risk of interference in the network. This network pattern can be observed using 2-path networks. The 2-path network Σ2 of the network Σ gives the possible interference pattern so a negative edge ab in the 2-path signed network means that there exist a vertex c such that ac and cb are the transmissions which could possibly interfere with each other at c. Thus, by analyzing 2-path networks, we can study and correct this problem of interference.We thus study the theoretic Properties 2-path networks keeping our problem of interference in the background. In Section1, we characterize the 2-path signed network, some of the results of which were presented in [35], give algorithms to construct 2-path signed network, detect if a network is isomorphic to a 2-path signed network, and collect P pairs. Section 2 is on the balancedness of 2-path signed networks where we characterize signed network whose 2-path signed networks are balanced. The property of balanced network is used to identify and categorize all the channels in 2-path in exactly two groups such that the negative edges are across the groups and positive are in the same class. We also provide an algorithm for the same. Section 3 is dedicated to another property of signed network known as clusterability, where we check whether we can categorize our vertices in more that two clusters so that the negative edges are across the group. We follow the property of sign-regularity in Section 4.


## 2. 2-Path Signed Network

### 2.1. Characterization of 2-Path Signed Network

In this section, we give a characterization of 2-path signed network. We check if a given signed network is a 2-path signed network of some signed network. We then find its underlying signed network. Following characterization of 2-path networks was given by Acharya and Vartak.Lemma 1 (see [22]).
A connected networkG with vertices vi,i=1,⋯,n, is a 2-path network of some network H if and only if G contains a collection of complete subgraphs G1,G2,⋯,Gn such that, for each i,j=1,⋯,n, the following hold: (i) vi∉Gi, (ii) vi∈Gj⟺vj∈Gi, and (iii) if vivj∈G then there exists Gk containing vivj.Letvivj be an edge in a signed network Σ. Let μij denote the marking on the vertex vj in N∗vi such that μij=σvivj; then, we have the following theorem.Theorem 1.
A connected signed networkΣ with vertices v1,v2,…,vn is a 2-path signed network of some signed network Σ′ if and only if Σ contains a collection of complete signed subgraphs Σ1,Σ2,…,Σn with vertices vi in Σj,j≠i having the marking μji such that, for each i,j=1,…,n, the following hold:(i)
vi∉Σi(ii)
viμji∈Σj⇔vjμji∈Σi, where i≠j and μji=μij(iii)
Ifvivj∈EΣ, then there exists Σk containing viμki,vjμkj and if σvivj=−⇔vi,vj is a P pair in ΣkProof.
Necessity. Suppose Σ is a 2-path signed network of signed network Σ′ with vertices v1,v2,…,vn. To show that there exist a collection of n complete signed subgraphs Σ1,Σ2,…,Σn such that (i), (ii), and (iii) hold, consider the marked neighborhood N∗vi so that Σi=δN∗vi for each vertex v1,v2,…,vn in Σ′. Each N∗vi,i=1 to n, generates a complete signed subgraph in 2-path signed network Σ of Σ′, since N∗vi consists of elements which have a common neighbor vi in Σ′. Next, vi∉N∗vi since the signed network Σ′ is simple and vi∉Nvi. Let viμji∈N∗vj for some i,j;i≠j,1≤i,j≤n. Then, vivj is an edge in Σ′ such that σvivj=μji, and thus vjμij is in the marked neighborhood N∗vi. Therefore, for i≠j, viμki,∈Σj⇔vjμkj∈Σi. Next, since the mark μij depends on the sign of edge vivj in Σ′, the vertex vj∈N∗vi gets the marking from the corresponding sign σvivj=μij; hence, μji=μij and (ii) follows.
Ifvivj is an edge in 2-path signed network Σ and thus in Σu, then from Lemma 1, vi,vj∈Nvk for some k. Let vivj be an edge in Σ with a sign “−,” then vivk and vkvj are negative edges in Σ′, by definition of 2-path signed network. Thus, by Remark 1, vi−,vj−⊆N∗vk and vi,vj is P pair. Hence, (iii) holds.
Sufficiency. Let Σ contain a collection of complete signed subgraphs Σ1,Σ2,…,\\Σn with vertices vi in Σj,j≠i with the marking μji, satisfying the three properties (i), (ii), and (iii). Join each vertex vi to the vertices of Σi; let the obtained signed network be Σ′. Let vj be in Σi, having the marking μij. Then, the sign of edge vivj in Σ′ is given by μij. From our construction of Σ′ and property (ii), as vjμij∈Σi, we have viμji∈Σj and μij=μji. Note that if vjvk∈EΣ, then by (iii), there exist Σi such that vjμij∈Σi and vkμik∈Σi. Also if sign of the edge vjvk is negative in Σ′, then μij=μik=− and vjvk is a P pair in Σ, whereas if the edge is positive in Σ′, then the marks μij and μik are according to the edge sign vivj and vivk in Σ, respectively.
Next, we will show thatΣ′2≅Σ. Clearly, the vertex set of Σ and Σ′2 is the same. We are left to show that their adjacencies along with their signs are preserved. For some k≠i and k≠j, let vivj be an arbitrary edge in Σ, such that vi,vj is in Σk. Clearly, vivk and vkvj are edges in Σ′. Thus, there is a path of length two between vi and vj in Σ′. Hence, vivj is an edge in Σ′2.
Furthermore, letvlvm be an arbitrary edge in Σ′2. Clearly, there must be atleast one path of length two vlvkvm in Σ′. As Σ′ is constructed joining a vertex vk to all those vertices present in Σk, therefore by (iii), vl and vm is in Σk (as both these vertices are adjacent to vk in Σ′). Hence, vlvm is an edge in one of the cliques and thus it is an edge in Σ. Hence, the adjacencies are preserved.
Finally, we show that the sign ofvivj is the same in Σ′2 and Σ. Let vivj be a negative edge in Σ; then, by condition (iii), vi,vj is a P pair in Σk, for some k, k≠i,j. By Property 2 and signing of the edges in Σ′, the edges formed by vertices incident to both vi and vj in Σ′ will all be negative; thus, the edge vivj in 2-path signed network Σ′2 is negative. Similarly, if σvivj=− in Σ′2, then all the vivj-paths of length two will be all-negative in Σ′. Let vivkvj be a 2-path in Σ′. As the edges incident to vk in Σ′ are formed by joining a vertex vk with vertices in Σk and σvkvi=μki and σvkvj=μkj, where viμki,vjμkj∈Σk and μki=μkj=−, then, since all edges in 2-path between vertices vi and vj in Σ′ are negative, then by (iii) σvivj=− in Σ. Similarly, the same holds for positive edge. If vivj is a positive edge in Σ′2, then there exist atleast one vertex vk in Σ′, where vivkvj is a path of length two. Then, clearly, at least one of the two vertices vi and vj forms a positive edge with vk in Σ′, also in the complete sub signed network Σk containing both vi and vj, and thus vivj∈EΣ, and by (iii) it cannot be a negative edge. Hence, σvivj=+ in Σ. Conversely, if σvivj=+ in Σ, then as done above for negative edge for some Σk, the mark of one of these two vertices would be positive, and thus there would be a heterogeneous path of length two between vi and vj in Σ′ and thus a positive edge in Σ′2. Hence, Σ′2≅Σ.
Before going further, we prove the following lemmas.Lemma 2.
If a signed networkΣ has an induced cycle of length 2k,k≥3, then Σ2 contains two vertex disjoint cycles of length k each.Proof.
Letv1t1v2,…,vktkv1 be an induced cycle of length 2k,k≥3, in a signed network Σ. Then, there is a path of length two between each pair vi and vi+1 for i=1,…,k−1 and vk,v1. Thus, v1v2,…,vkv1 is a cycle of length k in Σ2. Similarly, t1t2,…,tkt1 is a cycle of length k in Σ2. Clearly, there is no vertex in common in the two cycles. Hence, the result follows.Remark 2.
If the signed networkΣ consists of a cycle of length 4, then Σ2 contains two disjoint edges corresponding to the vertices of the cycle.Lemma 3.
For a signed networkΣ, Σ2 contains an induced cycle of length k (k is odd and k>3) if either Σ has a cycle of length k or Σ has a cycle of length 2k.Proof.
First, assume thatΣ has an induced cycle C:v1v2,…,vkv1 of length k (k is odd and k>3). Clearly, C′:v1v3,…,vkv2,…,vk−1v1 is a cycle of length k in Σ2.
Next, ifΣ has an induced cycle v1t1,…,vktk of length 2k, where vi,ti∈VΣ for i=1,2,…,k, clearly, v1v2,…,vkv1 and t1t2,…,tkt1 are two cycles of length k in Σ2. Hence, result follows.


### 2.2. Algorithm to DetectP Pairs

Here, in Algorithm1, we present algorithm for detection of P pairs. For an input network Σ, these P pairs gives the negative edges in Σ2 and thus will be used as an input for all the other future algorithms.Algorithm 1: An algorithm to detect and collect P pairs.
Input: Adjacency matrix A and dimension n.Output: Array P which has all collection of P pair and array Q which has pair of vertices which are not P pairs.Process:(1)
Enter the ordern and adjacency matrix A for the signed network Σ(2)
fori=1 to n2do(3)
Pi=0; Qi=0,(4)
t=1; l=1;(5)
fori=1 to ndo(6)
forj=1 to ndo(7)
fork=1:ndo(8)
if (i≠j≠k) then(9)
ifAi,j=1&&Ak,j=−1‖Ai,j=1&&Ak,j=1‖Ai,j=−1&&Ak,j=1then(10)
Qt=i;Qt+1=k;(11)
t=t+2;(12)
fori=1:ndo(13)
forj=1:ndo(14)
ifAi,j=−1then(15)
fork=1:ndo(16)
ifAk,j=−1&&i≠jthen(17)
Pl=i;Pl+1=k;(18)
l=l+2;(19)
fori=1:t−2, i=i+2do(20)
forj=1 to l−2, j=j+2do(21)
ifPi=Qj&&Pi+1=Qj+1then(22)
Pi=0;(23)
Pi+1=0;


#### 2.2.1. Complexity

In Steps 5, 6, and 7, we use three different loops running upton times (number of vertices). Thus, the complexity of this fragment is equal to On3.Next, we use three nested loops in Steps 12, 13, and 15. Again the complexity isOn3.The loops at Step 19 and Step 20 are used for the arrayP and Q with a size of m=l−2 and g=t−2, respectively. Since the maximum number of edges in a network is nn−1/2 and P and Q collects vertices incident to edges, thus m≤nn−1 and g≤nn−1. Therefore, the complexity of this fragment is Onn−1≤On2.Combining the above, the total complexity equalsOn3+On3+On2. Hence, the complexity involved in Algorithm 1 is On3.


#### 2.2.2. Implementation of Algorithm

Example 1.
In this example, we are given with a signed network, as shown in Figure4(a), and we find all the P pairs for the given signed network Σ. Let us consider adjacency matrix for the signed network which is given as follows:(2)A=0−1−10−10−11−1−1010110.
In order to detect theP pairs of Σ, we use Algorithm 1 where the inputs are the matrix A and size n=4. The size of array P and Q is initially fixed as n2. After initializing the array P and Q as zero, t=1 and l=1, we enter the first, second, and third loop which run for 1 to 4. The three loops at Steps 5, 6, and 7 are used to obtain two distinct elements Ai,j and Aj,k. Next, in Step 9 we check pair of vertices i,j and j,k if Ai,j=1 and Aj,k=1 or Ai,j=−1 and Aj,k=1 or Ai,j=1 and Aj,k=−1, then i and k enter as an consecutive entry in the array Q. The array Q collects the vertices forming positive 2-paths in Σ. For the above matrix, as we enter the loop, then for i=1,j=2,k=4, we find that A1,2=−1 and A2,4=1. Thus, as t=1, Q1=1 and Q2=4 and t is incremented to t=3. Similarly, after completing all the loops we get Q as follows.
One can note that the number of elements in arrayQ is given by the t−2 (since every time we enter Step 9, t is incremented by 2). In the given example, t=16, and thus size of array Q is 14. Next, we enter loop at Step 13, to find all the edges ij and jk such that Ai,j=−1 and Aj,k=−1. Once such pair is obtained then i and k are collected in Array P as done for array Q. For the given example, array P comes out to be
The size ofP is given by l−2 and in our example l=10. Finally, we compare the elements of P and Q pairwise to find if there are pairs of vertices which is common in both and then we remove these pairs from P. This is done by using two loops one moves from 1 to t−2 (the size of array Q) and the other moves from 1 to l−2 (size of array P). For i=5 and j=5, we see that P5=Q5 and P6=Q6. Therefore, P5=0 and P6=0. Proceeding in the same way, we obtain P for the given example as:
Thus, theP pair are 1,3 and 1,2. From Figure 4 and Remark 1, we can verify that the P pair obtained in the algorithm is the same as that for the given signed network.Figure 4
(a) Given signed networkΣ. (b) Its 2-path signed network.
(a)(b)Remark 3.
Each pairQi,Qi+1 in array Q, for i=1 to l−1, is a pair of vertices in Σ, which have a path of length two between them in Σ. Since they do not form a P pair, they form a positive edge in Σ2 (by Remark 1).


### 2.3. Algorithm to Construct 2-Path Signed Network

Next in Algorithm2, we obtain the 2-path signed network Σ2 for a given signed network Σ. We use the adjacency matrix A of Σ. We use Algorithm 1, to obtain the vertices forming negative edges (collected in array P) and positive edges (collected in array Q) of 2-path signed network. The adjacency matrix of 2-path signed network obtained is saved in matrix B.Algorithm 2: Algorithm to obtain a 2-path signed network for a given signed network.
Input: Adjacency matrix A, dimension n and array P from Algorithm 1.Output: Adjacency matrix B of 2-path signed network.Process:(1)
Enter the ordern and adjacency matrix A of for a given signed network Σ.(2)
fori=1 to ndo(3)
forj=1:ndo(4)
Bi,j=0 5 fort=1:m−1,t=t+2do(5)
if (Pt≠0) then(6)
ifPt=j&&Pt+1=kthen(7)
Bk,j=−1(8)
Bj,k=−1(9)
fort=1:g−1,t=t+2do(10)
ifQt=j&&Qt+1=kthen(11)
Bk,j=1(12)
Bj,k=1


#### 2.3.1. Complexity

In Step 2, we use two loops to initialize the matrixB zero, and thus the complexity of these steps is On2.In Step 5, we use a loop which runs up tom−1, m≤nn−1 (from previous algorithm). Thus, the complexity of this step is Onn−1=On2. Similarly, in Step 10, we use a loop which runs up to g−1, g≤nn−1. Again complexity of this step is Onn−1=On2.The total complexity isOn2+On2+On2 = On2.


#### 2.3.2. Implementation of the Algorithm

Example 2.
We are given with a signed networkΣ, as shown in Figure 4(a), with the adjacency matrix A as in Example 1. We have to find the adjacency matrix B of the 2-path signed network Σ2. In Steps 2 and 3, we use two loops, each running from 1 to 4 as n=4 and assign zero to all the entries of matrix B. Next, with the help of Algorithm 1, we obtain P as Q as
In Step 5, we enter the loop running uptom=7 for each pair Pt,Pt+1 which saves the vertices forming negative edge in Σ2. As an edge jk is given by entry jth row and kth column and by kth row and jth in the adjacency matrix, for each pair Pt=j and Pt+1=k, Bj,k=Bk,j=−1. Thus, for t=1, B1,3=B3,1=−1, similarly, for t=3B12=B21=−1. Thus, the matrix B after Step 9 is(3)A=0−1−10−1000−10000000.
Next, in Step 10, we enter the loop to find the vertices forming positive edges inΣ2, which is given by pair of vertices in array Q. For t=1, Q1=1,Q2=4 and so B1,4=B1,4=1. After running the loop for g=13, matrix B is given by(4)A=0−1−11−1011−11011110,which is the adjacency matrix for the 2-path signed network Σ2, as shown in Figure 4(b).


## 2.1. Characterization of 2-Path Signed Network

In this section, we give a characterization of 2-path signed network. We check if a given signed network is a 2-path signed network of some signed network. We then find its underlying signed network. Following characterization of 2-path networks was given by Acharya and Vartak.Lemma 1 (see [22]).
A connected networkG with vertices vi,i=1,⋯,n, is a 2-path network of some network H if and only if G contains a collection of complete subgraphs G1,G2,⋯,Gn such that, for each i,j=1,⋯,n, the following hold: (i) vi∉Gi, (ii) vi∈Gj⟺vj∈Gi, and (iii) if vivj∈G then there exists Gk containing vivj.Letvivj be an edge in a signed network Σ. Let μij denote the marking on the vertex vj in N∗vi such that μij=σvivj; then, we have the following theorem.Theorem 1.
A connected signed networkΣ with vertices v1,v2,…,vn is a 2-path signed network of some signed network Σ′ if and only if Σ contains a collection of complete signed subgraphs Σ1,Σ2,…,Σn with vertices vi in Σj,j≠i having the marking μji such that, for each i,j=1,…,n, the following hold:(i)
vi∉Σi(ii)
viμji∈Σj⇔vjμji∈Σi, where i≠j and μji=μij(iii)
Ifvivj∈EΣ, then there exists Σk containing viμki,vjμkj and if σvivj=−⇔vi,vj is a P pair in ΣkProof.
Necessity. Suppose Σ is a 2-path signed network of signed network Σ′ with vertices v1,v2,…,vn. To show that there exist a collection of n complete signed subgraphs Σ1,Σ2,…,Σn such that (i), (ii), and (iii) hold, consider the marked neighborhood N∗vi so that Σi=δN∗vi for each vertex v1,v2,…,vn in Σ′. Each N∗vi,i=1 to n, generates a complete signed subgraph in 2-path signed network Σ of Σ′, since N∗vi consists of elements which have a common neighbor vi in Σ′. Next, vi∉N∗vi since the signed network Σ′ is simple and vi∉Nvi. Let viμji∈N∗vj for some i,j;i≠j,1≤i,j≤n. Then, vivj is an edge in Σ′ such that σvivj=μji, and thus vjμij is in the marked neighborhood N∗vi. Therefore, for i≠j, viμki,∈Σj⇔vjμkj∈Σi. Next, since the mark μij depends on the sign of edge vivj in Σ′, the vertex vj∈N∗vi gets the marking from the corresponding sign σvivj=μij; hence, μji=μij and (ii) follows.
Ifvivj is an edge in 2-path signed network Σ and thus in Σu, then from Lemma 1, vi,vj∈Nvk for some k. Let vivj be an edge in Σ with a sign “−,” then vivk and vkvj are negative edges in Σ′, by definition of 2-path signed network. Thus, by Remark 1, vi−,vj−⊆N∗vk and vi,vj is P pair. Hence, (iii) holds.
Sufficiency. Let Σ contain a collection of complete signed subgraphs Σ1,Σ2,…,\\Σn with vertices vi in Σj,j≠i with the marking μji, satisfying the three properties (i), (ii), and (iii). Join each vertex vi to the vertices of Σi; let the obtained signed network be Σ′. Let vj be in Σi, having the marking μij. Then, the sign of edge vivj in Σ′ is given by μij. From our construction of Σ′ and property (ii), as vjμij∈Σi, we have viμji∈Σj and μij=μji. Note that if vjvk∈EΣ, then by (iii), there exist Σi such that vjμij∈Σi and vkμik∈Σi. Also if sign of the edge vjvk is negative in Σ′, then μij=μik=− and vjvk is a P pair in Σ, whereas if the edge is positive in Σ′, then the marks μij and μik are according to the edge sign vivj and vivk in Σ, respectively.
Next, we will show thatΣ′2≅Σ. Clearly, the vertex set of Σ and Σ′2 is the same. We are left to show that their adjacencies along with their signs are preserved. For some k≠i and k≠j, let vivj be an arbitrary edge in Σ, such that vi,vj is in Σk. Clearly, vivk and vkvj are edges in Σ′. Thus, there is a path of length two between vi and vj in Σ′. Hence, vivj is an edge in Σ′2.
Furthermore, letvlvm be an arbitrary edge in Σ′2. Clearly, there must be atleast one path of length two vlvkvm in Σ′. As Σ′ is constructed joining a vertex vk to all those vertices present in Σk, therefore by (iii), vl and vm is in Σk (as both these vertices are adjacent to vk in Σ′). Hence, vlvm is an edge in one of the cliques and thus it is an edge in Σ. Hence, the adjacencies are preserved.
Finally, we show that the sign ofvivj is the same in Σ′2 and Σ. Let vivj be a negative edge in Σ; then, by condition (iii), vi,vj is a P pair in Σk, for some k, k≠i,j. By Property 2 and signing of the edges in Σ′, the edges formed by vertices incident to both vi and vj in Σ′ will all be negative; thus, the edge vivj in 2-path signed network Σ′2 is negative. Similarly, if σvivj=− in Σ′2, then all the vivj-paths of length two will be all-negative in Σ′. Let vivkvj be a 2-path in Σ′. As the edges incident to vk in Σ′ are formed by joining a vertex vk with vertices in Σk and σvkvi=μki and σvkvj=μkj, where viμki,vjμkj∈Σk and μki=μkj=−, then, since all edges in 2-path between vertices vi and vj in Σ′ are negative, then by (iii) σvivj=− in Σ. Similarly, the same holds for positive edge. If vivj is a positive edge in Σ′2, then there exist atleast one vertex vk in Σ′, where vivkvj is a path of length two. Then, clearly, at least one of the two vertices vi and vj forms a positive edge with vk in Σ′, also in the complete sub signed network Σk containing both vi and vj, and thus vivj∈EΣ, and by (iii) it cannot be a negative edge. Hence, σvivj=+ in Σ. Conversely, if σvivj=+ in Σ, then as done above for negative edge for some Σk, the mark of one of these two vertices would be positive, and thus there would be a heterogeneous path of length two between vi and vj in Σ′ and thus a positive edge in Σ′2. Hence, Σ′2≅Σ.
Before going further, we prove the following lemmas.Lemma 2.
If a signed networkΣ has an induced cycle of length 2k,k≥3, then Σ2 contains two vertex disjoint cycles of length k each.Proof.
Letv1t1v2,…,vktkv1 be an induced cycle of length 2k,k≥3, in a signed network Σ. Then, there is a path of length two between each pair vi and vi+1 for i=1,…,k−1 and vk,v1. Thus, v1v2,…,vkv1 is a cycle of length k in Σ2. Similarly, t1t2,…,tkt1 is a cycle of length k in Σ2. Clearly, there is no vertex in common in the two cycles. Hence, the result follows.Remark 2.
If the signed networkΣ consists of a cycle of length 4, then Σ2 contains two disjoint edges corresponding to the vertices of the cycle.Lemma 3.
For a signed networkΣ, Σ2 contains an induced cycle of length k (k is odd and k>3) if either Σ has a cycle of length k or Σ has a cycle of length 2k.Proof.
First, assume thatΣ has an induced cycle C:v1v2,…,vkv1 of length k (k is odd and k>3). Clearly, C′:v1v3,…,vkv2,…,vk−1v1 is a cycle of length k in Σ2.
Next, ifΣ has an induced cycle v1t1,…,vktk of length 2k, where vi,ti∈VΣ for i=1,2,…,k, clearly, v1v2,…,vkv1 and t1t2,…,tkt1 are two cycles of length k in Σ2. Hence, result follows.


## 2.2. Algorithm to DetectP Pairs

Here, in Algorithm1, we present algorithm for detection of P pairs. For an input network Σ, these P pairs gives the negative edges in Σ2 and thus will be used as an input for all the other future algorithms.Algorithm 1: An algorithm to detect and collect P pairs.
Input: Adjacency matrix A and dimension n.Output: Array P which has all collection of P pair and array Q which has pair of vertices which are not P pairs.Process:(1)
Enter the ordern and adjacency matrix A for the signed network Σ(2)
fori=1 to n2do(3)
Pi=0; Qi=0,(4)
t=1; l=1;(5)
fori=1 to ndo(6)
forj=1 to ndo(7)
fork=1:ndo(8)
if (i≠j≠k) then(9)
ifAi,j=1&&Ak,j=−1‖Ai,j=1&&Ak,j=1‖Ai,j=−1&&Ak,j=1then(10)
Qt=i;Qt+1=k;(11)
t=t+2;(12)
fori=1:ndo(13)
forj=1:ndo(14)
ifAi,j=−1then(15)
fork=1:ndo(16)
ifAk,j=−1&&i≠jthen(17)
Pl=i;Pl+1=k;(18)
l=l+2;(19)
fori=1:t−2, i=i+2do(20)
forj=1 to l−2, j=j+2do(21)
ifPi=Qj&&Pi+1=Qj+1then(22)
Pi=0;(23)
Pi+1=0;


### 2.2.1. Complexity

In Steps 5, 6, and 7, we use three different loops running upton times (number of vertices). Thus, the complexity of this fragment is equal to On3.Next, we use three nested loops in Steps 12, 13, and 15. Again the complexity isOn3.The loops at Step 19 and Step 20 are used for the arrayP and Q with a size of m=l−2 and g=t−2, respectively. Since the maximum number of edges in a network is nn−1/2 and P and Q collects vertices incident to edges, thus m≤nn−1 and g≤nn−1. Therefore, the complexity of this fragment is Onn−1≤On2.Combining the above, the total complexity equalsOn3+On3+On2. Hence, the complexity involved in Algorithm 1 is On3.


### 2.2.2. Implementation of Algorithm

Example 1.
In this example, we are given with a signed network, as shown in Figure4(a), and we find all the P pairs for the given signed network Σ. Let us consider adjacency matrix for the signed network which is given as follows:(2)A=0−1−10−10−11−1−1010110.
In order to detect theP pairs of Σ, we use Algorithm 1 where the inputs are the matrix A and size n=4. The size of array P and Q is initially fixed as n2. After initializing the array P and Q as zero, t=1 and l=1, we enter the first, second, and third loop which run for 1 to 4. The three loops at Steps 5, 6, and 7 are used to obtain two distinct elements Ai,j and Aj,k. Next, in Step 9 we check pair of vertices i,j and j,k if Ai,j=1 and Aj,k=1 or Ai,j=−1 and Aj,k=1 or Ai,j=1 and Aj,k=−1, then i and k enter as an consecutive entry in the array Q. The array Q collects the vertices forming positive 2-paths in Σ. For the above matrix, as we enter the loop, then for i=1,j=2,k=4, we find that A1,2=−1 and A2,4=1. Thus, as t=1, Q1=1 and Q2=4 and t is incremented to t=3. Similarly, after completing all the loops we get Q as follows.
One can note that the number of elements in arrayQ is given by the t−2 (since every time we enter Step 9, t is incremented by 2). In the given example, t=16, and thus size of array Q is 14. Next, we enter loop at Step 13, to find all the edges ij and jk such that Ai,j=−1 and Aj,k=−1. Once such pair is obtained then i and k are collected in Array P as done for array Q. For the given example, array P comes out to be
The size ofP is given by l−2 and in our example l=10. Finally, we compare the elements of P and Q pairwise to find if there are pairs of vertices which is common in both and then we remove these pairs from P. This is done by using two loops one moves from 1 to t−2 (the size of array Q) and the other moves from 1 to l−2 (size of array P). For i=5 and j=5, we see that P5=Q5 and P6=Q6. Therefore, P5=0 and P6=0. Proceeding in the same way, we obtain P for the given example as:
Thus, theP pair are 1,3 and 1,2. From Figure 4 and Remark 1, we can verify that the P pair obtained in the algorithm is the same as that for the given signed network.Figure 4
(a) Given signed networkΣ. (b) Its 2-path signed network.
(a)(b)Remark 3.
Each pairQi,Qi+1 in array Q, for i=1 to l−1, is a pair of vertices in Σ, which have a path of length two between them in Σ. Since they do not form a P pair, they form a positive edge in Σ2 (by Remark 1).


## 2.2.1. Complexity

In Steps 5, 6, and 7, we use three different loops running upton times (number of vertices). Thus, the complexity of this fragment is equal to On3.Next, we use three nested loops in Steps 12, 13, and 15. Again the complexity isOn3.The loops at Step 19 and Step 20 are used for the arrayP and Q with a size of m=l−2 and g=t−2, respectively. Since the maximum number of edges in a network is nn−1/2 and P and Q collects vertices incident to edges, thus m≤nn−1 and g≤nn−1. Therefore, the complexity of this fragment is Onn−1≤On2.Combining the above, the total complexity equalsOn3+On3+On2. Hence, the complexity involved in Algorithm 1 is On3.


## 2.2.2. Implementation of Algorithm

Example 1.
In this example, we are given with a signed network, as shown in Figure4(a), and we find all the P pairs for the given signed network Σ. Let us consider adjacency matrix for the signed network which is given as follows:(2)A=0−1−10−10−11−1−1010110.
In order to detect theP pairs of Σ, we use Algorithm 1 where the inputs are the matrix A and size n=4. The size of array P and Q is initially fixed as n2. After initializing the array P and Q as zero, t=1 and l=1, we enter the first, second, and third loop which run for 1 to 4. The three loops at Steps 5, 6, and 7 are used to obtain two distinct elements Ai,j and Aj,k. Next, in Step 9 we check pair of vertices i,j and j,k if Ai,j=1 and Aj,k=1 or Ai,j=−1 and Aj,k=1 or Ai,j=1 and Aj,k=−1, then i and k enter as an consecutive entry in the array Q. The array Q collects the vertices forming positive 2-paths in Σ. For the above matrix, as we enter the loop, then for i=1,j=2,k=4, we find that A1,2=−1 and A2,4=1. Thus, as t=1, Q1=1 and Q2=4 and t is incremented to t=3. Similarly, after completing all the loops we get Q as follows.
One can note that the number of elements in arrayQ is given by the t−2 (since every time we enter Step 9, t is incremented by 2). In the given example, t=16, and thus size of array Q is 14. Next, we enter loop at Step 13, to find all the edges ij and jk such that Ai,j=−1 and Aj,k=−1. Once such pair is obtained then i and k are collected in Array P as done for array Q. For the given example, array P comes out to be
The size ofP is given by l−2 and in our example l=10. Finally, we compare the elements of P and Q pairwise to find if there are pairs of vertices which is common in both and then we remove these pairs from P. This is done by using two loops one moves from 1 to t−2 (the size of array Q) and the other moves from 1 to l−2 (size of array P). For i=5 and j=5, we see that P5=Q5 and P6=Q6. Therefore, P5=0 and P6=0. Proceeding in the same way, we obtain P for the given example as:
Thus, theP pair are 1,3 and 1,2. From Figure 4 and Remark 1, we can verify that the P pair obtained in the algorithm is the same as that for the given signed network.Figure 4
(a) Given signed networkΣ. (b) Its 2-path signed network.
(a)(b)Remark 3.
Each pairQi,Qi+1 in array Q, for i=1 to l−1, is a pair of vertices in Σ, which have a path of length two between them in Σ. Since they do not form a P pair, they form a positive edge in Σ2 (by Remark 1).


## 2.3. Algorithm to Construct 2-Path Signed Network

Next in Algorithm2, we obtain the 2-path signed network Σ2 for a given signed network Σ. We use the adjacency matrix A of Σ. We use Algorithm 1, to obtain the vertices forming negative edges (collected in array P) and positive edges (collected in array Q) of 2-path signed network. The adjacency matrix of 2-path signed network obtained is saved in matrix B.Algorithm 2: Algorithm to obtain a 2-path signed network for a given signed network.
Input: Adjacency matrix A, dimension n and array P from Algorithm 1.Output: Adjacency matrix B of 2-path signed network.Process:(1)
Enter the ordern and adjacency matrix A of for a given signed network Σ.(2)
fori=1 to ndo(3)
forj=1:ndo(4)
Bi,j=0 5 fort=1:m−1,t=t+2do(5)
if (Pt≠0) then(6)
ifPt=j&&Pt+1=kthen(7)
Bk,j=−1(8)
Bj,k=−1(9)
fort=1:g−1,t=t+2do(10)
ifQt=j&&Qt+1=kthen(11)
Bk,j=1(12)
Bj,k=1


### 2.3.1. Complexity

In Step 2, we use two loops to initialize the matrixB zero, and thus the complexity of these steps is On2.In Step 5, we use a loop which runs up tom−1, m≤nn−1 (from previous algorithm). Thus, the complexity of this step is Onn−1=On2. Similarly, in Step 10, we use a loop which runs up to g−1, g≤nn−1. Again complexity of this step is Onn−1=On2.The total complexity isOn2+On2+On2 = On2.


### 2.3.2. Implementation of the Algorithm

Example 2.
We are given with a signed networkΣ, as shown in Figure 4(a), with the adjacency matrix A as in Example 1. We have to find the adjacency matrix B of the 2-path signed network Σ2. In Steps 2 and 3, we use two loops, each running from 1 to 4 as n=4 and assign zero to all the entries of matrix B. Next, with the help of Algorithm 1, we obtain P as Q as
In Step 5, we enter the loop running uptom=7 for each pair Pt,Pt+1 which saves the vertices forming negative edge in Σ2. As an edge jk is given by entry jth row and kth column and by kth row and jth in the adjacency matrix, for each pair Pt=j and Pt+1=k, Bj,k=Bk,j=−1. Thus, for t=1, B1,3=B3,1=−1, similarly, for t=3B12=B21=−1. Thus, the matrix B after Step 9 is(3)A=0−1−10−1000−10000000.
Next, in Step 10, we enter the loop to find the vertices forming positive edges inΣ2, which is given by pair of vertices in array Q. For t=1, Q1=1,Q2=4 and so B1,4=B1,4=1. After running the loop for g=13, matrix B is given by(4)A=0−1−11−1011−11011110,which is the adjacency matrix for the 2-path signed network Σ2, as shown in Figure 4(b).


## 2.3.1. Complexity

In Step 2, we use two loops to initialize the matrixB zero, and thus the complexity of these steps is On2.In Step 5, we use a loop which runs up tom−1, m≤nn−1 (from previous algorithm). Thus, the complexity of this step is Onn−1=On2. Similarly, in Step 10, we use a loop which runs up to g−1, g≤nn−1. Again complexity of this step is Onn−1=On2.The total complexity isOn2+On2+On2 = On2.


## 2.3.2. Implementation of the Algorithm

Example 2.
We are given with a signed networkΣ, as shown in Figure 4(a), with the adjacency matrix A as in Example 1. We have to find the adjacency matrix B of the 2-path signed network Σ2. In Steps 2 and 3, we use two loops, each running from 1 to 4 as n=4 and assign zero to all the entries of matrix B. Next, with the help of Algorithm 1, we obtain P as Q as
In Step 5, we enter the loop running uptom=7 for each pair Pt,Pt+1 which saves the vertices forming negative edge in Σ2. As an edge jk is given by entry jth row and kth column and by kth row and jth in the adjacency matrix, for each pair Pt=j and Pt+1=k, Bj,k=Bk,j=−1. Thus, for t=1, B1,3=B3,1=−1, similarly, for t=3B12=B21=−1. Thus, the matrix B after Step 9 is(3)A=0−1−10−1000−10000000.
Next, in Step 10, we enter the loop to find the vertices forming positive edges inΣ2, which is given by pair of vertices in array Q. For t=1, Q1=1,Q2=4 and so B1,4=B1,4=1. After running the loop for g=13, matrix B is given by(4)A=0−1−11−1011−11011110,which is the adjacency matrix for the 2-path signed network Σ2, as shown in Figure 4(b).


## 3. Balance in 2-Path Signed Network

### 3.1. Characterization of Balanced 2-Path Signed Network

In this section, we provide with a characterization of balanced 2-path signed network. The characterization helps us to identify the groups in the interference network (2-path signed network) and find the balanced. We refer the following lemma given by Zaslvasky.Lemma 4 (see [54]).
A signed network in which every chordless cycle is positive and is balanced.Theorem 2.
For a signed networkΣ of order n, the following statements are equivalent:(i)
Σ2 is balanced.(ii)
(a)
Each homogeneous cycle inΣ is either positive or is a P cycle of length 4k, for some positive integer k.(b)
Each heterogeneous odd cycle inΣ either does not contain P section or contains even number of P section of even length.(c)
For each heterogeneous even cycle (length greater than 4), the following conditions hold:(c:1)
If it hasP sections of odd length l, then either l≡1mod4 or if l≡1mod4; then, there are even number of such P sections each separated by positive section of even length.(c:2)
If it hasP sections of even length, then there are even number of such P sections each separated by positive section of even length.(d)
For each vertexu in Σ with du≥3,N∗u does not contain any P pairs.Proof.
i⟹ii Let Σ2 be balanced. If a cycle in Σ is a positive homogeneous cycle, then the cycle (or cycles in case the cycle in Σ is of even length) formed in its 2-path signed graph Σ2 will be a positive cycle. Let C be an all-negative cycle (P cycle), with length ≠4k in Σ. Here, the length of C is either odd or 2t, where t is odd. By Lemma 3, the corresponding cycle or cycles formed in Σ2 will be odd length all-negative, since cycle C is a P cycle in Σ. Thus, by Lemma 4, Σ2 is not balanced, which is a contradiction. Hence, Σ does not contain a P cycle with length ≠4k as Σ2 is balanced. Thus, a of ii follows.
Next, let there exist a heterogeneous cycleC1:v1v2…vpv1,p being odd in Σ, with a P section v1v2,…,vk, k being odd. Clearly, the length of P section is even. The cycle C1 in Σ will generate an odd cycle C1′:v1v3,…,vk−2vk,…,vpv2,…,vp−1v1 in Σ2. Now, v1v3,v3v5,…,vk−2vk are odd number of negative edges in C1′ of Σ2 and also v2v4,…,vk−3vk−1 are even number of negative edges in the cycle C1′ of Σ2 (see (b) in Figure 5, here k=3). Thus, the cycle C1′ in Σ2, will be a negative cycle and hence Σ2 is not balanced, which is a contradiction. Similarly, for odd number of such P sections, the signed network Σ2 is unbalanced, whereas if there are even number of such P sections in the cycle of Σ; then, there would be even number of negative edges in the corresponding cycle of Σ2.
Next, let us consider a heterogeneous even cycleC1:1v2,…,vpv1 in Σ, p even and v1v2,…,vl be a P section of odd length l. From Lemma 2, we know that a cycle of even length p in Σ gives rise to two cycles in Σ2 of length p/2 each. Now, the P section v1v2,…,vl would correspond to l−1/2 negative edges in both the cycles, clearly as Σ2 is balanced, that is, each of these cycles have even number of negative edges which is possible if l−1/2 is an even number or there is another negative edge which is due to some other P section in the same cycle Σ. If l−1/2 is even or l≡1mod4, then we are done, if not then we prove that there are even number of such P section. Clearly, l≡1mod4. Let vi,…,vk, where i≠k and i,k∈l+1,l+2,…,p, be another P section of length s, such that s≢1mod4. Then, again as proved above there would be s−1/2 negative edges in the cycles of Σ2. Now, as each cycle has odd number of negative edges in Σ2 due to P sections v1,…,vp and vi,…,vk in Σ, therefore there are now even number of edges in each of the cycles generated by cycle C1 in Σ2, which makes these cycles balanced.
Lastly, letu be a vertex in Σ with degree greater than or equal to 3. If neighborhood N∗u contains exactly one P pair, say v1,v2, then there exist atleast one vertex v3 in N∗u which does not form P pair with vertices v1,v2. Thus, by definition of 2-path, v1v2v3 will be a cycle in Σ2 with exactly one negative edge v1v2. Thus, 2-path signed network is not balanced. Similarly, if neighborhood N∗u contains more than one P pair and there exist atleast one vertex in N∗u which does not form P pair, then again there is a cycle of length three with exactly one negative edge. Next, if all the vertices in N∗u are P pairs, then any three vertices v1,v2,v3 in N∗u give rise to a negative cycle of length three in Σ2 as v1,v2, v2,v3 and v1,v3 are P pairs in N∗u. Thus, again making Σ2 unbalanced, which is a contradiction to our hypothesis. Therefore, no neighborhood of a vertex of degree greater than three in Σ contains a P pair.
ii⟹i Let, if possible, a,b,c, and d hold. Let us consider the neighborhood for each vertex vi in Σ. If the neighborhood consist of a single vertex, then it does not contribute to the edges in Σ2. Next, if the neighborhood contains two vertices say vj,vk, then either vjvk is an edge in Σ2 which is part of a cycle or a tree. If the edge vjvk is part of the tree, then it is balanced by default. Next, if it is part of a cycle in Σ2, then by Lemma 2 and Lemma 3, we know that this cycle in Σ2 is due to a cycle in Σ. If the corresponding cycle in Σ is homogeneous, then by condition a either it is positive or a P cycle of length 4k, k being odd. A positive cycle in Σ gives rise to a positive cycle in Σ2, thus making the cycle balanced, else a cycle of even length greater than 4 in Σ gives rise to two cycles in Σ2 of equal length. Thus, the cycles formed in Σ2 due to the P cycle in Σ are of even length and thus balanced. If the cycle is heterogeneous in Σ, then the following cases arise:(1)
If cycle inΣ is of odd length, then by (b) the cycle either does not contain P section or contains even number of P section of even length. If the cycle does not contain a P section then cycle in Σ2 is also positive hence balanced. Next, if the cycle in Σ contains odd number of P section of even length then the cycle in Σ2 contain even number of negative edges (as an even P section in Σ gives rise to odd negative edges in cycle of Σ2 as the negative even section in Figure 5(b) gives rise to three negative edges 13,35, and 24 in 2-path signed network). Hence, again giving rise to a balanced cycle.(2)
If cycle inΣ is of even length greater than 4, then by (c) either it has P sections of odd length l such that l≡1mod4 and if l≢1mod4 then there are even number of such P sections each separated by positive section of even length or as P sections of even length then there are even number of such P sections each separated by positive section of even length. In both the cases, even number of negative edges appear in both the cycles of Σ2, thus making these cycles balanced.
Next, if the neighborhood ofvi for some i=1 to n contain more than two vertices, they give rise to a clique in Σ2. Now, the negative edges of these cliques are due to the P pairs in each neighborhood but from (d) no neighborhood contains a P pair; thus, all the cliques are positive. Therefore, by virtue of the conditions, all cycles (and cliques) in Σ2 will be positive, and thus by Lemma 4, Σ2 will be balanced.Figure 5
(a) A P section of length three. (b) A P section of length four.
(a)(b)


## 3.1. Characterization of Balanced 2-Path Signed Network

In this section, we provide with a characterization of balanced 2-path signed network. The characterization helps us to identify the groups in the interference network (2-path signed network) and find the balanced. We refer the following lemma given by Zaslvasky.Lemma 4 (see [54]).
A signed network in which every chordless cycle is positive and is balanced.Theorem 2.
For a signed networkΣ of order n, the following statements are equivalent:(i)
Σ2 is balanced.(ii)
(a)
Each homogeneous cycle inΣ is either positive or is a P cycle of length 4k, for some positive integer k.(b)
Each heterogeneous odd cycle inΣ either does not contain P section or contains even number of P section of even length.(c)
For each heterogeneous even cycle (length greater than 4), the following conditions hold:(c:1)
If it hasP sections of odd length l, then either l≡1mod4 or if l≡1mod4; then, there are even number of such P sections each separated by positive section of even length.(c:2)
If it hasP sections of even length, then there are even number of such P sections each separated by positive section of even length.(d)
For each vertexu in Σ with du≥3,N∗u does not contain any P pairs.Proof.
i⟹ii Let Σ2 be balanced. If a cycle in Σ is a positive homogeneous cycle, then the cycle (or cycles in case the cycle in Σ is of even length) formed in its 2-path signed graph Σ2 will be a positive cycle. Let C be an all-negative cycle (P cycle), with length ≠4k in Σ. Here, the length of C is either odd or 2t, where t is odd. By Lemma 3, the corresponding cycle or cycles formed in Σ2 will be odd length all-negative, since cycle C is a P cycle in Σ. Thus, by Lemma 4, Σ2 is not balanced, which is a contradiction. Hence, Σ does not contain a P cycle with length ≠4k as Σ2 is balanced. Thus, a of ii follows.
Next, let there exist a heterogeneous cycleC1:v1v2…vpv1,p being odd in Σ, with a P section v1v2,…,vk, k being odd. Clearly, the length of P section is even. The cycle C1 in Σ will generate an odd cycle C1′:v1v3,…,vk−2vk,…,vpv2,…,vp−1v1 in Σ2. Now, v1v3,v3v5,…,vk−2vk are odd number of negative edges in C1′ of Σ2 and also v2v4,…,vk−3vk−1 are even number of negative edges in the cycle C1′ of Σ2 (see (b) in Figure 5, here k=3). Thus, the cycle C1′ in Σ2, will be a negative cycle and hence Σ2 is not balanced, which is a contradiction. Similarly, for odd number of such P sections, the signed network Σ2 is unbalanced, whereas if there are even number of such P sections in the cycle of Σ; then, there would be even number of negative edges in the corresponding cycle of Σ2.
Next, let us consider a heterogeneous even cycleC1:1v2,…,vpv1 in Σ, p even and v1v2,…,vl be a P section of odd length l. From Lemma 2, we know that a cycle of even length p in Σ gives rise to two cycles in Σ2 of length p/2 each. Now, the P section v1v2,…,vl would correspond to l−1/2 negative edges in both the cycles, clearly as Σ2 is balanced, that is, each of these cycles have even number of negative edges which is possible if l−1/2 is an even number or there is another negative edge which is due to some other P section in the same cycle Σ. If l−1/2 is even or l≡1mod4, then we are done, if not then we prove that there are even number of such P section. Clearly, l≡1mod4. Let vi,…,vk, where i≠k and i,k∈l+1,l+2,…,p, be another P section of length s, such that s≢1mod4. Then, again as proved above there would be s−1/2 negative edges in the cycles of Σ2. Now, as each cycle has odd number of negative edges in Σ2 due to P sections v1,…,vp and vi,…,vk in Σ, therefore there are now even number of edges in each of the cycles generated by cycle C1 in Σ2, which makes these cycles balanced.
Lastly, letu be a vertex in Σ with degree greater than or equal to 3. If neighborhood N∗u contains exactly one P pair, say v1,v2, then there exist atleast one vertex v3 in N∗u which does not form P pair with vertices v1,v2. Thus, by definition of 2-path, v1v2v3 will be a cycle in Σ2 with exactly one negative edge v1v2. Thus, 2-path signed network is not balanced. Similarly, if neighborhood N∗u contains more than one P pair and there exist atleast one vertex in N∗u which does not form P pair, then again there is a cycle of length three with exactly one negative edge. Next, if all the vertices in N∗u are P pairs, then any three vertices v1,v2,v3 in N∗u give rise to a negative cycle of length three in Σ2 as v1,v2, v2,v3 and v1,v3 are P pairs in N∗u. Thus, again making Σ2 unbalanced, which is a contradiction to our hypothesis. Therefore, no neighborhood of a vertex of degree greater than three in Σ contains a P pair.
ii⟹i Let, if possible, a,b,c, and d hold. Let us consider the neighborhood for each vertex vi in Σ. If the neighborhood consist of a single vertex, then it does not contribute to the edges in Σ2. Next, if the neighborhood contains two vertices say vj,vk, then either vjvk is an edge in Σ2 which is part of a cycle or a tree. If the edge vjvk is part of the tree, then it is balanced by default. Next, if it is part of a cycle in Σ2, then by Lemma 2 and Lemma 3, we know that this cycle in Σ2 is due to a cycle in Σ. If the corresponding cycle in Σ is homogeneous, then by condition a either it is positive or a P cycle of length 4k, k being odd. A positive cycle in Σ gives rise to a positive cycle in Σ2, thus making the cycle balanced, else a cycle of even length greater than 4 in Σ gives rise to two cycles in Σ2 of equal length. Thus, the cycles formed in Σ2 due to the P cycle in Σ are of even length and thus balanced. If the cycle is heterogeneous in Σ, then the following cases arise:(1)
If cycle inΣ is of odd length, then by (b) the cycle either does not contain P section or contains even number of P section of even length. If the cycle does not contain a P section then cycle in Σ2 is also positive hence balanced. Next, if the cycle in Σ contains odd number of P section of even length then the cycle in Σ2 contain even number of negative edges (as an even P section in Σ gives rise to odd negative edges in cycle of Σ2 as the negative even section in Figure 5(b) gives rise to three negative edges 13,35, and 24 in 2-path signed network). Hence, again giving rise to a balanced cycle.(2)
If cycle inΣ is of even length greater than 4, then by (c) either it has P sections of odd length l such that l≡1mod4 and if l≢1mod4 then there are even number of such P sections each separated by positive section of even length or as P sections of even length then there are even number of such P sections each separated by positive section of even length. In both the cases, even number of negative edges appear in both the cycles of Σ2, thus making these cycles balanced.
Next, if the neighborhood ofvi for some i=1 to n contain more than two vertices, they give rise to a clique in Σ2. Now, the negative edges of these cliques are due to the P pairs in each neighborhood but from (d) no neighborhood contains a P pair; thus, all the cliques are positive. Therefore, by virtue of the conditions, all cycles (and cliques) in Σ2 will be positive, and thus by Lemma 4, Σ2 will be balanced.Figure 5
(a) A P section of length three. (b) A P section of length four.
(a)(b)


## 4. Clusterability

### 4.1. Clusterability in 2-Path Signed Networks

In this section, we discuss the clusterablity of a 2-path signed network.Lemma 5 (see [55]).
A signed networkΣ is clusterable if and only if Σ contains no cycle with exactly one negative edge.Theorem 3.
For a given signed networkΣ of order n, the following conditions are equivalent:(i)
Σ2 is clusterable.(ii)
For all sequence of verticesv1,v2,…,vr;1≤r≤n in Σ such that v1,v2∈Nt1; v2,v3∈Nt2; … ; v1,vr∈Ntr for some t1,t2,…,tr∈VΣ. If there exist a pair of vertices in sequence vi,vi+1∈Nti having property P, then the sequence has atleast one pair of vertices vl,vl+1∈Ntl,l≠i satisfying property P, for some l, 1≤l≤r.(iii)
(a)
IfΣ contains a heterogeneous cycle, then no even cycle in Σ contains exactly one P section of length <5 and no odd cycle contains exactly one P section of length 2.(b)
Each neighborhood of vertexv in Σ with dv≥3 either does not contain a P pair or all vertices are P pairs.Proof.
i⟹ii Let for a given signed network Σ, Σ2 be clusterable. Then, no cycle in Σ2 has exactly one negative edge. Let v1,v2,…,vr; 1≤r≤n be a sequence of vertices in Σ such that v1,v2∈Nt1; v2,v3∈Nt2; … ; v1,vr∈Ntr for some t1,t2,…,tr∈VΣ. Let vi,vi+1∈Nti be a pair in sequence v1,v2,…,vr; for some r, 1≤r≤n having property P. Now, C:v1v2…vrv1 is a cycle in Σ2, due to the sequence Nt1,…,Ntr in Σ. Clearly, vi,vi+1 will form a single negative edge in cycle C in Σ2, which is not possible. Thus, there is atleast one more pair of vertices vl,vl+1∈Ntl, l≠i satisfying property P.
ii⟹i Let v1,v2,…,vr; 1≤r≤n be an arbitrary sequence of vertices in Σ such that v1,v2∈Nt1; v2,v3∈Nt2; … ; v1,vr∈Ntr for some t1,t2,…,tr∈VΣ. If there exist a pair of vertices vi,vi+1∈Nti for some i having property P, then the sequence has atleast one other pair of vertices vl,vl+1∈Ntl for some l∈1,…,r satisfying property P. This sequence of vertices generates cycles in Σ2 such that no cycle has exactly one negative edge. Thus, by Lemma 5, Σ2 is clusterable.
i⟹iii Let Σ2 be clusterable. To prove that iiia and iiib hold, let, if possible, (a) does not hold. This implies, there exist an even heterogeneous cycle C in Σ of length 2k, with P section of length <5. C will give rise to two cycles C1 and C2 of length k each in Σ2, and clearly, at least one of the cycles will contain exactly one negative edge (see Figure 6), which is a contradiction to the hypothesis by Lemma 5. Next, if there exist an odd heterogeneous cycle with P section of length 2, then it will correspond to a single negative edge in the cycle of Σ2, which is again not possible. Hence, iiia and iiib hold.
Next, we assume thatb in iii does not hold. Let N∗u be a neighborhood of a vertex u in Σ with du≥3 and containing at least one P pair. Let v1 be a vertex in N∗u, which does not form a P pair with any other vertex in N∗u. Clearly, as du≥3, ∃v2,v3 such that v2,v3 is a P pair. The 2-path signed network Σ2, will now contain a cycle v1v2v3v1 with exactly one negative edge v2v3, since each neighborhood Nu gives rise to clique δNu. By Lemma 5, it is a contradiction to the hypothesis, whereas if all vertices in N∗u form P pairs, then all the edges in the corresponding clique will be negative, thus Σ2 remains clusterable.
iii⟹i Assume that condition a and b in iii hold. We have to show that Σ2 is clusterable. By Theorem 1, we know that Σ2 is obtained by taking the union of cliques generated by the neighborhood of vertices of Σ. Thus, each cycle in Σ2 is either due to cliques generated by Nt for t∈VΣ such that Nt≥3 or due to induced cycles in Σ. Now, by condition a, no heterogeneous even cycle in Σ contains exactly one P section of length <5. Thus, each cycle formed in Σ2 has either no negative edge or has more than one negative edge. Also, if no odd cycle in Σ contains exactly one P section of length 2, then its corresponding cycle in Σ2 does not contain exactly one negative edge. From b, it is clear that no clique in Σ2 contains exactly one negative edge as the clique formed here is homogeneous; hence, by Lemma 5Σ2 is clusterable.Figure 6
(a) A P section of length less than 5 in cycleC of Σ. (b) The corresponding P sections in cycle C1 and C2 in Σ2.
(a)(b)


## 4.1. Clusterability in 2-Path Signed Networks

In this section, we discuss the clusterablity of a 2-path signed network.Lemma 5 (see [55]).
A signed networkΣ is clusterable if and only if Σ contains no cycle with exactly one negative edge.Theorem 3.
For a given signed networkΣ of order n, the following conditions are equivalent:(i)
Σ2 is clusterable.(ii)
For all sequence of verticesv1,v2,…,vr;1≤r≤n in Σ such that v1,v2∈Nt1; v2,v3∈Nt2; … ; v1,vr∈Ntr for some t1,t2,…,tr∈VΣ. If there exist a pair of vertices in sequence vi,vi+1∈Nti having property P, then the sequence has atleast one pair of vertices vl,vl+1∈Ntl,l≠i satisfying property P, for some l, 1≤l≤r.(iii)
(a)
IfΣ contains a heterogeneous cycle, then no even cycle in Σ contains exactly one P section of length <5 and no odd cycle contains exactly one P section of length 2.(b)
Each neighborhood of vertexv in Σ with dv≥3 either does not contain a P pair or all vertices are P pairs.Proof.
i⟹ii Let for a given signed network Σ, Σ2 be clusterable. Then, no cycle in Σ2 has exactly one negative edge. Let v1,v2,…,vr; 1≤r≤n be a sequence of vertices in Σ such that v1,v2∈Nt1; v2,v3∈Nt2; … ; v1,vr∈Ntr for some t1,t2,…,tr∈VΣ. Let vi,vi+1∈Nti be a pair in sequence v1,v2,…,vr; for some r, 1≤r≤n having property P. Now, C:v1v2…vrv1 is a cycle in Σ2, due to the sequence Nt1,…,Ntr in Σ. Clearly, vi,vi+1 will form a single negative edge in cycle C in Σ2, which is not possible. Thus, there is atleast one more pair of vertices vl,vl+1∈Ntl, l≠i satisfying property P.
ii⟹i Let v1,v2,…,vr; 1≤r≤n be an arbitrary sequence of vertices in Σ such that v1,v2∈Nt1; v2,v3∈Nt2; … ; v1,vr∈Ntr for some t1,t2,…,tr∈VΣ. If there exist a pair of vertices vi,vi+1∈Nti for some i having property P, then the sequence has atleast one other pair of vertices vl,vl+1∈Ntl for some l∈1,…,r satisfying property P. This sequence of vertices generates cycles in Σ2 such that no cycle has exactly one negative edge. Thus, by Lemma 5, Σ2 is clusterable.
i⟹iii Let Σ2 be clusterable. To prove that iiia and iiib hold, let, if possible, (a) does not hold. This implies, there exist an even heterogeneous cycle C in Σ of length 2k, with P section of length <5. C will give rise to two cycles C1 and C2 of length k each in Σ2, and clearly, at least one of the cycles will contain exactly one negative edge (see Figure 6), which is a contradiction to the hypothesis by Lemma 5. Next, if there exist an odd heterogeneous cycle with P section of length 2, then it will correspond to a single negative edge in the cycle of Σ2, which is again not possible. Hence, iiia and iiib hold.
Next, we assume thatb in iii does not hold. Let N∗u be a neighborhood of a vertex u in Σ with du≥3 and containing at least one P pair. Let v1 be a vertex in N∗u, which does not form a P pair with any other vertex in N∗u. Clearly, as du≥3, ∃v2,v3 such that v2,v3 is a P pair. The 2-path signed network Σ2, will now contain a cycle v1v2v3v1 with exactly one negative edge v2v3, since each neighborhood Nu gives rise to clique δNu. By Lemma 5, it is a contradiction to the hypothesis, whereas if all vertices in N∗u form P pairs, then all the edges in the corresponding clique will be negative, thus Σ2 remains clusterable.
iii⟹i Assume that condition a and b in iii hold. We have to show that Σ2 is clusterable. By Theorem 1, we know that Σ2 is obtained by taking the union of cliques generated by the neighborhood of vertices of Σ. Thus, each cycle in Σ2 is either due to cliques generated by Nt for t∈VΣ such that Nt≥3 or due to induced cycles in Σ. Now, by condition a, no heterogeneous even cycle in Σ contains exactly one P section of length <5. Thus, each cycle formed in Σ2 has either no negative edge or has more than one negative edge. Also, if no odd cycle in Σ contains exactly one P section of length 2, then its corresponding cycle in Σ2 does not contain exactly one negative edge. From b, it is clear that no clique in Σ2 contains exactly one negative edge as the clique formed here is homogeneous; hence, by Lemma 5Σ2 is clusterable.Figure 6
(a) A P section of length less than 5 in cycleC of Σ. (b) The corresponding P sections in cycle C1 and C2 in Σ2.
(a)(b)


## 5. Sign-Regularity

### 5.1. Property of Sign-Regularity in 2-Path Signed Networks

In this section, we establish a characterization of a sign-regular 2-path signed network. Note that(5)ρvi=∪t∈VΣNt:vi∈VΣ,vi=vi,vj∈P∗:vj∈VΣ.Theorem 4.
For a signed networkΣ of order n, Σ2 is sign-regular if and only if(i)
For all verticesvi,vj∈VΣ such that vi∈Nvj, ρvi is identical for every vi∈VΣ(ii)
IfP∗ is collection of all P pairs, then vi is identical for all 1≤i≤nProof.
Necessity. Let for a given signed network Σ, Σ2 be sign-regular. Then, number of positive and negative edges incident to each vertex in Σ2 is identical. Since Σ2 is obtained by taking the union of cliques generated by the neighborhood of vertices of Σ, thus the total number of vertices in each neighborhood containing vi is the same for each vertex vi∈VΣ. Also, ρvi gives the total number of edges incident to a vertex vi,i∈1,…,n. Hence, ρvi is identical ∀vi∈VΣ2. Therefore, i holds. Since P∗ consists of all pair of vertices satisfying property P, hence number of negative edges incident to each vertex in Σ2 must be equal. Thus, the vertex vi appearing in the number of P pairs in P∗, vi is the same for every i≤i≤n.
Sufficiency. Let i and ii hold. Now, i suggests that, for all the vertices vi in VΣ such that vi∈Nvj, the union of all these neighborhoods which gives the total vertices adjacent to vi in Σ2 have the same cardinality. Thus, each vertex in Σ2 is adjacent to the same number of vertices. Next, we know that the elements of P∗ generate all the negative edges of Σ2 and vi gives the number of negative edges incident to vi in Σ2. By (ii), the cardinality vi is the same for each vertex vi,i=1,…,n. Thus, the number of negative edges incident to vi is the same for each i=1 to n. Since the number of total edges and negative edges incident to vertex vi is the same for each i, the number of positive edges will also be same. Therefore, Σ2 is sign-regular.


### 5.2. Algorithm to Detect if 2-Path Signed Network of a Signed Network Is Sign-Regular

Algorithm3 detects if, for a given signed network Σ, its 2-path Σ2 is sign-regular, by using results of Theorem 4. Consider the adjacency matrix A and its order n as input. The vector countrow gives the number of nonzero elements in each row (degree of the vertices). The array count gives the number of edges for each vertex v present in some neighborhood of a vertex u. Also, vector count1 counts the number of negative edges in Σ2 for each vertex u.Algorithm 3: Algorithm to check sign-regularity of 2-path signed network.
Input: Adjacency matrix A of Σ, number of vertices n and array P from Algorithm 1.Output: Whether the 2-path of a given network is sign-reglar or not.Process:(1)
Enter the adjacency matrixA with elements Ai,j for a given signed network Σ along with the order n of signed network Σ.(2)
h=1;(3)
fori=1:ndo(4)
counti=0;(5)
count1i=0;(6)
countrowi=0;(7)
fori=1:ndo(8)
forj=1:ndo(9)
if (Ai,j≠0) then(10)
countrowi=countrowi+1;(11)
fori=0 to ndo(12)
forj=1:ndo(13)
if (Ai,j≠0) then(14)
countj=countj+countrowi−1;(15)
fori=1:ndo(16)
forj=1:ndo(17)
ifcounti≠countjthen(18)
Print The 2-path network is not regular.(19)
h = 0; break;(20)
fori=1:ndo(21)
forj=1:ldo(22)
ifi=Pjdo(23)
count1i=count1i+1.(24)
fori=1:ndo(25)
forj=1:ndo(26)
ifcount1i≠count1jthen(27)
Print “The two path network is not regular.”(28)
h = 0;(29)
break;(30)
if (h≠0) then(31)
Print “The network is sign-regular.”


#### 5.2.1. Complexity

From Steps 3 to 6, initialization of the vector arrays uses a single loop which runs upton. Thus, the complexity of these steps =On.In Steps 7 and 8, two loops are used upto Step 10. Also, at Steps 11, 15, and 24, again two loops running upton are used independent of each other. Thus, they have combined complexity =On2.In Step 21, theP pairs are collected, and we know that the complexity of this step is of order n3. Finally, the two loops in Steps 20 and 21 go upto n and l, repectively. Thus, the complexity of this step =Onl. Total complexity =On+On2+On3+Onl=On3.


#### 5.2.2. Implementation of Algorithm

Example 3.
In this example, we implement Algorithm3, for a signed network, as shown Figure 4(a). We want to check whether, for a given signed network, its corresponding 2-path signed network is sign-regular. This is done by the adjacency matrix (as in Example 1) of the given signed network Σ. Now, in the given signed network, n = 4, so the vector arrays count and count1 are initialized as zero along with variable h which is initialized as 1. After we enter the loop at Step 7 and Step 8, we fetch each nonzero value of the matrix. For i = 1 and j=2count2=1 (as 2 and 3 are in the neighborhood of 1 and count2=0+2−1) and count3=1. Next, for i=2count1=0+3−1=2, count3=3 and count4=2. Similarly, moving further, when i = 3, we get count1=2+3−1=4,count2=1+3−1=3, and count4=2+3−1=4. For i = 4, count2=4 and count3=4. In Step 14, we check that if there exist i, j, such that count1i≠count1j, but since this is not true we move to Step 20 and collect all P pairs. Next, in Step 21, we check whether the number of negative edges incident to each vertex is identical for all the vertices. We count the number of appearance of each vertex in array P of Algorithm 1; this is done by array count1 as P is the following:
Thus,count11=2,count2=1,count3=1, and count4=0. Next, in Step 26, we check these entries of array count1 and initially find that count11≠count2. Hence, the number of negative edges incident to vertex 1 and 2 is not the same; thus, the 2-path signed network is not sign-regular. The same is clear from Figure 4(b), hence the proof.


## 5.1. Property of Sign-Regularity in 2-Path Signed Networks

In this section, we establish a characterization of a sign-regular 2-path signed network. Note that(5)ρvi=∪t∈VΣNt:vi∈VΣ,vi=vi,vj∈P∗:vj∈VΣ.Theorem 4.
For a signed networkΣ of order n, Σ2 is sign-regular if and only if(i)
For all verticesvi,vj∈VΣ such that vi∈Nvj, ρvi is identical for every vi∈VΣ(ii)
IfP∗ is collection of all P pairs, then vi is identical for all 1≤i≤nProof.
Necessity. Let for a given signed network Σ, Σ2 be sign-regular. Then, number of positive and negative edges incident to each vertex in Σ2 is identical. Since Σ2 is obtained by taking the union of cliques generated by the neighborhood of vertices of Σ, thus the total number of vertices in each neighborhood containing vi is the same for each vertex vi∈VΣ. Also, ρvi gives the total number of edges incident to a vertex vi,i∈1,…,n. Hence, ρvi is identical ∀vi∈VΣ2. Therefore, i holds. Since P∗ consists of all pair of vertices satisfying property P, hence number of negative edges incident to each vertex in Σ2 must be equal. Thus, the vertex vi appearing in the number of P pairs in P∗, vi is the same for every i≤i≤n.
Sufficiency. Let i and ii hold. Now, i suggests that, for all the vertices vi in VΣ such that vi∈Nvj, the union of all these neighborhoods which gives the total vertices adjacent to vi in Σ2 have the same cardinality. Thus, each vertex in Σ2 is adjacent to the same number of vertices. Next, we know that the elements of P∗ generate all the negative edges of Σ2 and vi gives the number of negative edges incident to vi in Σ2. By (ii), the cardinality vi is the same for each vertex vi,i=1,…,n. Thus, the number of negative edges incident to vi is the same for each i=1 to n. Since the number of total edges and negative edges incident to vertex vi is the same for each i, the number of positive edges will also be same. Therefore, Σ2 is sign-regular.


## 5.2. Algorithm to Detect if 2-Path Signed Network of a Signed Network Is Sign-Regular

Algorithm3 detects if, for a given signed network Σ, its 2-path Σ2 is sign-regular, by using results of Theorem 4. Consider the adjacency matrix A and its order n as input. The vector countrow gives the number of nonzero elements in each row (degree of the vertices). The array count gives the number of edges for each vertex v present in some neighborhood of a vertex u. Also, vector count1 counts the number of negative edges in Σ2 for each vertex u.Algorithm 3: Algorithm to check sign-regularity of 2-path signed network.
Input: Adjacency matrix A of Σ, number of vertices n and array P from Algorithm 1.Output: Whether the 2-path of a given network is sign-reglar or not.Process:(1)
Enter the adjacency matrixA with elements Ai,j for a given signed network Σ along with the order n of signed network Σ.(2)
h=1;(3)
fori=1:ndo(4)
counti=0;(5)
count1i=0;(6)
countrowi=0;(7)
fori=1:ndo(8)
forj=1:ndo(9)
if (Ai,j≠0) then(10)
countrowi=countrowi+1;(11)
fori=0 to ndo(12)
forj=1:ndo(13)
if (Ai,j≠0) then(14)
countj=countj+countrowi−1;(15)
fori=1:ndo(16)
forj=1:ndo(17)
ifcounti≠countjthen(18)
Print The 2-path network is not regular.(19)
h = 0; break;(20)
fori=1:ndo(21)
forj=1:ldo(22)
ifi=Pjdo(23)
count1i=count1i+1.(24)
fori=1:ndo(25)
forj=1:ndo(26)
ifcount1i≠count1jthen(27)
Print “The two path network is not regular.”(28)
h = 0;(29)
break;(30)
if (h≠0) then(31)
Print “The network is sign-regular.”


### 5.2.1. Complexity

From Steps 3 to 6, initialization of the vector arrays uses a single loop which runs upton. Thus, the complexity of these steps =On.In Steps 7 and 8, two loops are used upto Step 10. Also, at Steps 11, 15, and 24, again two loops running upton are used independent of each other. Thus, they have combined complexity =On2.In Step 21, theP pairs are collected, and we know that the complexity of this step is of order n3. Finally, the two loops in Steps 20 and 21 go upto n and l, repectively. Thus, the complexity of this step =Onl. Total complexity =On+On2+On3+Onl=On3.


### 5.2.2. Implementation of Algorithm

Example 3.
In this example, we implement Algorithm3, for a signed network, as shown Figure 4(a). We want to check whether, for a given signed network, its corresponding 2-path signed network is sign-regular. This is done by the adjacency matrix (as in Example 1) of the given signed network Σ. Now, in the given signed network, n = 4, so the vector arrays count and count1 are initialized as zero along with variable h which is initialized as 1. After we enter the loop at Step 7 and Step 8, we fetch each nonzero value of the matrix. For i = 1 and j=2count2=1 (as 2 and 3 are in the neighborhood of 1 and count2=0+2−1) and count3=1. Next, for i=2count1=0+3−1=2, count3=3 and count4=2. Similarly, moving further, when i = 3, we get count1=2+3−1=4,count2=1+3−1=3, and count4=2+3−1=4. For i = 4, count2=4 and count3=4. In Step 14, we check that if there exist i, j, such that count1i≠count1j, but since this is not true we move to Step 20 and collect all P pairs. Next, in Step 21, we check whether the number of negative edges incident to each vertex is identical for all the vertices. We count the number of appearance of each vertex in array P of Algorithm 1; this is done by array count1 as P is the following:
Thus,count11=2,count2=1,count3=1, and count4=0. Next, in Step 26, we check these entries of array count1 and initially find that count11≠count2. Hence, the number of negative edges incident to vertex 1 and 2 is not the same; thus, the 2-path signed network is not sign-regular. The same is clear from Figure 4(b), hence the proof.


## 5.2.1. Complexity

From Steps 3 to 6, initialization of the vector arrays uses a single loop which runs upton. Thus, the complexity of these steps =On.In Steps 7 and 8, two loops are used upto Step 10. Also, at Steps 11, 15, and 24, again two loops running upton are used independent of each other. Thus, they have combined complexity =On2.In Step 21, theP pairs are collected, and we know that the complexity of this step is of order n3. Finally, the two loops in Steps 20 and 21 go upto n and l, repectively. Thus, the complexity of this step =Onl. Total complexity =On+On2+On3+Onl=On3.


## 5.2.2. Implementation of Algorithm

Example 3.
In this example, we implement Algorithm3, for a signed network, as shown Figure 4(a). We want to check whether, for a given signed network, its corresponding 2-path signed network is sign-regular. This is done by the adjacency matrix (as in Example 1) of the given signed network Σ. Now, in the given signed network, n = 4, so the vector arrays count and count1 are initialized as zero along with variable h which is initialized as 1. After we enter the loop at Step 7 and Step 8, we fetch each nonzero value of the matrix. For i = 1 and j=2count2=1 (as 2 and 3 are in the neighborhood of 1 and count2=0+2−1) and count3=1. Next, for i=2count1=0+3−1=2, count3=3 and count4=2. Similarly, moving further, when i = 3, we get count1=2+3−1=4,count2=1+3−1=3, and count4=2+3−1=4. For i = 4, count2=4 and count3=4. In Step 14, we check that if there exist i, j, such that count1i≠count1j, but since this is not true we move to Step 20 and collect all P pairs. Next, in Step 21, we check whether the number of negative edges incident to each vertex is identical for all the vertices. We count the number of appearance of each vertex in array P of Algorithm 1; this is done by array count1 as P is the following:
Thus,count11=2,count2=1,count3=1, and count4=0. Next, in Step 26, we check these entries of array count1 and initially find that count11≠count2. Hence, the number of negative edges incident to vertex 1 and 2 is not the same; thus, the 2-path signed network is not sign-regular. The same is clear from Figure 4(b), hence the proof.


## 6. Conclusion

In this paper, we studied various characterizations of 2-path signed networks and other allied properties such as balancedness, clusterability, and sign-regularity. We designed a model using the 2-path signed networks on radio frequency interference. We assumed that the vertices represented channel/stations and transmission between them was represented by edges. The negative sign in signed network Σ was given to the edgeuv if the transmission from u and v takes place at the same time and frequency, otherwise uv was given a positive sign. The paper explored both theoretic and applicable aspect of 2-path signed networks. In our work, we not only focused on the characterization and other results due to the signing but also the algorithms which can be readily used in real world problems.



---

*Source: 1028941-2020-10-31.xml*