Common neighbor count

As explained in Graph Algorithms for Data Science

Common neighbor count is the number of nodes directly connected to both members of a node pair, often used as a link-prediction score.

Common neighbor count measures neighborhood overlap for a pair of nodes: count the distinct nodes connected to both. As a link-prediction feature, a larger count suggests a greater chance that the pair will form a future connection. section 10.3.3 section 10.1

The measure fits situations where shared contacts create opportunities to meet. Two people with many mutual friends are more likely to encounter one another; likewise, Twitch streams with overlapping audiences through an intermediate stream may develop a direct audience-overlap link. section 10.0 section 10.3.3

To prepare common neighbor count for a link-prediction model:

• Start with node pairs marked by TEST_TRAIN or NEGATIVE_TEST_TRAIN relationships, where the pair has no direct connection. section 10.3.3
• Match neighbors shared by both endpoints and count distinct shared nodes. section 10.3.3
• Use OPTIONAL MATCH so pairs with no shared neighbors remain in the results. section 10.3.3
• Store the count as the commonNeighbor property on the pair relationship for model training or testing. section 10.3.3

Mutual friends as a prediction signal

If Luke and Rajiv are closer in a friendship network because they share friends, they are a stronger future-link candidate than Jose and Alice. The count is not a guarantee; it is one feature describing how much two nodes' neighborhoods overlap. section 10.0 section 10.1

Figure 10.10 Common neighbors between a pair of nodes

Use the diagram to inspect the intermediate nodes that belong to both endpoints' neighborhoods before counting them. section 10.3.3

Common neighbor count can be evaluated alongside other pair features. In one trained model, it was among the relevant features, behind the Adamic-Adar index and ahead of network distance in feature importance. section 10.4.3

How Graph Algorithms for Data Science covers it

How deep it goes

Works through counting distinct shared neighbors, retaining zero-count pairs, and storing the result as a relationship property.

Examples

Uses mutual friends in a social network and shared Twitch-stream audiences to illustrate future links.

What it assumes

Assumes prepared train and test node pairs without direct links while teaching the shared-neighbor calculation.

What you can do after

Apply it via Cypher matching to calculate and store commonNeighbor values for train and test node pairs.

How it connects

Connects link prediction with neighborhood overlap, Adamic-Adar index, preferential attachment, network distance, and node-pair features.

liveBookmanning.com

Read Graph Algorithms for Data Science on liveBook Get the book at manning.com

Related concepts

• Adamic-Adar indexused by · The Adamic-Adar index is a link-prediction metric that scores node pairs by weighting common neighbors more highly when they have lower degree.
• node degreemeasures · Node degree is the number of edges or relationships directly incident to a node, with direction, self-loops, and structural conventions determining how connections are counted.
• link predictionuses · Link prediction is a graph-learning task that estimates whether a connection exists or may occur between nodes, often by scoring candidate links.
• clustering coefficientmeasured by · A clustering coefficient is a graph metric measuring the extent to which relevant neighboring vertices are connected to one another.
• optional match clauseuses · An OPTIONAL MATCH clause is a Cypher query clause that preserves rows when a pattern is absent by binding the unmatched elements to null.
• link prediction featureuses · A link prediction feature is an input variable that represents similarity, distance, or structural evidence for a prospective relationship between two nodes.

This explainer was generated by Manning's knowledge graph from the text of Graph Algorithms for Data Science. The section links point to the parts of the book it draws on.