# How to convert an unrestricted co-occurrence network to a restricted one?

I have built an unrestricted co-occurrence network of words from a songs corpus. To convert it to a restricted network, Ramon Ferrer Cancho and Ricard V. Sole describe the following approach in their paper The small world of human language:

The technique can be improved by choosing only pairs of consecutive words, the mutual co-occurrence of which is larger than expected by chance. This can be measured with the condition $p_{ij} > p_i*p_j$, which defines the presence of correlations beyond that expected from a random ordering of words. If a pair of words co-occurs less than expected when independence between such words is assumed, the pair is considered to be spurious. Graphs in which this condition is used will be called restricted (unrestricted otherwise).

Word pairs are considered as co-occurring if they occur within a maximum distance of 2 within a song. Here, $i$ and $j$ are the two words; $p_{ij}$ is the probability that the two words co-occur. If $i$ and $j$ are statistically independent, then the probability that they co-occur is given by the product $p_{i}\cdot p_{j}$. If they are not independent, and they have a tendency to co-occur, then $p_{ij}$ will be greater than $p_{i}\cdot p_{j}$.

I am confused on how to calculate $p_{ij}$, $p_{i}$, and $p_{j}$. For example, to calculate $p_{i}$, can I take the count of all occurrences of $i$ divided by total number of songs in my corpus? Alternatively, $p_{i}$ can also be calculated by dividing count of all occurrences of $i$ by total number of words in the corpus. Which would be right approach out of the two?

Similarly, to calculate $p_{ij}$, can I take the count of co-occurences of $i$ and $j$ divided by total number of words or total number of possible co-occurring word pairs?

EDIT: Moreover, If $i$ and $j$ are statistically independent, then shouldn't the probability that they co-occur be given by $4∗p_{i}⋅p_{j}$ since word pairs are considered as co-occurring if they occur within a maximum distance of 2 within a song.

• If you observe that a word can occur multiple times in a song, which implies a word count divided by a song count can exceed unity--impossible for a probability--your questions answer themselves. – whuber Jun 10 '11 at 21:29
• Thanks, whuber, that makes sense. But what about $p_{ij}$, should I divide the count of co-occurences of $i$ and $j$ by total number of words or total number of possible co-occurring word pairs? – stressed_geek Jun 11 '11 at 7:45
• Moreover, If $i$ and $j$ are statistically independent, then shouldn't the probability that they co-occur be given by $4*p_{i}\cdot p_{j}$ since word pairs are considered as co-occurring if they occur within a maximum distance of 2 within a song. – stressed_geek Jun 11 '11 at 7:52

One usually estimates probabilities with frequencies: according to Laplace (1814),

The ratio of this number [of "favorable cases"] to that of all the cases possible is the measure of this probability...

This is justified by an urn model (or "tickets in a box" model) of probability: print the text on paper, cut out each word, and drop them into a box. Imagine creating "sentences" by randomly drawing one piece of paper from the box, writing the word seen on it, returning the paper to the box (to leave its contents unchanged), and repeating. The number of "favorable cases" for any word is the number of slips of paper on which it is written. The number of "all cases possible" is the total number of slips of paper in the box.

Therefore, to compute $p_i$, you count two things: $n$, the number of words in a text, and $n_i$, the number of words that match word $i$. Then $p_i = n_i/n$.

For example, in the sentence

I once had a girl; or should I say, she once had me.

there are $n=13$ words. We would compute $p_{\text{once}} = 2/13$, $p_{\text{she}} = 1/13$, $p_{\text{boy}} = 0/13$, etc.

With this model we can compute the probability of a "co-occurrence." This (in your situation) is the chance that word $i$ is followed by word $j$ in a random sequence of three words drawn as described.

Continuing the example, let's compute the probability of co-occurrence of "she had." This can be done with a probability tree:

• The chance that the first word is "she" equals $1/13$.

• Conditional on the first word being "she", there is a $2/13$ chance that the second word is "had". Thus there is a $1/13 \cdot 2/13$ chance of "she had ...".

• Conditional on the first word being "she" and the second not being "had", there is a $2/13$ chance that the third word is "had". Because the chance of the second word not being "had" is $11/13$, this conditional probability equals $1/13 \cdot 11/13 \cdot 2/13$. It is the chance of "she ... had" where "..." is not "had."

• Conditional on the first word not being "she", the chance that the second is "she" and the third is "had" equals $1/13 \cdot 2/13$. Because the chance of the first word not being "she" is $12/13$, the conditional chance equals $12/13 \cdot 1/13 \cdot 2/13$. It is the chance of "... she had" where "..." is not "she."

These three conditional events are mutually exclusive, allowing us to add their chances. Whence the chance of co-occurrence of "she had" is

$$p_{ij} = 1/13 \cdot 2/13 + 1/13 \cdot 11/13 \cdot 2/13 + 12/13 \cdot 1/13 \cdot 2/13 = 72/2197 = 0.032772.$$

Note that $p_i \cdot p_j = 1/13 \cdot 2/13 = 2/169 = 26/2197 = 0.0118343.$ In particular, it is definitely not the case that $p_{ij} = p_i \cdot p_j$ under this probability model. Moreover, the ratio $p_{ij} / (p_i p_j) = 36/13$ is none of the intuitively "obvious" values $1$, $3$, or $4$ (it is slightly less than $3$).

Comparing a co-occurrence probability to frequencies within an actual text is challenging because the $n-2$ sequences of three words that do appear in the text are not independent. For instance, consider co-occurrences of "once had" in the preceding example. The initial sequence "I once had" is a co-occurrence. It guarantees that the second sequence, "once had a" also is a co-occurrence. However, it lowers the chances that the third sequence is a co-occurrence, because the third sequence must begin with "had," making it impossible to begin with "once." People often address this by computing expected values of the frequencies. Returning to the probability tree calculation, we find the expected number of co-occurrences of "she had" in a random sequence of three words, counting "she she had" as just one co-occurrence, is $72/2179$. Therefore the expected number of such co-occurrences in a sentence of 13 words, which contains 11 such sequences, equals $11 \cdot 72/2179 = 792/2179 = 0.36$. That does not depart significantly from the observed number, $1$.

What these considerations teach us is that any research that applies probability to co-occurrence networks needs to be clear and specific about (a) how probability is being applied: that is, what probability model is used; and (b) how co-occurrences will be identified and their frequencies computed. It is evident, though, that the formula $p_{ij} = p_i \cdot p_j$ (for independently drawn words $i$ and $j$) is unlikely to be even approximately true when a "co-occurrence" can include one intermediate word between $i$ and $j$.

• Thanks, for the detailed answer, but I think I didn't frame my doubt properly. I thought it would be inappropriate to change the problem statement now completely after your answer, so I have started another thread with a much clearer problem statement – stressed_geek Jul 20 '11 at 10:59
• @stressed That's a good way to approach the situation, because the new question does address a different aspect of your problem. For the record, that question is here – whuber Jul 20 '11 at 12:35