linkpredict

func DefaultBuildConfig ¶

func DefaultBuildConfig() *BuildConfig

DefaultBuildConfig returns sensible defaults.

func BuildGraphFromEngine ¶

func BuildGraphFromEngine(ctx context.Context, engine storage.Engine, undirected bool) (Graph, error)

BuildGraphFromEngine constructs a Graph from a storage engine.

This creates an in-memory adjacency representation optimized for link prediction algorithms. For large graphs (>1M nodes), consider sampling or using candidate generation to limit memory usage.

OPTIMIZED: This function now uses streaming construction with:

• Chunked processing to avoid memory spikes
• Parallel edge fetching for 4-8x speedup
• GC hints between chunks
• Context cancellation support

Parameters:

• ctx: Context for cancellation
• engine: Storage engine implementing GetOutgoingEdges
• undirected: If true, treats edges as bidirectional

Example:

engine := storage.NewMemoryEngine()
// ... populate with nodes and edges ...

// Build undirected graph (social network)
graph := linkpredict.BuildGraphFromEngine(ctx, engine, true)

// Build directed graph (citation network)
graph = linkpredict.BuildGraphFromEngine(ctx, engine, false)

func BuildGraphFromEngineOptimized ¶

func BuildGraphFromEngineOptimized(
	ctx context.Context,
	engine storage.Engine,
	config *BuildConfig,
) (Graph, error)

BuildGraphFromEngineOptimized is the optimized replacement for BuildGraphFromEngine.

This version provides:

• Streaming construction (fixes memory spikes)
• Parallel edge fetching (4-8x speedup)
• Context cancellation support
• Optional progress callbacks

Parameters:

• ctx: Context for cancellation
• engine: Storage engine
• config: Build configuration (nil uses defaults)

Example:

config := &linkpredict.BuildConfig{
	ChunkSize:   500,
	WorkerCount: 4,
	Undirected:  true,
	ProgressCallback: func(p, t int, e time.Duration) {
		fmt.Printf("Progress: %d/%d (%.1fs)\n", p, t, e.Seconds())
	},
}
graph, err := linkpredict.BuildGraphFromEngineOptimized(ctx, engine, config)

func ImportFromReader ¶

func ImportFromReader(r io.Reader) (Graph, error)

ImportFromReader reads a graph from simple text format (tab-separated node pairs).

func NewGraphBuilder ¶

func NewGraphBuilder(engine storage.Engine, config *BuildConfig) *GraphBuilder

NewGraphBuilder creates a new optimized graph builder.

func NewGraphStreamer ¶

func NewGraphStreamer(engine storage.Engine, config *BuildConfig) *GraphStreamer

NewGraphStreamer creates a streamer for very large graphs.

func DefaultHybridConfig ¶

func DefaultHybridConfig() HybridConfig

DefaultHybridConfig returns balanced configuration for general use.

func NewHybridScorer ¶

func NewHybridScorer(config HybridConfig) *HybridScorer

NewHybridScorer creates a new hybrid scorer with the given configuration.

func DefaultParallelScoreConfig ¶

func DefaultParallelScoreConfig() *ParallelScoreConfig

DefaultParallelScoreConfig returns defaults for parallel scoring.

func AdamicAdar ¶

func AdamicAdar(graph Graph, source storage.NodeID, topK int) []Prediction

AdamicAdar computes link predictions using Adamic-Adar index.

Algorithm: score(u, v) = Σ(1 / log(|N(z)|)) for z in N(u) ∩ N(v)

Weights common neighbors by their rarity. A common neighbor with few connections is a stronger signal than a highly-connected one.

Intuition: If you and I both know a person who knows everyone, that's weak evidence we should connect. But if we both know someone exclusive, that's strong evidence.

Pros:

• Weights rare connections higher (less noise)
• Often outperforms simpler methods
• Well-studied in literature

Cons:

• Requires degree calculation
• Undefined for degree-1 nodes (uses log)

Example:

predictions := linkpredict.AdamicAdar(graph, "user-789", 15)
for _, p := range predictions {
	fmt.Printf("→ %s: %.3f weighted score\n", p.TargetID, p.Score)
}

Reference: Adamic & Adar (2003), "Friends and neighbors on the Web"

func CommonNeighbors ¶

