Graph theory as the mathematical language for systems modeling has a vast application in various fields. Thus, different types of graph models have been extended and applied for specific purposes in different types of systems. For example, the relationship of elements can be considered without weight or weighted, directional or without direction, simple or with the possibility of multiple relations, and so on. To model many systems, we encounter the concept of signed relations, positive or negative, between system components, such as friendship or enmity in social networks, positive or negative relationships between agents in different types of multi-agent systems, repulsion or attraction between particles in an electromagnetic system, activation or inhibition relationship in gene regulation networks, synaptic relations in neural networks, etc. Hence, the mathematical concepts and theorems of signed graphs are widely used in various fields of science and engineering such as physics, control engineering, biological systems and bioinformatics, social networks, and ecosystem science (Saberi et al. 2021; Ehsani 2020; Saiz et al. 2017; Aref 2019; Lin et al. 2013; Shahriari and Jalili 2014; Aoyama et al. 2017).

The basic idea of the concept of structural balance in signed graphs originated from Hider's research in psychology: any triadic relationship in which the product of signs of the links is negative would be the source of challenge and inconsistency in the system and it is considered as an imbalanced triad (Heider 1946).

Cartwright and Harari extended this concept and provided a mathematical framework for the analysis of signed graphs and structural balance. A signed graph is said to be balanced if there is no negative triad or cycle in it, or equivalently, for every pair of nodes, all paths between them have the same sign. Under this condition, the graph can be partitioned into two parts such that the edges inside each part are positive and the edges between them are negative (Catwright and Harary 1956). The sign of a triad, or a cycle or a path in the above-mentioned propositions, means the product sign of all edges in the triad, the cycle, or the path. Therefore, the structural balance in a signed graph naturally corresponds to partitioning the graph into two parts.

Whether a signed graph is balanced or not, is a simple problem and belongs to class P, however, real-world signed networks rarely satisfy balance conditions perfectly. Hence, several indices have been presented to measure how far is a signed graph from the balance condition. An index, the degree of balance proposed by Cartwright and Harari, is equal to the proportion of the balanced cycles in a signed graph (Catwright and Harary 1956). It can be proved that the number of cycles in a graph grows exponentially with its size. A more significant index, known as the line index of balance defined by Harari and equals the smallest number of edges whose removal from the signed graph, results in balance (Harary 1959). The computation of this index corresponds to partitioning the graph into two subgraphs such that the total number of edges that violate the balance condition is minimal. Another index corresponding exactly to the line index of balance, introduced in the context of the Ising spin glass model in physics, is the frustration index (Barahona 1982). To explain this index, consider a spin assignment in a signed graph, which means the value of \(1\) or \(-1\) is assigned to the nodes of the graph. An edge is called satisfied if it is positive and both endpoints have the same value, or if it is negative and the endpoints have opposite values, otherwise it is called frustrated. Then, the Hamiltonian energy function for a spin system is defined in Eq. 1, where \(A=\left[{a}_{ij}\right]\) is the adjacency matrix of the signed graph, and \({\text{S}}_{\text{i}}\) and \({\text{S}}_{\text{i}}\) are spin values of the nodes \({\text{S}}_{\text{i}}\) and \({\text{S}}_{\text{i}}\) respectively.

$$H=-\sum {a}_{ij}{S}_{i}{S}_{j}$$

1

The frustration index is defined as the minimum number of frustrated edges in a signed graph over all possible spin assignment schemes. The minimum energy of a spin system corresponds to this spin assignment. As the system structure gets further from the balance condition, the frustration index increases and so does the Hamiltonian energy of the system. These concepts are extended in the field of monotone systems and near monotone systems and applied in control engineering and biomedical networks (Sontag 2006; Iacano and Altafini 2010).

The computation of the line index of balance or frustration index corresponds to partitioning the graph into two subgraphs such that the total number of edges that violate the balance condition is minimized. This problem can be reduced from the Max-Cut problem which is known as an NP-hard problem. Therefore, partitioning a signed graph into two subgraphs such that the total number of edges that violate the balance condition is minimized, as an optimization problem belongs to the NP-hard class.

However, detecting near-balanced partitions as the main sub-systems and the relations between them can be considered a basic tool for the analysis function and dynamics of complex networks. Since this problem has wide applications in the analysis of different systems in various fields of science and engineering and given that this problem belongs to the NP-Hard class, many approaches have been developed for it. Some earlier methods, based on block modeling and generalized block modeling techniques in linear algebra, were first developed by Doreian and Mrvar (Doriean and Mrvar 1996; Doreian 2008; Arinik 2021). Another category of methods develops spectral graph concepts for signed graphs analysis and clustering (Kunegis et al. 2010; Knyazev 2018). In recent years many algorithms have been presented for this problem based on different metaheuristics algorithms (Brusco and Doreian 2019; Che et al. 2020; Levorato et al. 2015). Also, some recent studies extend exact methods such as integer programming to solve the problem in specific conditions (Aref et al. 2018). Many other studies have tried to extend traditional concepts in the field of community detection algorithms to signed networks. For example, modularity, as a basic concept presented in the Louvain method for community detection, has been extended and applied to signed networks (Zhuo et al. 2019).

Nevertheless, many methods ignore negative links and partition the graph considering only positive edges. Though these methods present good solutions for some real networks, they are not suitable for many conditions due to the importance of negative links in the network structure. In fact, negative links have a major role in the dynamism and function of signed networks and much research deal with this issue. Also, the important role of positive links between two opposite parts in information diffusion and system dynamics has been considered in some studies (Kaur and Singh 2016; Everett and Borgatti 2014; Ehsani and Sepehri 2014). Considering these aspects, we present a simple and powerful algorithm for signed graph partitioning, detecting the negative links connecting two parts based on their role in the global structural balance. We further extend some measures in order to analyze positive and negative links' structural properties and apply them to some benchmark network datasets.