Improvement on the association strength: Implementing a probabilistic measure based on combinations without repetition

https://publons.com/publon/10.1162/qss_a_00122

The use of co-occurrence data is popular in numerous scientific domains, such as scientometrics (e.g., Leydesdorff & Vaughan, 2006; van Eck & Waltman, 2009), computational linguistics (e.g., Schutze, 1998), community ecology (e.g., Peres-Neto, 2004), development economics (e.g., Hidalgo, Kilinger et al., 2007), molecular biology (e.g., Maslov & Sneppen, 2002) and evolutionary economic geography (e.g., Boschma, Balland, & Kogler, 2015). Its use is widespread and closely related to the popularity of network analysis across disciplines.

Co-occurrence data is used to infer the relation (referred to as relatedness here, following Hidalgo et al. [2007]), between entities, which can be species of fish, authors, or technological classes, by observing how each of these co-occur with others in places such as streams, articles, or patents. However, the total number of co-occurrences between a pair of entities cannot be used straightforwardly to reflect the relatedness between them because entities with more observations are more likely to co-occur than entities with fewer observations. To correct for this size effect, a normalization measure is applied to the data¹. van Eck and Waltman (2009) review the most popular normalization measures and make a convincing case for the use of a probability-based measure known as the association strength. This measure is based on dividing the observed number of co-occurrences over the expected numbers of co-occurrences when assuming observations are randomly distributed over co-occurrences².

In this paper, it is shown that the probability formula for the association strength, as proposed by van Eck and Waltman (2009), is not optimized to calculate the expected number of co-occurrences. The formula of van Eck and Waltman (2009) is proportional to probability calculations based on combinations with repetition, which means that when estimating the probability that two entities co-occur, the first observation drawn is assumed to be available for drawing again when drawing the second observation. However, in the use of co-occurrence data the co-occurrence of observations from the same entity is disregarded³. Authors, for example, do not coauthor papers with themselves (Leydesdorff & Vaughan, 2006). Therefore, van Eck and Waltman (2009) suggest setting these self co-occurrences to missing values⁴. This makes the possibility of drawing the same observation or any other observation from the same entity impossible in the second draw once an observation from this entity has been drawn in the first draw.

Therefore, an improved formula for the association strength is introduced using a probability measure based on combinations without repetition but with a noticeable change. In combinations with repetition, one cannot draw an observation in the second draw if it has been drawn in the first draw. In this setting, none of the observations belonging to the same entity as the first observation can be drawn in the second draw. Furthermore, two refinements are proposed in this paper regarding the inputs to the formula, which in the current definition do not properly take into account how the number of observed co-occurrences is calculated.

The improved formula is compared to the original formula in a theoretical setting, a number of simulations, and a real-world application using patent data. It is shown that, first, the original formula overestimates the relatedness between a pair of entities when this pair has at least one co-occurrence. This indicates that the original formula can wrongly identify two entities as related when in fact they are not; and, second, the original formula overestimates the relatedness between some pairs more than others. This indicates that the overestimation is not proportional and that the differences between the relatedness values for each pair are also distorted.

In the theoretical analysis, the improved formula is subtracted from the original formula to obtain a formula for the difference. By considering the domain of each variable, it is shown that the original formula underestimates the number of expected occurrences in all cases and therefore overestimates the relationship between two entities when there is at least one observed co-occurrence. Continuing the theoretical exploration, the first-order partial derivatives of the difference with respect to each variable is taken, which shows that the overestimation is not equal across all possible types of co-occurrence matrices.

Just taking the partial derivatives is not sufficient to show the size of the difference for each case, as the values of the variables are interconnected in ways that do not allow for analytical solving. Therefore, simulations are run in which four different exemplary cases are taken to the extreme to demonstrate the effect on the difference. The simulations show that the overestimation by the original formula can be close to 0% but also close to 100% of the relatedness value given by the improved formula, depending on the specificities of the co-occurrence matrix.

