Skip to main content

Module cocitation

igraph

Module cocitation 

Source
Expand description

Cocitation, bibliographic coupling and vertex similarity (igraph_cocitation.h).

This module binds the functions of igraph’s igraph_cocitation.h header (documented in the Similarity measures section of the Structural chapter of the C manual) as methods of Graph. They all measure how similar two vertices are by looking at the neighbors they share:

  • cocitation: how many vertices cite (point to) both of them;
  • bibliographic coupling: how many vertices both of them cite;
  • Jaccard similarity: |N(u) ∩ N(v)| / |N(u) ∪ N(v)|;
  • Dice similarity: 2 |N(u) ∩ N(v)| / (|N(u)| + |N(v)|), a monotone function of the Jaccard one (D = 2J / (1 + J));
  • inverse log-weighted similarity (Adamic–Adar): common neighbors, each weighted by 1 / ln(degree), so that sharing a rare neighbor counts more than sharing a hub.

Such scores are the classic baseline for link prediction: two non-adjacent vertices with many common neighbors are likely to become connected.

§Example

use igraph::prelude::*;

// The citation network of igraph's own example: 0 -> 1, 2 -> 1, 2 -> 0, 3 -> 0.
let g = Graph::from_edges(&[(0, 1), (2, 1), (2, 0), (3, 0)], 4, true)?;

// 0 and 1 are both cited by 2.
let cocit = g.cocitation(..)?;
assert_eq!(cocit[(0, 1)], 1.0);
// 2 and 3 both cite 0; 0 and 2 both cite 1.
let bib = g.bibcoupling(..)?;
assert_eq!((bib[(2, 3)], bib[(0, 2)]), (1.0, 1.0));

// Ignoring directions, 1 and 2 share the neighbor 0 out of {0, 1, 2}.
let jac = g.similarity_jaccard(1..3, 1..3, NeighborMode::All, false)?;
assert!((jac[(0, 1)] - 1.0 / 3.0).abs() < 1e-12);
let dice = g.similarity_dice_pairs(&[(1, 2)], NeighborMode::All, false)?;
assert!((dice[0] - 0.5).abs() < 1e-12);

§Provided functionality

C functionMethod of GraphResult
igraph_cocitationcocitationMatrix, one row per selected vertex
igraph_bibcouplingbibcouplingMatrix, one row per selected vertex
igraph_similarity_inverse_log_weightedsimilarity_inverse_log_weightedMatrix, one row per selected vertex
igraph_similarity_jaccardsimilarity_jaccardMatrix from × to
igraph_similarity_jaccard_pairssimilarity_jaccard_pairsVec<f64>, one value per pair
igraph_similarity_jaccard_essimilarity_jaccard_esVec<f64>, one value per edge
igraph_similarity_dicesimilarity_diceMatrix from × to
igraph_similarity_dice_pairssimilarity_dice_pairsVec<f64>, one value per pair
igraph_similarity_dice_essimilarity_dice_esVec<f64>, one value per edge

All the functions of the header are covered.

§Differences from the C functions

These wrappers are safer than the C functions they bind, and give the results the C documentation promises in cases where igraph 1.0.1 does not:

  • igraph_similarity_jaccard and igraph_similarity_dice fill the matrix as if from and to were the same vertex list. If they differ, the results are wrong, and when from is longer than to the C code writes past the end of the matrix. similarity_jaccard and similarity_dice call them only when the two lists are identical and have no repeated vertex. Otherwise they compute every from × to pair with the *_pairs function.
  • When a vertex appears several times in vids, igraph_cocitation, igraph_bibcoupling and igraph_similarity_inverse_log_weighted fill only its last row and leave the other rows at zero. The wrappers fill every row.
  • On a directed graph, the Jaccard and Dice functions clear igraph’s property cache around the C call. Otherwise a cached “no multi-edges” flag would count each mutual pair u -> v, v -> u twice with NeighborMode::All (see crate::structural).

§See also