Navigating the massive world of reddit: using backbone networks to map user interests in social media

Introduction

In the past decade, social media platforms have grown from a pastime for teenagers into tools that pervade nearly all modern adults’ lives (Rainie & Wellman, 2012). Social media users typically organize themselves around specific interests, such as a sports team or hobby, which facilitates interactions with other users who share similar interests. For example, Facebook users subscribe to topic-specific “pages” (Strand, 2011), Twitter users classify their tweets using topic-specific “hashtags” (Chang, 2010), Del.ici.ous users bookmark links with topic-specific tags (Golder & Huberman, 2006; Halpin, Robu & Shepherd, 2007), and reddit users post and subscribe to topic-specific sub-forums called “subreddits” (Gilbert, 2013).

These interest-based devices provide structure to the growing worlds of social media, and are essential for the long-term success of social media platforms because they make these big worlds feel small and navigable. However, navigation of social media is challenging because these worlds do not come with maps (Boguna, Krioukov & Claffy, 2008; Benevenuto et al., 2012). Users are often left to discover pages, hashtags, or subreddits of interest haphazardly, by word of mouth, following other users’ “votes” or “likes,” or by using a basic search feature. Owing to the scale-free structure of most online social networks, these elementary navigation strategies result in users being funnelled into a few large and broad interest groups, while failing to discover more specific groups that may be of greater interest (Albert, Jeong & Barabási, 1999; Barabási, Albert & Jeong, 2000). This observation leads to the question: Is it possible to build a map to aid users in the discovery of relevant interests on social networks?

In this work, we combine techniques for network backbone extraction (Serrano, Boguñá & Vespignani, 2009) and community detection (Blondel et al., 2008) to construct a roadmap that provides an alternative method for social media users to navigate (i.e., find relevant interests) these social networks by identifying related interest groups and suggesting them to users. We implement this method for the social news web site reddit (Anonymous, 2015a), one of the most visited social media platforms on the web (Anonymous, 2015b), and produce an interactive map of all of the subreddits. An interactive version of the reddit interest map is available online (Olson, 2013a).

Once we construct this map, we then ask: Does the reddit backbone network display the same complex network characteristics observed in many other real-world networks? By viewing subreddits as nodes linked by users with common interests, we find that the reddit social media world has a scale-free, small-world, and modular community structure. We hypothesize that the scale-free property is the result of a preferential attachment process in which new reddit users, or existing users who are exploring, are most likely to encounter and become active in the largest and most active sub-reddits. However, because other processes may also account for the scale-free property, this hypothesis requires further investigation. Additionally, the small-world property explains how the big world of reddit can seem small and navigable to users when it is mapped out. Finally, the modular community structure in which narrow interest-based subreddits (e.g., dubstep or rock music) are organized into broader communities (e.g., music) allows users to easily identify related interests by zooming in on a broader community. We suggest that the integration of such interest maps into popular social media platforms will assist users in organizing themselves into more specific interest groups, which will help alleviate the overcrowding effect often observed in large online communities (Gilbert, 2013).

Further, this work releases and provides an overview of a data set of over 850,000 anonymized reddit user’s interests, thus establishing another standard real-world social network data set for researchers to study. This is useful because, although reddit is among the largest online social networks and has been identified as a starting point for the viral spread of memes and other online information (Sanderson & Rigby, 2013), it has been relatively understudied (Merritt, 2012; Gilbert, 2013; Buntain & Golbeck, 2014; Leavitt & Clark, 2014). This data set can be downloaded online at Olson (2013b).

Results

Network properties

In Fig. 3, we show a series of network statistics to provide an overview of the backbone reddit interest network. These network statistics are plotted over a range of α cutoff values for the backbone reddit interest network (see Methods) to demonstrate that the interest network we chose in Fig. 1 is robust to relevant α cutoff values. Since lower α cutoff values result in many nodes becoming disconnected from the network, we only use the largest connected component of the network for all network statistics reported. As expected, the majority of the edges are pruned by an α cutoff of 0.05 (Fig. 3A). This result demonstrates that the backbone interest network is stable with an α cutoff ≤0.05, which is the most relevant range of α cutoffs to explore. Surprisingly, 80% of the subreddits that we investigated—roughly 12,000 subreddits—do not have enough users that consistently post in another subreddit to maintain even a single edge with another subreddit. The majority of these 12,000 subreddits likely do not have any significant edges due to user inactivity, e.g., some subreddits have only a single user that frequently posts to them (Fig. 4). Another factor that likely contributes to the 12,000 unlinked subreddits is temporary interests, i.e., an interest such as the U.S. Presidential election that temporarily draws a large number of people together, but eventually fades into obscurity again.

