Mesoscopic analysis of online social networks: The role of negative ties

A class of networks are those with both positive and negative links. In this manuscript, we studied the interplay between positive and negative ties on mesoscopic level of these networks, i.e., their community structure. A community is considered as a tightly interconnected group of actors; therefore, it does not borrow any assumption from balance theory and merely uses the well-known assumption in the community detection literature. We found that if one detects the communities based on only positive relations (by ignoring the negative ones), the majority of negative relations are already placed between the communities. In other words, negative ties do not have a major role in community formation of signed networks. Moreover, regarding the internal negative ties, we proved that most unbalanced communities are maximally balanced, and hence they cannot be partitioned into $k$ nonempty sub-clusters with higher balancedness $\left(k\ge 2\right)$. Furthermore, we showed that although the mediator triad $++-$ (hostile-mediator-hostile) is underrepresented, it constitutes a considerable portion of triadic relations among communities. Hence, mediator triads should not be ignored by community detection and clustering algorithms. As a result, if one uses a clustering algorithm that operates merely based on social balance, mesoscopic structure of signed networks significantly remains hidden.

Figure 1

Different types of triadic signed relations between three actors. In structural balance, triads $A$ and $C$ are balanced, and $B$ and $D$ are unbalanced. In general structural balance, only triad B is unbalanced and the others are balanced.

Figure 2

“$++-$” relation (hostile-mediator-hostile) between three clusters. The value of $F\left(G\right)$ is reduced by $P1$, if mediator cluster $M$ is merged into the closest friend $C1$.

Figure 3

(a) Result of fitting a GB model based on general structural balance, which merges $C1$ and $M$ to get a lower frustration. (b) Result of fitting a GB model based on relaxed structural balance, which allows off-diagonal positive blocks similar to the output of signed community detection methods, if one restricts the clusters to be internally cohesive.

Figure 4

All three two-clusterings result in $F_2(G,C)=0$. (a) Cluster and community are consistent with each other. (b) Clusters are not communities. (c) Two distinguishable communities get clustered into $C1$.

Figure 5

Observed statistics (dashed blue line) in Slashdot dataset as compared to those of 200 realizations from $M_r\left(G\right)$ for different values of $r$. In all cases, $p$-value is less than 0.001.

Figure 6

Observed statistics (dashed blue line) in Epinions dataset as compared to those of 200 realizations from $M_r\left(G\right)$ for different values of $r$. In all cases, $p$-value is less than 0.001.

Figure 7

(a) Information of negative edge is equal to $-{\text{log}}_2\left(1\right)=0$, which also means $F_1\left(G\right)\le F_2\left(G\right)$. (b) Information of negative edges is equal to $-{\text{log}}_2\left(\frac{4}{5}\right)=0.322$.

Figure 8

Constructed community network of Slashdot. All communities are internally balanced. The size of each community is proportional to the number of its members. Communities with higher ratio of negative relations are closer to yellow color (lighter gray). Some of the larger aggressive communities, which are the enemies of the majority of their neighbors, have been placed on the top of the network. These communities indicate a meaningful group of people that are allies, and troll the neighbor communities.