func CommonNeighbors(graph Graph, source storage.NodeID, topK int) []Prediction

CommonNeighbors computes link predictions based on common neighbor count.

Algorithm: score(u, v) = |N(u) ∩ N(v)|

This is the simplest structural heuristic. Two nodes with many shared neighbors are likely to connect.

Pros:

• Very fast (O(deg(u) * deg(v)))
• Intuitive and explainable
• Works well for social networks

Cons:

• Biased toward high-degree nodes
• Doesn't account for neighbor importance

Example 1 - Friend Recommendations:

graph := linkpredict.BuildGraphFromEngine(ctx, engine, true)
predictions := linkpredict.CommonNeighbors(graph, "alice", 5)

fmt.Println("People Alice should meet:")
for _, p := range predictions {
	fmt.Printf("  → %s: %d mutual friends\n", p.TargetID, int(p.Score))
}
// Output:
//   → diana: 3 mutual friends
//   → emily: 2 mutual friends

Example 2 - Research Collaboration Network:

// Build citation graph
graph := linkpredict.BuildGraphFromEngine(ctx, engine, false)

// Find potential collaborators for a researcher
predictions := linkpredict.CommonNeighbors(graph, "researcher-123", 10)

for _, p := range predictions {
	// High common neighbor count = strong collaboration potential
	if p.Score >= 3 {
		fmt.Printf("Strong collaboration signal: %s\n", p.TargetID)
		sendCollabInvite(p.TargetID)
	}
}

Example 3 - Document Clustering:

// Documents connected by citations or references
graph := buildDocumentGraph(documents)

// Find related documents
predictions := linkpredict.CommonNeighbors(graph, "paper-456", 20)

relatedDocs := make([]string, 0)
for _, p := range predictions {
	if p.Score >= 2 { // At least 2 common references
		relatedDocs = append(relatedDocs, string(p.TargetID))
	}
}

createCluster(relatedDocs)

ELI12:

Imagine you're at a party and want to find new friends. Common Neighbors says: "Count how many friends you have IN COMMON with each person."

• You and Sarah both know: Alex, Jamie, Charlie → 3 common friends
• You and Mike both know: Alex → 1 common friend
• Prediction: You should meet Sarah! (higher score)

It's like Facebook's "People You May Know" - they show you people who have lots of mutual friends with you, because you probably move in similar circles!

Real-world Example:

• You know: [Alice, Bob, Charlie, Diana]
• Sarah knows: [Bob, Charlie, Diana, Emily]
• Common: [Bob, Charlie, Diana] = 3 friends
• Score: 3 (raw count)

Pros & Cons:

✅ Simple and intuitive
✅ Works well for social networks
✅ Fast to compute
❌ Biased toward popular nodes (everyone knows them!)
❌ Doesn't normalize by total friends

Performance:

• O(|neighbors| × avg_degree) per source node
• Fast for sparse graphs (most real-world graphs)
• Memory: O(candidates) for score tracking

func Jaccard ¶

func Jaccard(graph Graph, source storage.NodeID, topK int) []Prediction

Jaccard computes link predictions using Jaccard coefficient.

Algorithm: score(u, v) = |N(u) ∩ N(v)| / |N(u) ∪ N(v)|

Normalizes common neighbors by total neighborhood size, reducing bias toward high-degree nodes.

Score Range: [0.0, 1.0]

• 0.0: No common neighbors
• 1.0: Identical neighborhoods

Pros:

• Normalized (comparable across node pairs)
• Less biased than raw common neighbors
• Standard similarity measure

Cons:

• May underweight important connections
• Sensitive to degree imbalance

Example 1 - Document Similarity:

graph := buildDocumentGraph(documents)
predictions := linkpredict.Jaccard(graph, "paper-123", 10)

fmt.Println("Similar documents:")
for _, p := range predictions {
	fmt.Printf("  → %s: %.1f%% overlap\n", p.TargetID, p.Score*100)
}
// Output:
//   → paper-789: 45.2% overlap (high similarity)
//   → paper-456: 12.8% overlap (moderate)

Example 2 - Balanced Friend Recommendations:

graph := linkpredict.BuildGraphFromEngine(ctx, engine, true)

// Jaccard normalizes for degree (better than raw common neighbors)
predictions := linkpredict.Jaccard(graph, "user-123", 5)