Next, we are interested in exploring whether the backbone reddit interest network is a scale-free network, where preferential attachment to subreddits can result in a few extremely popular (i.e., connected) subreddits and mostly unpopular subreddits. As such, scale-free networks are known to have node degree distributions that fit a power law (Albert, Jeong & Barabási, 1999; Barabási & Albert, 1999; Barabási, Albert & Jeong, 2000; Albert & Barabási, 2002). Regardless of the α cutoff, we observed that the node degree distribution of all backbone reddit interest networks fit a power law (R² ≈ 0.91 for k ≥ 50; Fig. 3B). This scale-free network structure is likely partially due to reddit’s default subreddit system (Anonymous, 2011), where newly registered users are subscribed to a set of subreddits by default. As expected, as α approaches 1.0, the power law exponent approaches 0.0. This occurs because as the α cutoff used for extracting the backbone network approaches 1.0, more edges are retained in the network and the structure approaches a fully connected graph in which the degree distribution is flat (i.e., characterized by a trivial power law with an exponent of zero). Furthermore, we want to confirm that the backbone reddit interest network is a small-world network(Watts & Strogatz, 1998). Small-world networks are known to contain numerous clusters, as indicated by a high average clustering coefficient, with sparse edges between those clusters, which results in an average shortest path length between all nodes (L_sw) that scales logarithmically with the number of nodes (N): (1)${\displaystyle L_{sw}\approx {log}_{10}\left(N\right).}$

Figures 3C and 3D depict the average clustering coefficient and shortest path length for all nodes in the backbone reddit interest network. Compared to Erdős–Rényi random networks with the same number of nodes and edges, the backbone network has a significantly higher average clustering coefficient. Similarly, the measured average shortest path length of the backbone network (α cutoff =0.05) follows Eq. (1), with L_sw = log₁₀(2, 347) = 3.37 ≈ 3.71 from Fig. 3D. Thus, the backbone reddit interest backbone network qualitatively appears to exhibit small-world network properties.

To quantitatively determine whether the reddit interest network exhibits small-world network properties, we used the small-worldness score (S_G) proposed in Humphries & Gurney (2008): (2)${\displaystyle S_G=\frac{C_G/C_{\mathrm{rand}}}{L_G/L_{\mathrm{rand}}}}$ where C is the average clustering coefficient, L is the average shortest path length between all nodes, G is the network the small-worldness score is being computed for, and “rand” is an Erdős–Rényi random network with the same number of nodes and edges as G. If S_G > 1, then the network is classified as a small-world network. For the backbone reddit network, we calculated S_G = 14.2 (P < 0.001), which indicates that the reddit interest network exhibits small-world network properties.

Now that we know that the backbone reddit interest network is scale-free and exhibits small-world network properties, we want to study the community structure of the backbone network. Shown in Fig. 3F, the backbone network exhibits a consistently high modularity score with an α cutoff as high as 0.9, implying that even a slight reduction in the number of edges in the backbone network reveals the reddit interest community structure. Correspondingly, depicted in Fig. 3E, the number of identified communities (i.e., clusters) remains relatively low until the α cutoff is reduced to ≤0.9. As the α cutoff is reduced, the number of identified communities generally decreases, which coincides with the loss of nodes as α decreases. Thus, the backbone reddit interest network has ≈30 core communities, and another ≈30 weakly linked communities that are lost as a more stringent α cutoff is applied.

Discussion

We have shown that backbone networks can be used to automatically map massive interest networks in social media based solely on user behavior. By viewing the big world of reddit as a hierarchical map, users can now explore related interests without providing any prior information about their own interests. Additionally, these maps could provide a dynamic view of interests on the social network, owing to the fact that they are constructed from actual user behavior in the social network. Future applications of this method may also facilitate navigation of other popular social network platforms such as Facebook and Twitter.

Furthermore, such an interest map could allow social media users to self-organize into more specific interest forums, thus reducing potential preferential attachment to large, general interest forums and alleviating the issues that arise in overcrowded social network forums (Gilbert, 2013). Given previous work that suggests network properties such as small-worldness and even modularity can result solely from network growth processes (Hintze & Adami, 2010), it would be interesting in future work to observe what processes govern network growth when users have access to an interests map like those shown in Figs. 1 and 2, and what network properties emerge from these growth processes.

Additionally, we explored the network properties of the backbone reddit interest network that we composed from the posting behavior of over 850,000 active reddit users. In this analysis, we found that the reddit interest network has a scale-free, small-world, and modular community structure, corroborating findings in many other online social networks (Ahn et al., 2007; Mislove et al., 2007). Uniquely, reddit potentially enforces a scale-free network structure on its users by automatically subscribing all new users to the same set of subreddits (Anonymous, 2011). Exploring the effect of automatically subscribing users to a fixed set of interest-specific forums on social interest network structure could be another interesting venue of future work. To expedite future analyses of the reddit interest network, we have provided the raw, anonymized data set available to download online (Olson, 2013b).

Interestingly, our findings corroborate earlier analyses of the Del.icio.us tag network focusing on collaborative tagging systems (Golder & Huberman, 2006; Halpin, Robu & Shepherd, 2007). We show here that reddit’s subreddit degree distribution also follows a power law, as predicted for collaborative tagging systems. Further, whereas Halpin, Robu & Shepherd (2007) suggested that the long tail of infrequently-used tags could likely be ignored, we demonstrated that entire interest meta-communities exist in that long tail that would not otherwise be discovered, including the sports, programming, and LGBT meta-communities. Finally, while Halpin, Robu & Shepherd (2007) was limited to visualizing only subsets of the collaborative tagging network due to excess edges, the mapping method we present here suffers no such limitations due to the backbone network extraction method.

