Predictive Characteristics of Co-authorship Networks: Comparing the Unweighted, Weighted, and Bipartite Cases

The first predictor is common neighbors, which simply measures the number of common neighbors for two nodes: s(u,v)=|Γ<!-- G -->(u)∩<!-- n -->Γ<!-- G -->(v)|.$$\begin{array}{} \displaystyle s(u,v)=|\Gamma(u)\cap\Gamma(v)|. \end{array} $$(1)

Because it is so simple and it occurs in the seminal work by Liben-Nowell and Kleinberg (2007), this predictor is used (if only as a comparison point) in virtually every link prediction study. It is intuitively clear that, for instance, two unconnected people who have a large amount of friends in common are likely to eventually meet and befriend each other. This intuition was confirmed empirically in collaboration networks by Newman (2001a), who found that “[a] pair of scientists who have five mutual previous collaborators, for instance, are about twice as likely to collaborate as a pair with only two, and about 200 times as likely as a pair with none.” In other words, many social networks exhibit a natural tendency towards forming triangles and hence, the common neighbors predictor is directly related to the clustering coefficient.

Several normalizations of the common neighbors predictor have been proposed in the literature. Because most of these normalizations yield very similar results (Guns, 2009), we choose one to represent this set of predictors, namely the cosine measure: s(u,v)=|Γ<!-- G -->(u)∩<!-- n -->Γ<!-- G -->(v)||Γ<!-- G -->(u)||Γ<!-- G -->(v)|.$$\begin{array}{} \displaystyle s(u,v)=\frac{|\Gamma(u)\cap\Gamma(v)|}{\sqrt{|\Gamma(u)|}\sqrt{|\Gamma(v)|}}. \end{array} $$(2)

Let d(u, v) denote the length of the shortest path from u to v. The graph distance predictor then is defined as: s(u,v)=1d(u,v).$$\begin{array}{} \displaystyle s(u,v)=\frac{1}{d(u,v)}. \end{array} $$(3)

Katz (1953) proposed a centrality indicator whose stated aim was to overcome the limitations of plain degree centrality. Interestingly, the same procedure can be used to obtain a measure of relatedness between two nodes. The latter has become known as the Katz predictor. Let A denote the adjacency matrix of the unweighted network G, such that A_ij is 1 if there is a link between nodes i and j, and 0 otherwise.

Then, each element Aijk$\begin{array}{} \displaystyle \boldsymbol {\rm A}^k_{ij} \end{array} $ of A^k (the k^th power of A) has a value equal to the number of walks with length k from i to j (Wasserman & Faust, 1994). Generally, longer walks indicate a weaker association between the start and end node. Katz (1953) therefore introduces a parameter β (0 < β < 1), representing “the probability of effectiveness of a single link.” Based on the assumption that more and shorter walks between two nodes indicate a higher likelihood of link formation, the Katz predictor is defined as: s(i,j)=∑<!-- ? -->k=1∞<!-- 8 -->β<!-- ? -->kAijk.$$\begin{array}{} \displaystyle s(i,j)= \sum^\infty_{k=1}\beta^k\boldsymbol {\rm A}^k_{ij}. \end{array} $$(4)

The intuition behind rooted PageRank (Liben-Nowell & Kleinberg, 2007) can be understood from the perspective of a random walker. The random walker starts at a fixed node i. At each step, it moves to a random neighbor of the current node. Contrary to ordinary PageRank, rooted PageRank does not allow teleportation to a randomly chosen node with probability (1–α)/n. Instead, there is a probability (1–α) that the walker will teleport back to i. Note that the literature mentions several measures that are closely related to rooted PageRank, such as cycle-free effective conductance (Koren et al., 2006) and escape probability (Song et al., 2009).

We now turn to the question how the aforementioned predictors can be applied to weighted networks, such that they take link weight into account.