for _, p := range predictions {
	// 0.3 = 30% of combined neighborhood overlaps
	if p.Score > 0.3 {
		fmt.Printf("Strong match: %s (%.0f%% similar networks)\n",
			p.TargetID, p.Score*100)
	}
}

Example 3 - Tag-Based Content Recommendation:

// Items connected by shared tags
graph := Graph{
	"movie-action-1": {"action": {}, "scifi": {}, "thriller": {}},
	"movie-action-2": {"action": {}, "scifi": {}, "drama": {}},
	"movie-comedy-1": {"comedy": {}, "romance": {}},
}

predictions := linkpredict.Jaccard(graph, "movie-action-1", 10)

for _, p := range predictions {
	// High Jaccard = similar tag profiles
	fmt.Printf("Recommend %s: %.2f similarity\n", p.TargetID, p.Score)
}
// movie-action-2 will rank high (2/4 = 0.5 Jaccard)

ELI12:

Jaccard is like comparing your playlist with a friend's:

Your songs: [A, B, C, D, E] = 5 songs
Friend's songs: [C, D, E, F, G] = 5 songs
In common: [C, D, E] = 3 songs

Jaccard = 3 / (5 + 5 - 3) = 3/7 = 42.9% similar taste!

Why subtract 3? Because C, D, E appear in BOTH lists, so we don't count them twice in the total. That's the "union" part.

Compare to Common Neighbors:

• Common Neighbors: "You share 3 songs" (raw count)
• Jaccard: "42.9% of your combined music overlaps" (percentage)

Jaccard is BETTER when comparing things of different sizes:

• You: 100 friends, share 10 with Alice

• You: 20 friends, share 10 with Bob

  Common Neighbors: Both score 10 (seems equal) Jaccard: Alice = 10/110 = 9%, Bob = 10/30 = 33% (Bob is closer!)

Real-world Use:

• Content recommendation (movies, articles, products)
• Duplicate detection (similar documents, profiles)
• Community detection (overlapping friend groups)

Pros & Cons:

✅ Normalized (0-1 range, comparable)
✅ Handles different network sizes fairly
✅ Standard similarity metric
❌ Sensitive to rare connections (small denominator)
❌ Slower than raw common neighbors

Performance:

• O(|N(u)| + |N(v)|) per candidate pair
• Requires set intersection/union calculation
• Memory: O(candidates) for tracking

func PreferentialAttachment ¶

func PreferentialAttachment(graph Graph, source storage.NodeID, topK int) []Prediction

PreferentialAttachment computes link predictions based on node degree product.

Algorithm: score(u, v) = |N(u)| * |N(v)|

Models the "rich get richer" phenomenon: high-degree nodes tend to acquire more connections. Common in scale-free networks (social media, citation networks, the web).

Pros:

• Extremely fast (O(1) per candidate)
• No neighbor intersection needed
• Captures growth dynamics

Cons:

• Strongly biased toward hubs
• Ignores local structure
• Not similarity-based

Example:

predictions := linkpredict.PreferentialAttachment(graph, "paper-123", 10)
for _, p := range predictions {
	fmt.Printf("→ %s: %.0f degree product\n", p.TargetID, p.Score)
}

Reference: Barabási & Albert (1999), "Emergence of scaling in random networks"

func ResourceAllocation ¶

func ResourceAllocation(graph Graph, source storage.NodeID, topK int) []Prediction

ResourceAllocation computes link predictions using resource allocation index.

Algorithm: score(u, v) = Σ(1 / |N(z)|) for z in N(u) ∩ N(v)

Similar to Adamic-Adar but uses linear weighting instead of logarithmic. Models resource transmission through common neighbors.

Intuition: Each common neighbor sends a "resource" unit to the target. If the neighbor has many connections, the resource is divided among them.

Pros:

• Simpler than Adamic-Adar (no log)
• Often performs comparably
• Intuitive "spreading" interpretation

Cons:

• Similar limitations to Adamic-Adar
• Undefined for degree-0 nodes

Example:

predictions := linkpredict.ResourceAllocation(graph, "concept-456", 20)
for _, p := range predictions {
	fmt.Printf("→ %s: %.3f resource score\n", p.TargetID, p.Score)
}

Reference: Zhou et al. (2009), "Predicting missing links via local information"