It is important to note that the sample of user behavior we have taken is cross-sectional, reflecting users’ reddit posts and thus the relationships among reddit interests at a fixed point in time in mid-2013. However, as users’ interests evolve, so too do the relationships among them (Banerjee et al., 2009). In some cases, highly specialized and related subreddits may fuse into a single subreddit, while in other cases a general subreddit may split into multiple more specialized ones. Thus, such an interest map would require periodic (or, ideally, real-time) updating to accurately reflect dominant interests in the social network and their relationships to one another. Further, given that the network meta-communities are likely to change over time, it is not feasible to manually annotate the meta-communities as we did in Fig. 1. In future work, it would be beneficial to improve this mapping method by implementing a programmatic annotation algorithm using automatic content analysis of the conversations in the subreddits.

Methods

To acquire the data for this study, we mined user posting behavior data from reddit by first gathering the user names of 876,961 active users that post to 15,122 distinct subreddits (see Fig. 4 for more detail). reddit provides an open source API for anyone to freely mine data from the web site (Anonymous, 2015c), and only requests that published compilations of reddit data be anonymized to protect the privacy of its users. We note that this data set represents a complete sample of all active users who posted one or more times on reddit between January 2013 and August 2013. For each of the users, we gathered their 1,000 most recent link submissions and comments, counted how many times they post to each subreddit, and registered them as interested in a subreddit only if they posted there at least 10 times. We applied this threshold of at least 10 posts to filter out users that are not active in a particular subreddit. Due to storage space limitations, the latter data format is the rawest form of data we were able to store long-term for this study.

From these data, we defined a bipartite network X, where X_ij = 1 if user i is an active poster in subreddit j and otherwise is 0. We then projected this as a weighted unipartite network Y as XX′, where Y_ij is the number of users that post in both subreddits i and j. This resulted in 4,520,054 non-zero, symmetric edges between the subreddits. Details of the raw weighted subreddit network are shown in Fig. 5.

Due to the challenges associated with analyzing large weighted networks, we reduced the number of edges in the weighted subreddit network using a backbone extraction algorithm (Serrano, Boguñá & Vespignani, 2009) that has previously been used to reduce bipartite projections (Ahn et al., 2011). This algorithm begins by replacing symmetric valued edges (S_ij) with asymmetric weighted edges (A_ij and A_ji), where A_ij = S_ij/i^’s degree and A_ji = S_ij/j^’s degree. It then preserved edges whose weight is statistically incompatible, at a given level of significance α, with a null model in which edge weights are distributed uniformly at random. In our resulting backbone network, two subreddits are linked if the number of users who post in both of them is statistically significantly larger than expected in a null model, from the perspective of both subreddits. To recombine the directed edges between each two nodes, we replaced the two directed edges with a single undirected edge whose weight is the average of the two directed edges.

Thus, this technique defines a binary network of subreddit pathways along which there is a high probability users might traverse if they navigate reddit by following the posts of other users. Adjusting the α parameter allows the backbone network to include more (e.g., when α is larger) or fewer (e.g., when α is smaller) such pathways. Figure 3 summarizes the topological properties of backbones extracted using a range of α parameter values; in the findings and discussion we focus on a backbone extracted using α = 0.05. Our choice of α = 0.05 is arbitrary, but because the backbone extraction technique we use is rooted in probability theory, it nonetheless offers a precise interpretation: an edge is retained in the backbone if there is less than a 5% chance that an edge with the same weight or greater would appear under a null model in which all edge weights were conditionally (on node degree) random. Future work on extracting the reddit backbone may benefit from exploring the use of more computationally complex algorithms designed specifically for bipartite projections, including the fixed-degree (Zweig & Kaufmann, 2011) and stochastic-degree (Neal, 2014) sequence models.

We used Python’s PRAW package (Python reddit API Wrapper: https://github.com/praw-dev/praw) to gather the data and Python’s NetworkX package (Hagberg, Schult & Swart, 2008) to compute all network statistics except for the power law exponent, which was computed using the PARETOFIT module in Stata (Jenkins & Van Kerm, 2015). In the backbone graph, we focus only on the largest connected component. We detected network communities using Blondel et al. (2008), which aims to partition the nodes into mutually exclusive sets that maximize the graph’s modularity. Other community detection algorithms exist and may yield slightly different partitionings, but all aim to achieve the same goal in principle (Fortunato, 2010). We visualize the backbone network and detected communities using the OpenOrd node layout. Both the community detection and node layout routines are implemented in Gephi (Bastian, Heymann & Jacomy, 2009). Meta-communities identified by the community detection algorithm, e.g., “sports” and “programming,” were manually annotated using domain knowledge to identify a proper annotation.