To measure to what extent these theoretical simulations are representative of real-world applications of research on co-occurrence data, a number of patent samples, containing data on the technology classes per document, is treated to compare the results of both formulas. In these samples, the overestimation of relatedness values for individual pairs varies between close to 0% to up to 3.234% of the value given by the improved formula, and therefore does not attain the most extreme values obtained in the simulation. Nonetheless, it clearly confirms that some pairs are more overestimated than others. The results also show that some pairs are misidentified as being related by the original formula, but that this is only the case for a rather small share of the pairs, up to about 0.29% of the number of pairs identified by the original formula.

Therefore, it is advisable to use the improved formula when working with co-occurrence data where self-co-occurrences are nonexistent or irrelevant. The reformulation of the probability measure does not in any way alter the conclusion by van Eck and Waltman (2009) that probability-based measures outperform so-called set-theoretic measures in normalizing co-occurrence data. The improved measure, including the recommended method of implementation, is available in the EconGeo package for R maintained by Balland (2016).

This paper is organized as follows: Section 2 gives a short overview of the use of co-occurrence data and the association strength; Section 3 discusses the refinements; Sections 4 to 6 explore the overestimation by the original formula respectively in a theoretical setting, simulations, and a real-world example using patent data; and Section 7 concludes.

Co-occurrence data is generally derived from a binary occurrence matrix O of some order m × n. The rows of O correspond to the places in which the observations occur and the columns to the entities to which they belong⁵. There is a large variety of what these places and entities can be⁶. The example in Matrix 1 shows three patents that contain a reference to, respectively, only class c, class c and class d, and all classes a to d.

By multiplying the transpose of O by O itself the co-occurrence matrix C is obtained⁷, in which both the rows and the columns represent the entities and the matrix gives how often they co-occur with the other.

In the case of our example, this would yield the co-occurrence matrix C given in Matrix 2. Where class a co-occurs once with b, c, and d; class b co-occurs once with a, c, and d; class c co-occurs once with a and b, and twice with d; and class d co-occurs once with a and b, and twice with c.

The diagonal is set to zero as the reference to a certain class does not entail a co-occurrence between that class and itself in the line of research for which the formula is intended. Ahlgren et al. (2003), Leydesdorff and Vaughan (2006) and van Eck and Waltman (2009) suggest setting the diagonal to missing values. This leads to the same results. However, it is advisable to use zeros, because missing values often results in errors when using statistical software⁸. Setting the diagonal to zero has important implications down the line.

In many applications of co-occurrence data, such as the concept of relatedness, the raw numbers of co-occurrences between entities cannot straightforwardly be interpreted as giving the strength of the relation between each pair of entities. There is a so-called size effect, as some classes co-occur more often with others for the simple reason that these classes have more occurrences in the first place. In our example, d has more co-occurrences with c than with a or b but c also has more occurrences in total and therefore is more likely to co-occur with any class.

To correct the absolute number of co-occurrences for the size effect a normalization procedure is applied to the data (van Eck & Waltman, 2009)⁹. Correcting co-occurrence data for the size effect to derive relationships between entities is done through direct similarity measures¹⁰. van Eck and Waltman (2009) wrote an extensive review of the most popular direct similarity measures: the cosine, the Jaccard index, the inclusion index, and the association strength. Of these, the last is a probabilistic measure, while the others are set-theoretic measures. The authors show that set-theoretic measures do not properly correct for the size effect and argue in favor of the association strength.

The usability of their formula exceeds the domain of scientometrics. Hidalgo et al. (2007) developed an influential network analysis tool to derive the relatedness between entities on the basis of co-occurrences. Although they use a different probabilistic direct similarity measure than the ones covered by van Eck and Waltman (2009), other authors (e.g., Balland, Rigby, & Boschma, 2015) building on the framework of Hidalgo et al. (2007) do opt for the association strength, as defined by van Eck and Waltman (2009) ¹¹.

Albeit influential, refinements to the work of van Eck and Waltman (2009) are in place. The probabilistic formula should be based on a specific case of combinations without repetition instead of with repetition. Furthermore, the definitions of the inputs for the formula are imprecise. These points will be treated in the following section. It should be noted that the refinements to the measure do not undermine in any way the statement of van Eck and Waltman (2009) that probabilistic measures outperform set-theoretic measures in normalizing co-occurrence data to control for the size effect.

