Narrow Results

The unsigned graphs containing positive links only, have been analyzed fruitfully. However, the physical relations behind complex networks are dissimilar. We often encounter the signed networks that have both positive and negative links as well. It is very important to study the characteristics of complex networks and predict individual attitudes by analyzing the attitudes of individuals and their neighbors, which can divide individuals into different clusters or communities. To detect the clusters in signed networks, first, a modularity function for signed networks is proposed on the basis of the combination of positive and negative part. Then, a new graph clustering algorithm for signed graphs has also been proposed based on CNM algorithm, which has high efficiency. Finally, the algorithm has been applied on both artificial and the real networks. The results show that the proposed method has been able to achieve near-perfect solution, which is suitable for multiple types real networks.

In signed networks, negative edges represent negative relationships; the increase or gathering of negative interpersonal relationships can lead to social turmoil, which will affect the spreading of diseases or information. Therefore, it is significant to study the impact of the proportion and configuration of negative edges on spreading. In this paper, to study the impact of negative relationships on spreading, we propose a heterogeneous spreading model using signed networks. In this model, we use the balance of the local structure to quantify the probability of contact between individuals, making the contacts heterogeneous. We then examine the impact of negative edges on spreading using numerical simulations. We find that the balance of the network and the spreading coverage (i.e. outbreak size) gradually decrease with the proportion of negative edges. Compared with preference configurations (in which negative signs are placed on edges that have an important impact on spreading), a random configuration (in which negative signs are placed on random edges) has a suppressive effect on spreading. This provides information for epidemic prevention. Finally, we find that there are two important factors — contact probability and spreading paths — that could explain the observed spreading phenomena.

Community detection in signed networks has become a research hotspot in the area of network science recently. Since the classical problem has great significance for theoretical analysis and practical application, many heuristics or metaheuristics have been presented. Despite some progress and results that have been achieved, it remains an open challenge to identify community structure in large signed networks. In this paper, we propose a simple and effective iterated local search algorithm coupled with a powerful local search mechanism to solve the community detection problem. Due to the limitation of modularity in resolution, the modularity density criterion is adopted to find communities in signed networks. Extensive experiments have been conducted on synthetic and real-world networks. The statistical analyses demonstrate that the proposed algorithm can provide high-quality solutions compared to the state-of-the-art algorithms.

The signed network depicts individual cooperative or hostile attitude in a system. It is very important to study the characteristics of complex networks and predict individual attitudes by analyzing the attitudes of individuals and their neighbors, which can divide individuals into different modules or communities. To detect the modules in signed networks, first, a modularity function for signed networks is utilized on the basis of the existing modularity function. Then, a new module detection algorithm for signed networks has also been put forward, which has high efficiency. Finally, the algorithm has been applied on both artificial and real networks. The results show that the number of modules given by our proposed algorithm is consistent with that of the number of actual modules.

Recently, problems related to structural balance have received widespread attention in the research fields of signed networks, such as signed network partition, community detection and correlation clustering. Structural balance problems aim to find a partition of a signed network such that the frustration index, the sum of positive edges between subsets and negative edges within subsets, is minimized, which is known to be nondeterministic polynomial-time (NP)-complete and remains an open challenge. Many heuristic and meta-heuristic algorithms are developed to minimize the frustration index. However, most extant algorithms require quite a few parameters and are not efficient enough for large signed networks. In this study, we present a simple and effective iterated greedy (IG) algorithm for solving the structural balance problems with the objective of frustration minimization. In the algorithm, a constructive greedy heuristic is proposed to generate and reconstruct solutions to the problem with high efficiency. A two-stage local search procedure is designed to exploit the search space at different levels of granularity. An adaptive destruction method is developed to enhance the exploitation ability of the algorithm in the early stage and maintain the exploration ability later. Additionally, two acceleration methods are proposed to help the algorithm get a better performance in large signed networks. The experimental results indicate that the proposed IG algorithm outperforms other meta-heuristics in the literature especially in terms of the computational time.