Murata and Moriyasu (2007) propose the following weighted variant of common neighbors: s(u,v)=∑<!-- ? -->Z∈<!-- ? -->Γ<!-- G -->(u)∩<!-- n -->Γ<!-- G -->(v)w(u,z)+w(z,v)2.$$\begin{array}{} \displaystyle s(u,v)=\sum_{Z\rm {\in\Gamma(\it u)\cap}\Gamma(\it v)}\frac{w(u,z)+w(z,v)}{2}. \end{array} $$(5)

A potential downside of their approach is that this weighted variant lacks a theoretical basis and has been constructed ad hoc. Since the neighborhood-based predictors are based on similarity measures that have been used in information retrieval (Boyce, Meadow, & Kraft, 1994; Salton & McGill, 1983; van Rijsbergen, 1979), link weights can be taken into account by using the vector interpretation of the set-based similarity measures (Egghe & Michel, 2002; Egghe, 2009).

If element i is a member of the set, its corresponding vector element x_i = 1. Otherwise, x_i = 0. Assume there are two sets A and B, with corresponding vectors X→<!-- ? -->$\begin{array}{} \displaystyle \vec{X} \end{array} $ and Y→<!-- ? -->.$\begin{array}{} \displaystyle \vec{Y}. \end{array} $ If A={i∈<!-- ? -->1…<!-- ? -->,n|xi=1},B={i∈<!-- ? -->1…<!-- ? -->,n|yi=1}$$\begin{array}{} \displaystyle A=\{i\,{\rm\in}\,1\dots,n|x_i=1\},\\B=\{i\,{\rm\in}\,1\dots,n|y_i=1\} \end{array} $$

the step from sets to vectors can be taken using the following equation: |A|=∥X→<!-- ? -->∥2=∑<!-- ? -->i=1nxi2|B|=∥Y→<!-- ? -->∥2=∑<!-- ? -->i=1nyi2.|A∩<!-- n -->B|=X→<!-- ? -->⋅<!-- ? -->Y→<!-- ? -->=∑<!-- ? -->i=1nxi⋅<!-- ? -->yi$$\begin{array}{} \displaystyle |A|=\bigg\Vert\vec{X}\bigg\Vert^2=\boldsymbol\sum\nolimits_{i=1}^n x^2_i\\\displaystyle|B|=\bigg\Vert\vec{Y}\bigg\Vert^2=\boldsymbol\sum\nolimits_{i=1}^n y^2_i\qquad\quad.\\\displaystyle|A\cap B|=\vec{X}\cdot\vec{Y}=\sum\nolimits_{i=1}^nx_i\cdot y_i \end{array} $$(6)

The advantage of the vector-based measures over the set-theoretic ones is that they are not limited to the binary case, i.e. vector elements can have any numeric value.

To apply these in the context of link prediction, vectors X→<!-- ? -->$\begin{array}{} \displaystyle \vec{X} \end{array} $ and Y→<!-- ? -->$\begin{array}{} \displaystyle \vec{Y} \end{array} $ are, respectively, the adjacency vectors of nodes u and v. We thus obtain the weighted interpretation of common neighbors: s(u,v)=∑<!-- ? -->i=1nxi⋅<!-- ? -->yi.$$\begin{array}{} \displaystyle s(u,v)=\boldsymbol\sum^n_{i=1}x_i\cdot y_i\,\,. \end{array} $$(7)

Note that Equations (5) and (7) do not result in the same ranking. This is illustrated by Figure 2. According to (5), s(u, v) = 3.5 > s(u′,v′) = 3, whereas according to (7), s(u,v) = 6 < s(u′,v′) = 9. In our opinion, the ranking by (7) is more logical: both links need to have sufficient weight to indicate a ‘strong’ common neighbor and, hence, the situation on the right should have a higher likelihood score.

Figure 2