The objective of the association strength is to estimate the number of expected co-occurrences for each pair, assuming that these are randomly distributed, and compare this to the number of observed co-occurrences to give an indication of the relation between a pair of entities when corrected for the size effect. The challenge therefore is to correctly estimate the number of expected co-occurrences per combination.

As an intuitive example, Matrix 3 gives a co-occurrence matrix C in which three classes (a, b, and c) exist and co-occur exactly once with each other¹²:

As each class has two observations and two possible other classes to co-occur with, the expected number of co-occurrences is logically $22$ = 1 for each combination (a & b, a & c, and b & c).

In this case, the matrix of expected co-occurrences is exactly the same as the matrix of observed co-occurrences given in Matrix 3. Therefore, we observe as many co-occurrences as expected and $ObservedExpected$ should be equal to one for each combination.

In essence, the denominator gives that the chance of encountering a co-occurrence between an observation of class i and an observation of class j is equal to the probability of first drawing one of the observations of class i out of the total number of occurrences times the chance of drawing an observation belonging to class j out of the total number of occurrences plus the probability of first drawing j and then i times the total number of co-occurrences.

Calculating this formula for our example C in Matrix 3 would yield Relatedness Matrix R given in Matrix 4:

It is clear that the formula does not provide the intuitive answer of 1 but actually overestimates the relationship by returning that each pair co-occurs more often than could be expected given a random distribution.

The flaw cannot lie in the numerator, which is equal to the number of observed co-occurrences. Therefore the problem lies in the denominator. The formula to calculate the expected number of co-occurrences includes the possibility that when an occurrence of a certain entity is drawn the same occurrence or another occurrence of the same entity (if present) can be drawn in the next draw to complete the co-occurrence. This is known as combinations with repetition. However, as self co-occurrences are nonexistent one knows that one cannot redraw the same occurrence, but also none of the other occurrences of that class.

In the case of our example, the denominator of Eq. 1 yields an expected number of $23$ co-occurrences. This is because the formula observes two occurrences for each class and three possible partners to co-occur with, even though there are only two possible partners. Class a can co-occur with class b and class c but not with itself¹⁸.

Here, the denominator gives that the chance of encountering a co-occurrence between an observation of class i and an observation of class j is equal to the probability of first drawing one of the observations of class i times the chance of drawing an observation belonging to class j knowing that none of the observations of class i can be drawn plus the chance of first drawing one of the observations of class j times the chance of drawing an observation belonging to class i knowing that any other observations of class j cannot be drawn.

The implications of using Eq. 1 instead of Eq. 2 are that the relatedness between a pair is overestimated when at least one co-occurrence is observed and that the overestimation is larger for certain pairs than others. These implications are demonstrated and further explored in the following parts: first in a theoretic setting, then by running simulations and concluding with the analysis of a real-world example using patent data.

An obvious first notion from observing Eqs. 1 and 2 is that there is no difference in outcome when the number of observed co-occurrences is zero, as the numerator C_ij will then be zero.

Furthermore, it can be assumed that Eq. 1 overestimates the relation between two entities when there is at least one co-occurrence. The assumption in the probabilistic measure of Eq. 1 is that the same observation and other observations from the same entity can be drawn again but this is not possible. This enlarges the total pool from which observations can be drawn and therefore decreases the likelihood that a certain co-occurrence can be drawn. This leads to the denominator, which contains the expected number of co-occurrences, in Eq. 1 being smaller than the one in Eq. 2 in all cases, as was the case for the example Matrix 3, where the denominator indicated a co-occurrence probability of $23$ for each pair where actually only two options instead of three existed and therefore $22$ should have been the answer.

Due to the smaller expected probability, Eq. 1 divides the number of observed co-occurrences over too small a number of expected co-occurrences and therefore the relatedness these two entities is overestimated, when at least one co-occurrence is observed.

This means that D_probability is positive in all circumstances, which indicates that the improved formula predicts in all cases that more co-occurrences can be expected between i and j. This makes sense, as the improved formula excludes the possibility of drawing a combination of i and i, making it more likely to draw a combination between i and j.

