Source-linked AI summary
Producing a Unified Graph Representation from Multiple Social Network Views
Derek Greene, Pádraig Cunningham
TL;DR
Community finding and visualization can be harder when social networks provide heterogeneous relations and user attributes, and many community methods assume a single relation. The paper combines per-user neighbour sets from multiple views into unified graphs; across the evaluated Twitter datasets, these graphs preserved and highlighted community structure, with higher neighbour consistency than individual views in four of five datasets.
Problem
Social-network analysis must contend with heterogeneous relations and attributes, while many community-finding algorithms assume a single relation.
Source: §1 · pp. 1–2Method
The method uses SVD rank aggregation to combine per-user nearest-neighbour sets from relation-based or feature-based views into a sparse unified graph.
Source: §1 · p. 2Results
The unified graphs preserved and highlighted community structure, with higher neighbour consistency than individual views in four of five datasets; the co-listed view outperformed the aggregate for politics-uk.
Source: §4.3 · p. 11, §5 · p. 12Takeaways & Limitations
The authors suggest using the procedure as a preprocessing step for community finding, visualization, and user recommendation.
Source: §5 · p. 12Each user has at most k outgoing edges; the authors propose adaptive per-user k as future work to accommodate hubs and outliers.
Source: §5 · p. 12
Abstract
from arXiv · showhide
In many social networks, several different link relations will exist between the same set of users. Additionally, attribute or textual information will be associated with those users, such as demographic details or user-generated content. For many data analysis tasks, such as community finding and data visualisation, the provision of multiple heterogeneous types of user data makes the analysis process more complex. We propose an unsupervised method for integrating multiple data views to produce a single unified graph representation, based on the combination of the k-nearest neighbour sets for users derived from each view. These views can be either relation-based or feature-based. The proposed method is evaluated on a number of annotated multi-view Twitter datasets, where it is shown to support the discovery of the underlying community structure in the data.
1 Introduction
Social networks combine heterogeneous relations and user attributes, while many community-finding methods assume a single relation. The paper proposes an unsupervised way to combine multiple views into a sparse unified graph for analysis.
1 Introduction
- Multiple relations and user attributes, including demographic details and user-generated text, can describe the same users.Examples include follows, retweets, curated lists, co-authorship, and co-citation.Source: §1 · p. 1
- A unified representation can support analysis across views, while a single aggregated relation is easier to interpret than graphs with several relation types.The paper also notes that social-media user curation requires combining information from multiple views to make recommendations.Source: §1 · pp. 1–2
- Many community-finding algorithms assume one relation, although interest is growing in finding communities from richer, multi-relation data.The paper frames unified representations as preferable for some analysis tasks to treating individual views separately.Source: §1 · p. 1
- The proposed method combines ranked per-user neighbour sets into a sparse unified graph, without supervision or manual view weighting.It supports relation-based or feature-based views, including incomplete views when they can be partially mapped.Source: §1 · p. 2
2 Related Work
Prior work addresses multi-view clustering through interleaved optimization, graph-based clustering, integration, and ensemble strategies. These approaches include methods requiring user-specified view weights or labeled examples.
2 Related Work
- Multi-view clustering methods include interleaved k-Means and EM, spectral clustering over Markov-chain mixtures, late integration, and joint matrix factorization.The spectral and factorization methods use user-specified parameters to set views’ relative influence.Source: §2 · p. 2
- For heterogeneous network relations, Cai et al. use labeled examples to learn a linear combination of relation matrices before spectral clustering.Gollini & Murphy [6] extend latent-space models to jointly analyze multiple link relations, fitting them with variational Bayes for networks of up to thousands of nodes.Source: §2 · pp. 2–3
- Tang et al. compare modularity on an average network, feature integration, and clustering ensembles for multi-dimensional networks.On synthetic data and five-view YouTube data, feature integration was most effective.Source: §2 · p. 3
3 Methods
The method aggregates per-user neighbour rankings across feature-based or relational views, then combines the resulting neighbour sets into a sparse graph. It uses SVD rank aggregation and supports directed or mutual-neighbour graph construction.
3 Methods
- SVD rank aggregation combines per-user nearest-neighbour rankings across feature-based or relational views into a sparse graph of strongest connections.The views need a similarity measure, and can represent some or all users.Source: §3 · p. 3, §3.1 · p. 3
3.1 Neighbour Set Identification
- For each user, the method computes similarities and ranks other users in each view, normalizes the stacked rank matrix, then selects the top k users using its first left singular vector.The example aggregates three ranked neighbour sets for u1 at k = 3 into {u2, u3, u4}.Source: §3.1 · pp. 3–4, Figure 1 · p. 4
- The procedure can be parallelized across users, and truncated SVD can reduce computation; SVD ranking was chosen for computational reasons.Other rank aggregation techniques could also be used.Source: §3.1 · p. 4
3.2 Unified Graph Construction
- The global graph is directed and unweighted, with an edge from user i to user j when j is in i’s neighbour set.The resulting sparse graph covers users present in one or more input views.Source: §3.2 · p. 4
- Because neighbour relations may be asymmetric, applications unsuitable for directed graphs can instead use an undirected mutual-nearest-neighbour graph.The undirected alternative is based on shared neighbours.Source: §3.2 · p. 4
4 Evaluation
The evaluation uses five Twitter datasets with manually curated communities to test whether the unified graph preserves neighborhood consistency. Across visual and quantitative analyses, the graph reflects community structure, with consistency results generally favoring the unified representation.
4.1 Datasets
- Five Twitter datasets with manually curated ground-truth communities provide the evaluation set.The datasets include politics, football, Olympics, and rugby communities.Source: §4.1 · p. 5
4.2 Evaluation Measures
- Consistency measures whether each user’s k-nearest neighbours share ground-truth communities; macro-averaging weights communities equally, unlike user-level micro-averaging.For overlapping communities, neighbours count when they share at least one community with the user.Source: §4.2 · pp. 6–7
4.3 Discussion
- At k = 5, politics-uk shows separated political groups, while football communities align with clubs and weak cross-club ties mostly mark recent transfers or loans.The politics graph has only a handful of long-range inter-community links.Source: Figure 2 · p. 7, §4.3 · pp. 7–8, Figure 3 · p. 8
- In rugby, overlapping assignments increase inter-community connectivity, yet country groups contain club-based subgroups and cross-country transfer nodes.The ground truth covers 15 countries and allows some users to belong to multiple communities.Source: §4.3 · p. 9, Figure 4 · p. 9
- For both micro- and macro-average consistency, the unified graph generally leads individual views across datasets; politics-uk is the exception.The co-listed view outperforms the unified graph on politics-uk.Source: Figure 5 · p. 10, Figure 6 · p. 11, §4.3 · pp. 11–12
- No individual view outperforms all others on every dataset, while the proposed method performs robustly without manual view prioritization or weighting.The authors report this pattern across their experiments.Source: §4.3 · p. 12
5 Conclusions
The paper applies rank aggregation to nearest-neighbour sets to build unified graphs from heterogeneous views, and reports that these graphs preserve and highlight community structure in annotated Twitter datasets. It suggests the method as preprocessing for network analysis and identifies directions for extending the model and evaluation.
5 Conclusions
- Unified graphs preserve and highlight underlying community structure in annotated Twitter datasets.Source: §5 · p. 12
- The authors suggest using the procedure as preprocessing for community finding, visualisation, and user recommendation.Source: §5 · p. 12
- Each user currently has at most k outgoing edges; planned adaptive k selection would accommodate hubs and outlying users.Source: §5 · p. 12
- Planned extensions include evaluating unified graphs with community-finding algorithms and combining partial views across social platforms.Source: §5 · p. 12