Likewise, weighted cosine becomes: s(u,v)=∑<!-- ? -->xi⋅<!-- ? -->yi∑<!-- ? -->xi2∑<!-- ? -->yi2.$$\begin{array}{} \displaystyle s(u,v)=\frac{\boldsymbol\sum x_i\cdot y_i}{\sqrt{\boldsymbol \sum x^2_i \boldsymbol \sum y^2_i}}. \end{array} $$(8)

Equation (8) indicates why this is called the cosine measure: it is the cosine of the angle between two vectors. In other words, this measure takes into account the direction but not the magnitude of the two vectors.

We now turn to the weighted graph distance predictor. Let p(u, v) denote a path between u and v of length t. Let w_i (i = 1,…, t) denote the weight of the i^th link in the path. The weighted path length can be defined by taking the sum of the inverses of each weight (Brandes, 2001; Egghe & Rousseau, 2003; Newman, 2001b). wp(u,v)=∑<!-- ? -->i=1t1wi.$$\begin{array}{} \displaystyle w_p(u,v)=\sum^t_{i=1}\frac{1}{w_i}. \end{array} $$(9)

One can then define the distance or dissimilarity between u and v as the length of the shortest weighted path: d(u,v)=minpwp(u,v).$$\begin{array}{} \displaystyle d(u,v)={\mathop {\min} \limits_p}\,w_p(u,v). \end{array} $$(10)

Egghe and Rousseau (2003) remark that “A direct link is very important. Yet, if weights are high enough, it is possible that an indirect connection leads to a smaller dissimilarity than the direct link.” Consider Figure 3. This network contains three paths between u and v. The shortest weighted path, using Equation (10), is the path u–y–v, with a length of 1/2 + 1/3 = 5/6. Interestingly, we note that the direct link and the path via x have the same weighted path length. This may be perfectly appropriate in some cases, especially if there is no real cost attached to the number of nodes one has to traverse (assuming that the link weights are high enough). However, it seems likely that a larger number of intermediary nodes may have a negative effect on at least some social networks. For instance, if the nodes in Figure 3 are authors and edge weights represent the number of joint publications, one could argue that the ‘cost’ of traversing the direct link is smaller than that of the path via x or even of the path via y.

Figure 3

On the basis of similar considerations, Opsahl, Agneessens, and Skvoretz (2010) propose a generalization of weighted path length in a proximity-based weighted network: wp,α(u,v)=∑<!-- ? -->i=1t1wiα<!-- a -->,$$\begin{array}{} \displaystyle w_{p,{\alpha}}(u,v)=\sum^t_{i=1}\frac{1}{w^{\alpha}_i}, \end{array} $$(11)

where α is an extra tuning parameter. Here, we are only interested in those cases where 0 ≤ α ≤ 1. If α = 0, Equation (11) reduces to the path length of the corresponding unweighted path—i.e. only the number of intermediary nodes is taken into account. If α = 1, (10) reduces to (8)—i.e. only the edge weights are taken into account. Thus, setting 0 < α < 1 allows one to find a balance between both extremes. For instance, if α = 0.5, the paths in Figure 3 get the following weights: direct link: 1; path via y: 1.28; path via x: 1.41. The weighted shortest path then is formed by the direct link.

We thus obtain the weighted graph distance predictor: s(u,v)=1minpwp,α(u,v).$$\begin{array}{} \displaystyle s(u,v)=\frac{1}{\min\limits_{p}w_{p,{\alpha}}(u,v)}. \end{array} $$(12).

The weighted Katz predictor also uses Equation (4). The only difference is that in this case the adjacency matrix can contain any positive integer. As explained by Guns and Rousseau (2014), the value of an element Aijk$\begin{array}{} \displaystyle \boldsymbol {\rm A}^k_{ij} \end{array} $ in the weighted case is the number of walks with length k in the equivalent multigraph.

Finally, weighted rooted PageRank is very similar to unweighted rooted PageRank. The only difference is that link weights determine the transition probability to neighboring nodes. For instance, if we applied weighted rooted PageRank to the network in Figure 3 and the random walker was positioned at node v, node y(x) would be three (two) times more likely than u to be visited next.