To explore the difference due to different values of S_i, S_j, C_ij, and T the partial derivatives are taken of D_Formula with respect to each. Because T is a function of S_i, S_j, and all other co-occurrences, $∑k≠i,jn$S_k. T is replaced by S_i + S_j + L in Eq. 8 in which L = $∑k≠i,jn$S_k and its range is equal to or larger than zero.

This last statement suggests that a relationship between two entities will be more overestimated by Eq. 1 when there is a smaller amount of other possibilities to co-occur with.

Despite being informative, partial derivatives give an incomplete picture of the discrepancy between the two formulas, as these give the direction of a function with respect to an infinitesimal increase in one of the variables while keeping the others equal, even though in reality it is impossible to keep the other variables equal, as the inputs are all related to each other. Necessarily C_ij consists of S_i and S_j, and if not all S_i co-occur with S_j then L must at least have enough occurrences to co-occur with the remaining i, and js. In other words, the following logical conditions hold: C_ij ≤ min{S_i, S_j}; and L ≥ |S_i − S_j|. In the next section theoretical simulations are run in which these conditions can be met.

For the theoretical simulations a simple co-occurrence matrix C depicted in Matrix 5 is used. Although it is simple, this matrix allows for some exploration of the numerical difference between Eq. 1 or Eq. 2 for different values of S_i, S_j, C_ij, and L. In four different simulations, hypothetical and rather extreme situations are simulated to get insight into the effects of increasing the values of each of the variables S_i, S_j, C_ij, and L, while meeting the conditions C_ij ≤ min{S_i, S_j}; and L ≥ |S_i − S_j|.

In the first simulation, Matrix 5 is taken and the number of co-occurrences between c & d is increased by 1 in each step k, ceteris paribus. Matrix 6 gives this simulation.

In each step k the resulting relatedness matrix using Eq. 1 is subtracted from the resulting relatedness matrix using Eq. 2 and divided over the value of Eq. 2 to express the difference in percentages. The relatedness values for the pairs a & b and c & d are then plotted for each step. Each of these two changing relationships represent a different scenario:

• a&b. The changing difference in relatedness for the pair a & b simulates a steady increase in L, keeping C_ij = 1 and S_i = S_j = 3. This result is depicted in Figure 1.

• c&d. The changing difference in relatedness between classes c & d simulates a steady increase in C_ij but also in S_i and S_j, keeping L = 6. To increase C_ij beyond the maximum value of S_i and S_j, S_i and S_j also have to increase. From the partial derivatives it can be derived that an increasing C_ij would increase the difference, whereas an increase in S_i and S_j can both increase or decrease the difference. The result of the simulation is depicted in Figure 2.

The absolute difference between the calculated relatedness of Eqs. 1 and 2 for the pair a & b is equal to 1/3 across the entire simulation. However, as the number of other co-occurrences L increases, potential co-occurrence candidates increase as well, and therefore the expected number of co-occurrences for a & b decreases. As a result, relatedness values are higher as L increases and the relative difference decreases, as can be seen in Figure 1.

For pair c & d, L remains equal to 6 but C_cd, S_c, and S_d increase. Figure 2 depicts how the difference in the estimated relatedness increases asymptotically, converging from 33.3% to the value of 100%. As the $ObservedExpected$ should be close to 1 when two entities are close to having 100% of the occurrences in the sample, but the values of the original Eq. 1 converge to 2 the difference is close to 100% of the correct value.

To simulate an increase in C_ij while keeping S_i, S_j, and L equal, ceteris paribus, another simulation is needed: Matrix 1 is altered by replacing the number of co-occurrences between entities a & b and c & d by a large amount of co-occurrences x.

Then in each step k of the simulation a co-occurrence is subtracted from this amount x and added to the co-occurrences between entities a & d and b & c: See Matrix 6. This keeps S_i, S_j, and L equal but increases C_ij for the relatedness between a & d. Note that the result is insensitive to the exact value of x, as the resulting change in the denominator and numerator cancel each other out.

The result is a stable overestimation of 33.3% for all values of k. When a & d co-occur more often but the total number of co-occurrences in the sample stays the same, the relatedness between a & d naturally increases. Nonetheless, the increase in relatedness is proportional for the two formulas and therefore the difference remains 33.3%.

