AI Generated Answers. Questions originally appeared on this blog and are attributed to Sayed Ahmed. New AI-generated answers, code and original examples are offered for reuse without copyright restrictions asserted by this blog; third-party assets have their own rights. Verify results and respect data privacy.
Graph Mining – 1 course index · Original question source: Graph Mining: Link Prediction · Questions 11.20–11.37.
Q11.20. If two nodes do not have any common node — what is the probable similarity (Node Neigh. aspect)?
Answer. With no common neighbors, CN, Jaccard’s numerator, and Adamic–Adar are zero. That does not mean there can never be a future link: global features, attributes, or external events can still support a connection.
Q11.21. What is Common Neighbors ? Is it local or global structure? is it Node Neighbor or Preferential Attachment? and why?
Answer. Common Neighbors is CN(u,v)=|N(u)∩N(v)|. It is local and neighbor-overlap-based; it is not the degree-product preferential attachment score.
Q11.22. What is Jaccard Coefficient ? Is it local or global structure? is it Node Neighbor or Preferential Attachment? and why?
Answer. Jaccard similarity is J(u,v)=|N(u)∩N(v)| / |N(u)∪N(v)| (with an agreed rule when the union is empty). It normalizes common neighbors by neighborhood size and is local.
Q11.23. What is Adamic-Adar? Is it local or global structure? is it Node Neighbor or Preferential Attachment? and why?
Answer. Adamic–Adar is AA(u,v)=Σ_{z∈N(u)∩N(v)} 1/log(deg(z)), for common neighbors with degree>1. Rare shared neighbors contribute more than popular hubs. It is a local overlap score.
Q11.24. What is the name of the Node Similarity approach where Sum of the inverse logarithmic degree centrality of the neighbors shared by the two nodes are counted?
Answer. Adamic–Adar index. Each shared neighbor contributes inverse logarithmic degree weight, which decreases as that neighbor’s popularity grows.
Q11.25. What is the name of the Node Similarity approach where the ratio of seize of set intersection to the set union is counted?
Answer. Jaccard coefficient. It is the intersection-over-union of the two neighborhood sets.
Q11.26. What is the name of the Node Similarity approach where the count of common nodes are used?
Answer. Common Neighbors index. It counts shared adjacent vertices directly.
Q11.27. If node similarity score is counted as multiplication of the number/count of outgoing edges for a node pair. And then the higher results are assumed to create new links. What is this approach called?
Answer. Preferential attachment is the product of endpoint degrees in an undirected graph; for a directed graph use a clearly specified product such as source out-degree times destination in-degree, depending on the predicted edge orientation.
Q11.28. When similarity scores are calculated based on global link structure of graph – what is this called local structure or global structure?
Answer. That is a global-structure score if it uses information across the graph rather than only local neighborhoods.
Q11.29. What is an example of Global Structure?
Answer. Katz similarity is one example because it counts paths/walks of multiple lengths. Another is SimRank, which recursively compares neighbor similarities.
Q11.30. What are the examples of Global Structure?
Answer. Examples: Katz, SimRank, Personalized PageRank, commute-time/resistance proximity, and spectral or embedding-based global similarities. Different ones penalize path length and topology differently.
Q11.31. What is Kartz Index for Global Structure?
Answer. The correct name is Katz index, not ‘Kartz’. With adjacency matrix A, Katz(u,v)=Σ_{ℓ=1}^{∞} β^ℓ (A^ℓ)[u,v] for sufficiently small β, commonly β<1/ρ(A). It gives shorter walks greater influence.
Q11.32. What is Simrank for Global Structure?
Answer. SimRank captures the intuition ‘two nodes are similar if they are related to similar nodes’. A standard recurrence uses the average SimRank between all pairs of their in-neighbors, multiplied by decay C∈(0,1), with s(u,u)=1.
Q11.33. When Node Similarity is calculated as: Sum of count of all paths between node pairs – what is this approach called? Then how is the link prediction made?
Answer. Counting all length-weighted walks between a pair identifies Katz similarity (not an unweighted infinite raw count). Rank candidate nonedges by Katz score; tune β and validate on future edges.
Q11.34. When Node Similarity is calculated as: two nodes are similar if they are referred by similar nodes. What is the name?
Answer. That is SimRank. Nodes with similar incoming-neighbor patterns can receive high similarity recursively even without direct edges.
Q11.35. How can you measure if your implemented link prediction algorithm is great or not?
Answer. Use temporal or otherwise leakage-free held-out edges, compare against a simple baseline, report ranking/classification metrics, and check stability over different time windows. A good method should generalize rather than memorize training edges.
Q11.36. Can you use train and test concept for the measurement? Can you define the steps/problems formally? with Graph Notations?
Answer. Yes. Split observed edges by time: build G_train=(V,E_≤t), score eligible nonedges using G_train only, label positives that first appear in (t,t+Δ], and sample appropriately defined nonedges as negatives. Avoid giving the model test-period edges or future features.
Q11.37. What are some measures to calculate in the train/test approach?
Answer. Use precision@k, recall@k, average precision/PR-AUC, ROC-AUC, F1 at a selected threshold, and calibration if probabilities are claimed. Positive links can be extremely rare, so raw accuracy alone is usually misleading.
Worked example: local similarity and candidate ranking
import networkx as nx
G = nx.Graph()
G.add_edges_from([(0,1),(0,2),(1,2),(1,3),(2,3),(3,4)])
# Candidate link 0-3 is absent but both endpoints share 1 and 2.
print("Common neighbors:", list(nx.common_neighbors(G,0,3)))
# [1, 2]
print("Jaccard:", list(nx.jaccard_coefficient(G,[(0,3)]))[0][2])
# 0.6666666666666666
print("Preferential attachment:",
list(nx.preferential_attachment(G,[(0,3)]))[0][2])
# 6
print("Adamic-Adar:", list(nx.adamic_adar_index(G,[(0,3)]))[0][2])
# Approximately 1.8205 = 2 / ln(3)
# Rank all current nonedges (undirected graph)
ranked = sorted(nx.jaccard_coefficient(G),
key=lambda t:t[2], reverse=True)
print("Top predicted links:", ranked[:5])
# These scores do not imply that an edge will actually form.
Temporal evaluation and privacy checklist
Use training edges only up to the cutoff time; score eligible future candidates; use future links solely for evaluation. Compare precision@k and PR-AUC against a degree-product or common-neighbor baseline. Respect consent and avoid disclosing private relationships or sensitive inferences about individuals.