The bipartite author-publication networks are unweighted. Hence, it is, at least mathematically speaking, possible to apply the predictors from the ‘unweighted predictors’ section to the bipartite network as well. Here, we consider some specific issues that may arise when doing so.

First, we emphasize that our current analysis is only concerned with predicting links between authors themselves, and not links between articles or between authors and articles. This can be achieved by simply distinguishing between ‘eligible’ (author) nodes and ‘non-eligible’ (article) nodes. We only retain predictions that involve two eligible nodes.

Let us now consider the neighbor-based predictors (common neighbors and cosine). If u and v are bottom nodes (authors), their neighbors are by definition top nodes (articles). In other words, common neighbors, cosine and variants can be used for bipartite networks as well. However, their interpretation is completely different. Most importantly, applying Equations (1) and (2) to a bipartite network never yields a genuine prediction (appearance or disappearance of a link), only an estimate of the likelihood a co-authorship link in the training network will sustain in the test network. While this is a valid application in itself, it is different from what is typically considered as link prediction.

Note that this limitation does not mean that the bipartite neighbor-based predictors are the same, since their ranking is different. The common neighbors predictor ranks in decreasing order of the number of joint publications. Cosine is similar, but normalizes with respect to the total number of publications of the authors.

The bipartite graph distance predictor will not be considered in our analysis. The reason is that it yields the same ranking as its unweighted unipartite counterpart: the shortest path length for any bottom node pair is simply doubled in the bipartite case.

Contrary to graph distance, the bipartite Katz predictor can result in a ranking that is different from the unipartite predictor. Moreover, compared to the neighbor-based predictors, Katz has the advantage that it is not restricted to neighboring nodes (or neighbors of neighbors). However, note that the bipartite variant does not incorporate hypothesis H1b. This can be illustrated through the example in Figure 4. Assume that the top nodes represent publications and the bottom nodes represent authors. In both cases, authors a and b have two collaborators in common and can be connected via two paths of length 4. Consequently, the Katz predictor ranks both cases equally high, even though our hypothesis implies that the left case should rank higher than the right one.

Figure 4

Finally, bipartite rooted PageRank has the same advantage as Katz when compared to neighbor-based predictors: it is not restricted to predicting co-authors that u and v have in common, let alone that it is – like bipartite common neighbors or cosine – restricted to authors that already collaborate in the training network. At each step, the random walker switches between top and bottom nodes (disregarding teleportation). If the random walker is at a given paper, each of the paper’s authors has an equal chance of being the next hop. This implies that rooted PageRank values are lower in cases where papers have more authors: rooted PageRank ranks the right case of Figure 4 lower than the left one. In other words, if hypothesis H1b is correct, this should be reflected in the performance of bipartite rooted PageRank.

In the context of link prediction, the notions of recall and precision can be defined as follows. Precision P is the fraction of correctly predicted links compared to all predictions. Recall R is the fraction of correctly predicted links compared to all links in the test network. The F-score is the harmonic mean of precision and recall: F=2PRP+R.$$\begin{array}{} \displaystyle F=\frac{2PR}{P+R}. \end{array} $$(13)

If either P or R is low, F will be low as well. We rank predictions in decreasing order of their likelihood score. The values obtained for precision, recall and F-score depend on how many predictions are taken into account.

We use two measures for evaluation. Precision-at-20 (P@20) is the precision for the top 20 predictions and gauges a predictor’s ability to make a small number of high-quality predictions. F_max is the highest F-score obtained by a predictor. As argued by Guns, Lioma, and Larsen (2012), this measure offers a good summary of the overall capacities of (in our case here) a predictor.

Links in a network tend to be positively stable: we find that 61.7% (UA) and 62.7% (INF) of the links in the training network reoccur in the test network. Only 14.6% (UA) and 18.2% (INF) of the links in the test networks do not occur in the training network. All this suggests that plain reoccurrence is actually a fairly strong predictor.