Last, an increase in S_i and S_j while keeping C_ij equal is simulated. The simulation is very similar to the first simulation except that in addition to increasing the co-occurrences between c & d also those between b & c are increased in each step k: See Matrix 4. As a result, S_b and Sc increase while C_bd is kept at 1. L necessarily increases as well in the form of S_c to match the added co-occurrences of S_b and S_d.

Once again the percentage difference between calculating the level of relatedness for the pair b & d using Eqs. 1 and 2 is stable at 33.3% for all values k. This time the relatedness between b & d decreases as k increases because their total number of occurrences S_b and S_d increase but their number of co-occurrences remains 1.

The simulations in this section show that the difference can range between close to 100% and close to 0. In real-world applications of co-occurrence data the bias introduced by using Eq. 1 instead of Eq. 2 will be somewhere in between the extreme scenarios simulated here, in which each respective value in the relatedness matrix will be closer to a specific scenario than others.

The theoretical and simulational explorations demonstrate that Eq. 1 overestimates the relatedness between entities compared to Eq. 2 in a way that disproportionately affects certain pairs more than other pairs. However, the question remains how close these examples are to real-world applications.

Therefore, the outcomes of Eqs. 1 and 2 are compared using United States Patent and Trademark Office (USPTO) technology class data: See Hall, Jaffe, and Trajtenberg (2001) and USPTO, from utility patents in periods of 5 years from 1855 to 2014²².

In the occurrence matrix O of each time period the rows indicate patent numbers and the columns technology classes, like the example in Matrix 1. By multiplying the transpose of O by O itself a technology classes by technology classes co-occurrence matrix C is obtained. As before, the diagonal of C is set to zero and S_i can then be calculated as the column sum of column i or the row sum of row i²³. Next Eqs. 1 and 2 are calculated using the C of each time period and the results are compared in Table 1.

Table 1 gives a number of statistics for each time period mentioned in the respective header. The first row gives the number of different technology classes (n) referred to on the patents. This number is equal to the number of columns/rows in C. The second line gives the number of pairs that have a value higher than 1 according to Eq. 1 by van Eck and Waltman (2009); these relatedness pairs have more or just as many observed co-occurrences as expected and are therefore seen as related in research within this domain (see, for example, Balland et al., 2015). The third line gives the same statistic but employs the improved Eq. 2. On line four the difference between the number of related pairs according to each formula is given²⁴. Difference (%) expresses this difference as a percentage of the number of related pairs according to the improved Eq. 2.

By focusing on these first five statistics it can be seen that in 1855–1859 patents made references to 327 different technology classes and that according to Eq. 1 5,154 pairs of technology classes can be seen as related, whereas Eq. 2 identifies 5,150 related pairs. As a result, Eq. 1 identifies four pairs or $45150$ × 100 = 0.07% more as related than Eq. 2.

In later time periods the differences increase both in absolute terms and in relative terms with a maximum in relative terms of 0.29% in 1885–1889 and a maximum in absolute terms with 62 pairs wrongly seen as related in 1955–1959.

In addition to the overestimation, another problem of using Eq. 1 instead of Eq. 2 is that the relatedness between some pairs is more overestimated than between other pairs. The last four statistics explore this disproportionality. The largest difference in value gives the largest difference in the relatedness value of a single pair between Eqs. 1 and 2, and its percentage counterpart gives the largest overestimation relative to the value given by Eq. 2. In relative terms the highest over estimation is 3.23% and occurs in 2000–2004, and this percentage is way below some of the extreme scenarios simulated in Section 5. The largest absolute difference is 0.837 in 1860–1864.

The last two statistics are similar but give the smallest difference when C_ij > 0²⁵. When at least one co-occurrence exists between a pair its relation is overestimated, as already shown mathematically in Section 4. The values are close to zero both in absolute terms and in relative terms and therefore in strong contrast to the highest values, showing that some pairs get more overestimated than others.

The results also show that there is not necessarily a direct connection between the number of technology classes and the number of related pairs or the overestimation. In 2000–2004, there is the second highest number of different technology classes, and the number of related pairs is lower than in 1950–1954 when fewer technology classes were in use.

