Hypergraph topological quantities for tagged social networks

Recent years have witnessed the emergence of a new class of social networks, which require us to move beyond previously employed representations of complex graph structures. A notable example is that of the folksonomy, an online process where users collaboratively employ tags to resources to impart structure to an otherwise undifferentiated database. In a recent paper, we proposed a mathematical model that represents these structures as tripartite hypergraphs and defined basic topological quantities of interest. In this paper, we extend our model by defining additional quantities such as edge distributions, vertex similarity and correlations as well as clustering. We then empirically measure these quantities on two real life folksonomies, the popular online photo sharing site Flickr and the bookmarking site CiteULike. We find that these systems share similar qualitative features with the majority of complex networks that have been previously studied. We propose that the quantities and methodology described here can be used as a standard tool in measuring the structure of tagged networks.

Figure 1

(Color online) A hyperedge representing the fundamental building block in our network. Each hyperedge consists of three types of vertices, red circles, green squares, and blue triangles. In addition the regular edges are also colored according to the types of vertices they connect. In relation to folksonomies, the circles represent the users, the squares the resources, and the triangles the tags.

Figure 2

(Color online) The two types of hyperdegree distributions found in a subset of the website CiteULike. Left panel: The vertex degree distributions for users, tags and resources. Right panel: The degree distribution for the various edge types.

Figure 3

(Color online) The two types of hyperdegree distributions found in a subset of the website Flickr. Left panel: The vertex degree distributions for users, tags and resources. Right panel: The degree distribution for the various edge types. The near absence of data points for the cyan edge (resource-tag) is related to the fact that tags in Flickr are public and this prevents redundant tagging—that is the application of the same tag to the same resource by multiple users.

Figure 4

(Color online) The distribution of hyperedge neighbors $P\left(h_h\right)$ as measured from the data set in CiteULike (the spikes in the data are related to spamming), as well as the theoretical values computed from Eq. (6).

Figure 5

(Color online) The distribution of hyperedge neighbors $P\left(h_h\right)$ as measured from the data set in Flickr as well as the theoretical values computed from Eq. (6). It is evident that the assumption of statistical independence between vertex and edge degrees is not appropriate in this case.

Figure 6

(Color online) In a) the central red node has $D_h=0.5$ as per Eq. (7), because $z_{max}=6$ and $z_{min}=4$. In b) a path of distance $3$ (marked by arrows) between two tags via a tag-user, user-resource, and resource-tag path.

Figure 7

(Color online) The average hyperedge density $D_h\left(k\right)$ as a function of the degree $k$ of a vertex. On the left panel, the hyperedge density for different vertex categories in the CiteULike data set. On the right panel, the same quantities for Flickr. For both data sets the users tend to form increasingly dense connections with increasing $k$. The density for resources seem to fall off with increasing $k$, except in CiteULike, where there is an interesting turning point around $k=100$.

Figure 8

(Color online) The distribution of paths between different types of vertices, implying that the network as a whole exhibits the so called small- world effect. The black arrow shows that the number of user-tag paths of distance 2 are comparatively few. This means that there are very few resources that function as direct bridges between a user and a tag. The red arrow shows that are fewer paths between tags of length 3, as compared to those of length 2 and 4. This implies that the number of bridging hyperedges where two tags are connected via a user and then a resource (as shown in Fig. 6b) are rare in this network.

Figure 9

(Color online) The network of tags in CiteUlike, constructed via the application of the similarity measure shown in Eq. (9)—in this case considering the set of papers as neighbors. Vertices with distance larger than 0.9 have been discarded. The connection between tags “differential” and “equation” indirectly implies the clustering of the corresponding papers into the same group.