What happens if we incorporate link weights? We test this on the UA dataset and find that the F-score is virtually unaffected but precision-at-20 increases from 0.48 to 1.00. Similar results are obtained for the INF dataset (Table 2). All in all, this lends strong support to hypothesis H1a.

Table 2

Results for positive stability.

To test the influence of the number of authors per paper, we determine for each author pair in the training network the median number of authors on their co-authored publications. This results in an increase of precision, but a decrease (UA) or status quo (INF) in F-score. The effect of this factor would likely be higher if tested on datasets where the overall number of authors per paper is higher. Indeed, the highest number of co-authors is 10 in the UA dataset and 6 in the INF dataset. Based on our current investigation, however, the evidence in favor of hypothesis H1b is limited.

The relative performance of different predictors has been studied quite extensively (e.g. Guimerà & Sales-Pardo, 2009; Guns, 2014; Liben-Nowell & Kleinberg, 2007; Song et al., 2009) and is not the main focus of the present paper. Rather, we are interested in comparing the influence of the network type on predictor performance. Hence, we will present results per predictor family.

Tables 3 and 4 contain the results for the neighborhood-based predictors for UA and INF, respectively. In all cases, we observe that the unweighted variants perform as well as or better than the weighted ones, both for F-score and precision. Although in most cases the difference between the two is negligible, this is quite surprising. We will discuss this remarkable result in the last section of the paper. For now, we just observe that it appears to counter hypothesis H2a.

Table 3

Results for neighborhood-based predictors (UA).

Table 4

Results for neighborhood-based predictors (INF).

The bipartite predictors perform much better (with the exception of precision for common neighbors applied to the UA dataset, which has a perfect score for all three types). This does not really corroborate H2b: though, as explained above, the bipartite neighborhood-based predictors only ‘predict’ the recurrence of already existing co-authorship relations. In other words, their good performance is related to hypothesis H1a.

We have seen that Opsahl et al. (2010)’s refinement of graph distance introduces a tuning parameter that determines to what extent the measure takes link weights into account. Figure 5 shows the results for UA; the resulting picture for INF looks very similar. First, recall that α = 0 corresponds to the unweighted case, whereas α = 1 corresponds to the ‘fully’ weighted case. Neither of the two extremes turns out to be optimal. If weights are not used, precision suffers but as α increases, the maximum F-score decreases. The optimal situation for both datasets appears to lie around α values between 0.1 and 0.2. As has been explained above, we do not apply graph distance to a bipartite network, since the resultant ranking is the same as one would obtain for an unweighted network.

Figure 5

Figures 6–8 display the results for the Katz predictor for values of β between 0.1 and 0.9. For UA we find that, in general, the unweighted case has the lowest predictive power (Figure 6). In terms of precision (not shown), both the weighted and bipartite variants obtain perfect scores for each value of β, while the unweighted variant yields values between 0.57 and 0.67. In terms of F-score, however, the advantage of the bipartite variant is quite clear, while the difference between the weighted and unweighted variants is fairly small. For INF the bipartite variant again scores best, followed by the unweighted variant and finally the weighted one. The difference between bipartite and unweighted increases with higher values of β.

Figure 6

Figure 7

Figure 8

Finally, we turn to the rooted PageRank predictor. Results are shown in Figures 9–12. For UA we find that the differences between the three network types yield rather small differences in terms of F-score (Figure 9). The differences are more pronounced for precision (Figure 10). The overall ranking by either measure, however, is similar: bipartite scores better than weighted, which in turn scores better than unweighted.

Figure 9

Figure 10

Figure 11

Figure 12

A similar conclusion holds for the INF dataset (Figures 11 and 12). Here, we see that unweighted and weighted obtain the same precision scores, but in terms of F-score the weighted variant is better. The bipartite variant, however, scores best overall.