When comparing these specific time periods, 2000–2004 turns out to have a much more concentrated co-occurrence matrix C than the one in 1950–1954. In 2000–2004 each row or column i contains a few pairs with a lot of observations whereas others have relatively few observations. This contrasts with the more even spread of observations across C in 1950–1954. The average Gini coefficient per row of C in 2000–2004 is 0.936 versus 0.909 in 1950–1954.

Very much like the simulation based on Matrix 7, where S_i and S_j were increased while keeping C_ij equal, the pairs with little co-occurrence are less overestimated when there are more occurrences of the same technology class with other classes, as is more the case in 2000–2004. The pairs with relatively high numbers of co-occurrences have a larger share of the sample in 2000–2004 compared to 1950–1954, as in Matrix 6, where C_ij is increased while S_i and S_j are kept equal; these pairs are more overestimated in 2000–2004. The pairs with relatively many co-occurrences are likely to pass the threshold of 1 using either formula, and the stronger overestimation for these pairs in 2000–2004 does not lead to much change with respect to passing this threshold. This is not the case for the pairs with relatively fewer co-occurrences, which are less overestimated in 2000–2004 than in 1950–1954. Therefore, in 2000–2004 these are less likely to pass the threshold irrespective of whether Eq. 1 or Eq. 2 is used, and in 1950–1954 these pairs are more likely to pass the threshold using Eq. 1 but not when using Eq. 2. As a result, 2000–2004 has larger overestimations of individual relatedness values but fewer pairs that are wrongly identified as related.

The comparison shows that using Eq. 1 instead of Eq. 2 in research can lead to nonnegligible differences and that some pairs and matrices are affected disproportionately. Note that with an incorrect specification of S_i, S_j, and mEq. 1 becomes even more inaccurate: See Section 4. It is unlikely that papers employing Eq. 1 instead of Eq. 2 would have reached fundamentally different conclusions, but a risk is more present in some cases than others. It is recommended to use Eq. 2 in future research.

Co-occurrence data is commonly used in various domains. Researchers generally apply normalization measures to correct for the size effect. To this end, van Eck and Waltman (2009) make a convincing case to use a probability-based measure known as the association strength, in which the number of observed co-occurences is divided over the number of expected co-occurrences, assuming that observations are randomly distributed over co-occurences.

However, the probability formula to calculate the expected number of co-occurrences is not suited for the co-occurrence analysis it is recommended for, which is when self-co-occurrences are nonexistent or irrelevant²⁶. The formula assumes combinations with repetition, meaning that an observation from an entity can be drawn again after being picked in the first draw, even though neither this occurrence nor any other occurrence belonging to the same entity can be drawn in this line of work.

This paper introduces a formula that is based on, but not equal to, combinations without repetition in which the probability of drawing entity i and j together is calculated as the probability of drawing i first and then j, knowing that none of the observations pertaining to i can be drawn plus the probability of drawing j and then i, knowing that none of the observations pertaining to j can be drawn. This formula gives the correct results, as was demonstrated in an intuitive example.

Furthermore, it is shown that the original formula overestimates the relatedness between a pair of entities compared to the improved formula introduced here when there is at least one observed co-occurrence, and that the overestimation is not proportional across pairs. Simulations show that the overestimation of the relatedness can range between virtually 0% and almost 100% of the correct value given by the improved formula. In a real-world example, a number of patent samples showed that the overestimation of individual values was between virtually 0% and 3.234%, and the difference in the number of pairs that can be seen as related can be 0.29% more than the number of pairs identified as related by the improved formula.

This paper shows that the formula presented here is better equipped for the analysis of co-occurrence data. The formula, following all recommendations for inputs and treatment, is available in the EconGeo package for R maintained by Balland (2016).

I thank Ludo Waltman, Nees Jan van Eck, Pierre-Alexandre Balland, Ron Boschma, and two anonymous referees for useful comments on this paper. All errors remain my own.

The author has no competing interests.

This work has benefited from grant 438-13-406 from JPI Urban Europe.

The data used in Section 6 comes from Hall et al. (2001) and the USPTO and is freely available from the website of the USPTO.