The opinion spreading process can be modeled as the spread of an epidemic through a network, which assumes homogeneous relationships between individuals. However, positive and negative relationships in signed networks play different roles in the opinion spreading process, following the general rule that the same opinion will diffuse through friends, while the opposite opinion will likely emerge out of interactions between enemies. In order to explore opinion spreading behavior in signed networks, we proposed a simple opinion spreading model based on the susceptible-infected-recovered (SIR) epidemic model. Under the assumption of homogeneous mixing, we also analyzed the phase transition of opinion spreading in signed networks and found that critical spreading rates were closely related to the fraction of positive relationships in signed networks. Finally, we confirmed the correctness of our solutions using numerical simulations of the opinion spreading model in signed networks.

Over the past few decades, the study of epidemic propagation has caught widespread attention from many areas. The field of graphs contains a wide body of research, yet only a few studies explore epidemic propagation’s dynamics in “signed” networks. Motivated by this problem, in this paper we propose a new epidemic propagation model for signed networks, denoted as S-SIS. To explain our analysis, we utilized the mean field theory to demonstrate the theoretical results. When we compare epidemic propagation through negative links to those only having positive links, we find that a higher proportion of infected nodes actually spreads at a relatively small infection rate. It is also found that when the infection rate is higher than a certain value, the overall spreading in a signed network begins showing signs of suppression. Finally, in order to verify our findings, we apply the S-SIS model on Erdös–Rényi random network and scale-free network, and the simulation results is well consist with the theoretical analysis.

An approach to detect communities in signed networks that combines Genetic Algorithms and local search is proposed. The method optimizes the concepts of modularity and frustration in order to find network divisions far from random partitions, and having positive and dense intra-connections, while sparse and negative inter-connections. A local search strategy to improve the network division is performed by moving nodes having positive connections with nodes of other communities, to neighboring communities, provided that there is an increase in signed modularity. An extensive experimental evaluation on randomly generated networks for which the ground-truth division is known proves that the method is competitive with a state-of-art approach, and it is capable to find accurate solutions. Moreover, a comparison on a real life signed network shows that our approach obtains communities that minimize the positive inter-connections and maximize the negative intra-connections better than the contestant methods.

Graph representation learning (GRL) has become a prominent tool for furthering the understanding of complex networks providing tools for network embedding, link prediction, and node classification. In this paper, we propose the Hybrid Membership-Latent Distance Model (HM-LDM) by exploring how a Latent Distance Model (LDM) can be constrained to a latent simplex. By controlling the edge lengths of the corners of the simplex, the volume of the latent space can be systematically controlled. Thereby communities are revealed as the space becomes more constrained, with hard memberships being recovered as the simplex volume goes to zero. We further explore a recent likelihood formulation for signed networks utilizing the Skellam distribution to account for signed weighted networks and extend the HM-LDM to the signed Hybrid Membership-Latent Distance Model (sHM-LDM). Importantly, the induced likelihood function explicitly attracts nodes with positive links and deters nodes having negative interactions. We demonstrate the utility of HM-LDM and sHM-LDM on several real networks. We find that the procedures successfully identify prominent distinct structures, as well as how nodes relate to the extracted aspects providing favorable performances in terms of link prediction when compared to prominent baselines. Furthermore, the learned soft memberships enable easily interpretable network visualizations highlighting distinct patterns.

Decision-making processes often involve voting. Human interactions with exogenous entities such as legislations or products can be effectively modeled as two-mode (bipartite) signed networks — where people can either vote positively, negatively, or abstain from voting on the entities. Detecting communities in such networks could help us understand underlying properties: for example ideological camps or consumer preferences. While community detection is an established practice separately for bipartite and signed networks, it remains largely unexplored in the case of bipartite signed networks. In this paper, we systematically evaluate the efficacy of community detection methods on projected bipartite signed networks using a synthetic benchmark and real-world datasets. Our findings reveal that when no communities are present in the data, these methods often recover spurious user communities. When communities are present, the algorithms exhibit promising performance, although their performance is highly susceptible to parameter choice. This indicates that researchers using community detection methods in the context of bipartite signed networks should not take the communities found at face value: it is essential to assess the robustness of parameter choices or perform domain-specific external validation.