Source-linked AI summary
The Slashdot Zoo: Mining a Social Network with Negative Edges
Jérôme Kunegis, Andreas Lommatzsch, Christian Bauckhage
TL;DR
The paper asks how social-network analysis can represent relationships with negative edge weights, using Slashdot’s friend-and-foe network as its setting. It develops signed global, node, and link measures and finds multiplicative transitivity, enabling algebraic analysis that reveals facts unavailable to unsigned techniques.
Problem
Social-network methods generally restrict edge weights to positive values, leaving relationships such as distrust and dislike inadequately represented.
Method
The paper adapts network-analysis measures for signed edges across global, node, and link levels, using multiplicative transitivity to analyze Slashdot’s friend-and-foe graph.
Results
The three-level analysis shows that the Slashdot Zoo exhibits multiplicative transitivity and that signed methods apply to large social networks.
Takeaways & Limitations
Signed network analysis reveals facts in large social networks that common unsigned techniques cannot uncover.
Takeaways & Limitations
PageRank cannot use negative edge weights, so its resulting rank indicates centrality rather than popularity and does not distinguish friend from foe links.
Abstract
from arXiv · showhide
We analyse the corpus of user relationships of the Slashdot technology news site. The data was collected from the Slashdot Zoo feature where users of the website can tag other users as friends and foes, providing positive and negative endorsements. We adapt social network analysis techniques to the problem of negative edge weights. In particular, we consider signed variants of global network characteristics such as the clustering coefficient, node-level characteristics such as centrality and popularity measures, and link-level characteristics such as distances and similarity measures. We evaluate these measures on the task of identifying unpopular users, as well as on the task of predicting the sign of links and show that the network exhibits multiplicative transitivity which allows algebraic methods based on matrix multiplication to be used. We compare our methods to traditional methods which are only suitable for positively weighted edges.
1. INTRODUCTION
The paper addresses social-network analysis when relationships carry negative as well as positive weights. It studies signed network measures at global, node, and edge levels, using multiplicative transitivity to analyze Slashdot relationships.
- Slashdot’s Zoo lets users tag others as friends or foes, providing both positive and negative social endorsements.
- Slashdot provides an early online social-networking setting that allows users to rate others negatively, unlike most popular social-networking services.
- The paper systematically studies signed network-analysis methods at global, node, and edge levels.It examines signed clustering, popularity and centrality, and similarity measures for signed-link prediction.
- The evaluations target identifying unpopular users and predicting the signs of links.
- Multiplicative transitivity models signed paths through the rule that the enemy of my enemy is my friend.The authors evaluate whether this rule holds in the Slashdot Zoo and use it to motivate algebraic methods.
2. RELATED WORK
Prior work largely treats social networks as unsigned or uses negative links for specialized tasks. This paper instead analyzes positive and negative relationships together in one weighted graph and compares signed methods with existing approaches.
- Most web-based social-network analysis uses unweighted edges or weights restricted to positive values.
- Some prior work models multiple relationship types with separate graphs, whereas this paper analyzes all edges in one weighted graph.
- Community-discovery research uses negative edges to separate clusters rather than to measure popularity or similarity.
- Trust-network research mainly defines global trust measures using path lengths or PageRank, which the paper compares with its techniques.The paper reports that these approaches yield inferior results.
- Unsigned link prediction, distance, similarity, spectral, and graph-kernel methods provide the main methodological background.
- Signed Laplacian kernels and positive-edge centrality measures had been studied, but related signed applications included undirected collaborative filtering settings.
3. THE SLASHDOT ZOO
The Slashdot Zoo is a large directed corpus of positive and negative user endorsements collected without endorsement timestamps. Its degree structure follows a power law, and distance statistics indicate a small-world network.
- The corpus contains 77,985 users and 510,157 links, with each link recording an endorsing user, a recipient, and a friend or foe sign.No endorsement creation dates are available.
- Users can also be described as fans of their friends and freaks of their foes.
- The graph visualization uses green friend edges and red foe edges and is centered on CmdrTaco, the founder of Slashdot and an active editor.
- The corpus was retrieved between May and October 2008, so it is not a true network snapshot and may contain anomalies.Unknown tag dates make it possible for some users to exceed the usual friend-or-foe limits.
- 3.1 Definitions: The adjacency matrix A uses +1 for friend endorsements, −1 for foe endorsements, and 0 otherwise; it is sparse, square, and asymmetric.
- 3.2 Statistics: The degree distribution follows a power law, with the 200-friend-and-foe limit visible in the logarithmic plot.
- 3.2 Statistics: Average node distance is lower than in a same-size random graph, supporting the conclusion that the Slashdot Zoo exhibits the small-world phenomenon.The distance calculations ignore edge direction and sign.
4. CLUSTERING COEFFICIENT
This section extends clustering coefficients to signed and directed networks to measure whether edge signs follow multiplicative transitivity, then evaluates these measures on the Slashdot Zoo.
- Signed transitivity: Multiplicative transitivity means two incident edges tend to be completed by an edge whose weight equals their product.This corresponds to the signed-network intuition that the enemy of my enemy is my friend.
- Coefficient variants: The four variants cover regular, directed, signed, and signed directed clustering coefficients.For signed variants, a triangle contribution is weighted by sgn(abc), where c completes incident edges a and b.
- Signed transitivity: The signed clustering coefficient measures how much a signed network exhibits multiplicative transitivity, with values ranging from −1 to +1.It weights completed triangles according to whether their edge signs are coherent.
- Signed transitivity: The relative signed clustering coefficient is the signed-to-unsigned clustering coefficient ratio, indicating how well the multiplication rule applies.Its values range from −1 to +1; +1 means all triangles are oriented coherently.
- Interpretation: Signed clustering coefficients are zero when edge signs are equally distributed randomly, and they are no larger than their unsigned counterparts.Unsigned coefficients overestimate correctly placed edges because they ignore edge weights.
- Slashdot Zoo findings: The Slashdot Zoo has a higher clustering coefficient and lower mean node distance than a same-sized random graph, supporting its classification as a small-world network.Table 2 ignores edge direction and sign when calculating distances, while Table 3 compares clustering with a random graph.
5. POPULARITY AND CENTRALITY
This section extends popularity and centrality measures to signed networks and evaluates them for identifying unpopular users. Spectral measures capture network position, while Negative Rank combines signed and unsigned rankings and performs best for troll identification.
- Signed popularity and centrality measures are evaluated for identifying both well-liked and much-unliked users.The section reviews node-level measures and applies them to troll identification.
- Popularity and centrality measures: PageRank ignores edge signs because it uses the unsigned adjacency matrix, so it indicates centrality rather than popularity.Its Google matrix is defined for nonnegative edge weights, and friend and foe links are not distinguished.
- Popularity and centrality measures: Signed Spectral Ranking admits positive and negative values, representing positive and negative endorsements in the network.It is computed as the dominant left eigenvector of the signed matrix Gs.
- Negative Rank: Negative Rank subtracts PageRank from Signed Spectral Rank, using β to control PageRank’s influence.The paper initially sets β = 1 and later evaluates its effect.
- Negative Rank: For known trolls, Signed Spectral Rank is much lower than PageRank, motivating their difference as a troll-sensitive measure.For most users, the two rankings are nearly equal; the difference is pronounced for known trolls.
- Identifying trolls: Negative Rank performs best for identifying trolls, while Signed Spectral Ranking alone performs very badly.The results indicate that combining Signed Spectral Rank with PageRank is important for this task.
- Identifying trolls: The optimal Negative Rank performance occurs at β = 1.This confirms the paper’s initial choice of parameter value.
6. LINK PREDICTION
This section studies link prediction in signed social networks, focusing on predicting whether missing edges are positive or negative. The approach is motivated by algebraic link-prediction methods and applications such as recommending friends and foes.
- Similarity and distance measures are examined because algebraic link-prediction methods can be formulated using matrix multiplication.The section uses signed-network transitivity to assess these methods.
- The section focuses on predicting the sign of edges in signed social networks.Methods designed for nonnegative networks predict only edge presence or absence, so signed networks require algorithms that predict missing edge signs.
- Link prediction can support recommender systems that suggest new friend and foe relationships on Slashdot.The paper identifies recommending users to another user’s friend and foe list as a possible application.
6.1 Problem Formulation
The problem formulation treats similarity as a basis for predicting links between nodes. In signed directed networks, prediction may be asymmetric, so the relevant function need not be a conventional kernel.
- A similarity function maps two network nodes to a similarity value used to predict existing or future edges.Similar nodes are treated as more likely to be connected.
- Similarity functions need not be symmetric in this setting because a link from u to v may be predicted without predicting one from v to u.Such a function may instead be called a proximity measure.
6.2 Baseline Algorithms
The baseline algorithms use simple sign heuristics and adjacency-matrix multiplication. Shortest-path similarity measures do not outperform these baselines on accuracy.
- The always-positive baseline has nonzero accuracy because positive edges outnumber negative edges.
- The opposite-direction baseline copies the sign of an edge in the reverse direction and otherwise predicts a positive edge.
- The A2 baseline uses the squared adjacency matrix, directly exploiting multiplicative transitivity.
- Shortest-path similarity measures achieve no better accuracy than the three baseline algorithms.The baseline accuracies are reported in Table 5.
6.3 Algebraic Similarity Measures
The section develops algebraic similarity measures for signed link prediction, using dimensionality reduction to make matrix-based methods practical on large sparse networks. Matrix exponentials aggregate signed path information beyond length two, while signed Laplacian methods provide an alternative similarity framework.
- Dimensionality Reduction: Computing A^3 and higher powers becomes impractical because they produce nonsparse matrices, so the methods use dimensionality reduction.The graph has radius three and diameter six, making powers after A^2 too large for practical calculations.
- Dimensionality Reduction: Sparse singular value decomposition produces a low-rank approximation whose nonzero entries at missing edges predict their signs.The reduced approximation is efficient for large, sparse matrices.
- Matrix Exponential: The matrix exponential weights signed path counts by inverse factorial, extending the enemy-of-an-enemy rule to arbitrarily long paths.Odd numbers of negative edges contribute negatively to the signed path counts.
- Matrix Exponential: Unlike A^2, the matrix exponential can provide sensible predictions for node pairs farther apart than distance two.It often agrees with A^2 for distance-two pairs while retaining information from longer paths.
- Signed Laplacian Similarity: Signed Laplacian kernels extend Laplacian-based similarity methods to negative-edge graphs using a symmetric adjacency matrix and dimensionality-reduced pseudoinversion.The signed resistance-distance construction uses B = A + A^T and a diagonal degree matrix.
- Signed Laplacian Similarity: Asymmetric directed Laplacians perform poorly for link sign prediction according to extensive experimentation.The paper therefore does not favor the directed Laplacian formulation for this task.
6.4 Experimental Evaluation
The evaluation holds out 30% of edges and predicts their signs from the sign of learned similarity values. Exponential kernels perform best overall, while signed Laplacian similarity remains competitive and avoids overfitting as dimensionality grows.
- Evaluation Setup: 30% of edges are held out for testing, with similarity-function signs converted directly into positive or negative link predictions.Accuracy ranges from −1 for all wrong predictions to +1 for all correct predictions, with random guessing at zero.
- Results: Exponential kernels outperform their non-exponential counterparts on the link sign prediction task.The evaluation varies the dimensional reduction parameter k for each similarity measure.
- Results: The asymmetric matrix exponential achieves the overall best prediction accuracy.Its strong performance supports extending multiplicative transitivity to paths longer than two with damping factors.
- Results: Exponential kernels avoid the overfitting seen in A and A sym, reaching their best performance asymptotically as k grows.The non-exponential baselines instead attain their greatest accuracy at specific small values of k.
- Results: The signed Laplacian similarity matrix provides comparable accuracy to simple dimensional reduction and performs well at very small k.It also does not suffer from overfitting for large k.
7. CONCLUSION
The paper applies signed network analysis at global, node, and link levels to the Slashdot Zoo. It concludes that the network exhibits multiplicative transitivity and that signed methods reveal information unavailable to unsigned techniques.
- Contributions: The study defines signed clustering measures, introduces Negative Rank for identifying troll users, and evaluates signed spectral similarity measures for link sign prediction.These contributions cover global, node, and link-level analysis of the Slashdot Zoo.
- Conclusion: The Slashdot Zoo exhibits multiplicative transitivity, summarized by the phrase “the enemy of my enemy is my friend.”This property is presented as a characteristic of signed social networks.
- Conclusion: Signed network-analysis methods apply to large social networks and reveal facts that common unsigned techniques cannot uncover.The conclusion frames this as the principal significance of analyzing negative edge weights.
- Future Scope: The paper notes that further social networks with positive and negative endorsements could also be analyzed.Examples include other Slash2 sites, Digg, Essembly, and Epinions.
- Future Scope: Several methods remain uncovered, including betweenness centrality, spectral clustering, signed random-graph modeling, and stochastic prediction approaches.The paper presents these as techniques that could conceivably be extended to signed networks.