Graph Mining – 1 | 06. Shared Nearest Neighbor Clustering — Questions and Answers

AI Generated Answers. The original questions come from graph-mining posts on this blog and are attributed to Sayed Ahmed. These new AI-generated answers and original examples are offered for reuse without copyright restrictions asserted by the blog; cited external material keeps its own licensing. Please test the code and assumptions.

Graph Mining – 1 course index · Original question posts: Shared Nearest Neighbors and repost.

Algorithm choice throughout: For a simple, reproducible SNN variant, score only candidate pairs joined by an original edge; threshold common open-neighborhood counts; then take connected components. This is one specified variant, not a claim that all SNN algorithms give the same output.

Q06.01. What is one another name of the algorithm: Shared Nearest Neighbors?

Answer. A closely related method is Jarvis–Patrick clustering, which compares shared k-nearest neighbors. ‘Shared Nearest Neighbor (SNN)’ may denote a similarity measure or a family of clustering methods; variants are not identical.

Q06.02. What is the purpose of the Algorithm: Shared Nearest Neighbors?

Answer. SNN aims to cluster nodes or data points whose neighbor sets overlap substantially, discovering groups with similar local context. It is useful when direct distance alone is less informative than shared neighborhood structure.

Q06.03. Can you name other Algorithms that serve the same or similar purpose?

Answer. Other methods include Louvain, Leiden, label propagation, Girvan–Newman, spectral clustering, clique percolation, DBSCAN, and traditional hierarchical clustering. Compare objectives and whether overlapping clusters are needed.

Q06.04. What is the Criteria that SNN uses?

Answer. The central criterion is the size or weighted significance of the intersection of two nodes’ neighbor sets. An SNN similarity can be s(u,v)=|N_k(u)∩N_k(v)|. Higher overlap suggests greater local similarity.

Q06.05. Is SNN Hierarchical? What does Hierarchical mean in the context of Clustering/Community detection?

Answer. Not necessarily. The simple thresholded SNN graph plus connected components is a flat clustering method, not a hierarchical one. Hierarchical clustering builds nested groups, often represented by a dendrogram. Some SNN variants can be used inside a hierarchical procedure.

Q06.06. How does SNN work? i.e. what is the algorithm? i.e. how does SNN create clusters/communities?

Answer. Choose a neighbor set for each node, calculate shared-neighbor scores for candidate pairs, keep pairs whose score exceeds a chosen threshold τ, and take connected components of the resulting SNN graph. A density-based SNN variant may instead treat highly connected points as cores; the precise algorithm must be stated.

Q06.07. Give and explain the steps in SNN with a small example.

Answer. Example: if N(A)={B,C,D} and N(E)={B,C,F}, their common-neighbor count is 2 (B and C). If τ=2 they qualify as a similar pair; if τ=3 they do not. Repeat for candidate pairs and obtain communities from retained links.

Q06.08. What is threshold τ in the SNN algorithm? Is it numeric? What can be the maximum and the minimum values?

Answer. τ is the minimum shared-neighbor score needed to retain a candidate pair. With unweighted lists of at most k neighbors, τ is an integer in 0…k; practical thresholds are usually ≥1. If unrestricted open neighborhoods are used, the maximum depends on graph size and degrees.

Q06.09. For the following Undirected and unweighted Graphs, show the steps and the final clusters. Edges: {0, 1} {0, 2} {0, 3} {1, 2}, {1, 3} {2, 3} {2, 4} {3, 4} You can draw the graph first. You can use τ = 2.

Answer. Take the given undirected edges among 0–4. Open neighborhoods are N0={1,2,3}, N1={0,2,3}, N2={0,1,3,4}, N3={0,1,2,4}, N4={2,3}. Assumption: compare only pairs already connected by an original edge; retain an edge when common-neighbor count ≥τ=2. Retained edges are (0,1),(0,2),(0,3),(1,2),(1,3),(2,3), while (2,4),(3,4) fail. Result: communities {0,1,2,3} and {4}. If you allow all node pairs as candidates, results differ: (0,4) and (1,4) each share two neighbors and may join the clusters.

Q06.10. What is Node Similarity or Node Proximity between two nodes in SNN?

Answer. Node proximity is a numerical similarity between candidate vertices, often |N(u)∩N(v)| or |N_k(u)∩N_k(v)|. Alternatives normalize by union size, neighbor popularity, or edge weight.

Q06.11. What is the output of SNN? i.e. on an undirected and unweighted Graph?

Answer. The output may be a weighted SNN similarity graph, a thresholded graph, or a vertex partition (connected components/clusters), depending on the variant. Explicitly distinguish the constructed graph from its resulting cluster labels.

Q06.12. Will the output will have weights on the edges?

Answer. Intermediate SNN graphs can have edge weights equal to shared-neighbor scores even when the input graph is unweighted. If the next step thresholds the scores, the final retained graph may instead be unweighted; both are valid outputs by design.

Q06.13. Give the pseudocode for SNN algorithm

Answer. Pseudocode: for each vertex u, obtain N_k(u); for each candidate pair (u,v), calculate s=|N_k(u)∩N_k(v)|; if s≥τ add edge to an SNN graph; compute connected components or apply a specified SNN-density rule; return the groups and parameters.

Q06.14. Implement the SNN algorithm in Python or R or Matlab – whichever you prefer.

Answer. Use the NetworkX implementation in the worked example below. It computes shared-neighbor scores on existing edges, retains those meeting τ, and returns connected components. Compare its output with the hand-worked five-node example.

Q06.15. Can you apply SNN on weighted Graphs?

Answer. Yes. One option is to select each node’s top-k neighbors according to similarity weights and count overlaps of the top-k lists. Another is a weighted overlap or weighted Jaccard score. Do not rank by largest weight if the input weights are distances (where smaller means nearer).

Q06.16. If you can apply SNN on weighted graphs, then how will you apply the Threshold, say theta?

Answer. With weighted graphs, define two decisions distinctly: an edge-strength rule such as weight≥θ to determine eligible neighbors, and an SNN count threshold sharedNeighbors≥τ for retaining pairs. Other definitions are possible; provide the chosen rule in your report.

Q06.17. What is the first step in applying theta – if that is doable?

Answer. First specify what the weights mean, whether larger indicates stronger similarity, and how k-nearest or θ-qualified neighbor sets are constructed. Then compute intersections and apply τ. Without this step θ is ambiguous.

Q06.18. What is the difference between tau (τ) and theta.

Answer. In this presentation, θ is a threshold on original edge similarity or weight when forming neighbor sets; τ is the minimum shared-neighbor count or similarity used to retain SNN links. They are separate parameters, and not all SNN variants use both.

Q06.19. What is k in SNN algorithms (if Weighted)?

Answer. k is the number of top-ranked neighbors kept for each node in a k-nearest-neighbor SNN construction. k should be small relative to graph size when locality matters, and missing neighbors are handled naturally for low-degree nodes.

Q06.20. How do we know which tau(τ) or ”k” to choose?

Answer. Treat k and τ as hyperparameters. Compare plausible ranges against graph size, average degree, connectivity, known example groups, and stability under perturbation. Avoid choosing a threshold solely because it produces an attractive picture.

Q06.21. What are some evaluation metrics for tau or k?

Answer. Useful criteria include conductance, normalized cut, modularity, stability under resampling, connectedness, and—where trustworthy labels exist—ARI or NMI. Record trade-offs: overly strict τ can isolate nodes; overly permissive τ can merge groups.

Q06.22. what is Conductance?

Answer. For a nonempty proper vertex set S, conductance is φ(S)=cut(S,V\S)/min(vol(S),vol(V\S)), where the cut is the total crossing-edge weight and vol is the sum of incident weights (or degrees) on the set. Lower values indicate fewer external ties relative to internal volume.

Q06.23. Conductance whose property is this? The input graph, the output graph or the possible communities (from where you select the final communities)

Answer. Conductance is measured for a candidate community S relative to a specified reference graph, often the original input graph. The entire clustering may be summarized with a weighted average or worst-community conductance. Measuring only the pruned output can hide edges removed by the algorithm.

Q06.24. Is low value or high value of Conductance – that is used for the communities?

Answer. Lower conductance usually indicates a more strongly separated community, all else equal. However, minimizing it alone can select trivial or unbalanced groups; examine group sizes, coverage, and graph structure.

Q06.25. When comparing two k or tau values – which k or tau that you accept? Think in terms of Conductance.

Answer. Prefer the k/τ setting with better validated community quality: often lower conductance on the original graph, while respecting minimum community size, reasonable group count, coverage, and stability. Compare the same candidate pool and metric definition.

Q06.26. So, what was the purpose behind choosing these K or Tau values? What do we want to achieve ultimately? Is it to achieve Stronger communities by checking all possible communities and then measuring the community strength using Conductance? If it is – do all the questions on Weighted Graphs make sense? Why, Why not? How?

Answer. The purpose is to find meaningful, reasonably separated communities, not just a numerical minimum. Weighted settings make sense when weights represent real interaction strength or similarity. Define weight orientation and avoid evaluating on an artificially pruned graph alone.

Q06.27. Write a Pseudo-code for SNN on Undirected Weighted Graphs. Find the optimal value for K and tau.

Answer. Pseudocode: for each candidate k, build top-k weighted-similarity neighbor sets; for each candidate τ, form H with edges (u,v) when |N_k(u)∩N_k(v)|≥τ; obtain H’s connected components; reject trivial solutions; compute average conductance of components using original G; choose best valid (k,τ). If using an additional edge threshold θ, select eligible edges before ranking.

Q06.28. Implement SNN on Undirected Weighted Graphs. Print the optimal value for K and tau.

Answer. The full weighted Python grid-search example below prints the selected k and τ for the supplied toy graph; its result depends on the chosen parameters and penalty for trivial partitions. Replace sample weights with validated interaction strengths when applying to real data.

Q06.29. Why are we detecting communities and clusters anyway? What are the practical applications of such algorithms? Hint: Check notes on Introduction to Clustering/Community detection

Answer. Community detection supports anomaly and fraud analysis, collaboration science, epidemiology, network resilience, segmentation, recommendation, and biological module discovery. It can reveal structural groups, but membership should not be mistaken for individual intent, diagnosis, or culpability.

Implementation 1: Unweighted SNN

import networkx as nx
G = nx.Graph([(0,1),(0,2),(0,3),(1,2),
              (1,3),(2,3),(2,4),(3,4)])

def snn_unweighted(G, tau=2):
    H = nx.Graph(); H.add_nodes_from(G.nodes)
    for u, v in G.edges:
        s = len(set(G.neighbors(u)) & set(G.neighbors(v)))
        if s >= tau:
            H.add_edge(u, v, weight=s)
    return H

H = snn_unweighted(G, tau=2)
print(sorted(map(sorted, nx.connected_components(H))))
# [[0, 1, 2, 3], [4]]
print(sorted((min(u,v), max(u,v), d["weight"])
             for u,v,d in H.edges(data=True)))

Implementation 2: Weighted top-k SNN with parameter search

import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from([
 (0,1,0.90),(0,2,0.85),(1,2,0.93),
 (3,4,0.92),(3,5,0.88),(4,5,0.91),
 (2,3,0.10),(1,4,0.08)
])

def weighted_snn(G, k, tau):
    ranked = {
        u: set(v for v,d in sorted(G[u].items(),
               key=lambda x: -x[1]["weight"])[:k])
        for u in G.nodes
    }
    H = nx.Graph(); H.add_nodes_from(G)
    for u,v in G.edges:
        shared = len(ranked[u] & ranked[v])
        if shared >= tau:
            H.add_edge(u,v,weight=shared)
    return H

best = None
for k in (2,3,4):
    for tau in (1,2,3):
        H = weighted_snn(G, k, tau)
        groups = list(nx.connected_components(H))
        # Require a nontrivial split and no singleton groups.
        if len(groups) < 2 or any(len(c)<2 for c in groups):
            continue
        mean_phi = sum(nx.conductance(G, c, weight="weight")
                       for c in groups)/len(groups)
        key = (mean_phi, k, tau)
        if best is None or key < best[0]:
            best = (key, [sorted(c) for c in groups])
print("best (conductance, k, tau), communities:", best)
# If None, relax the validation constraints or expand the grid.

Teaching note. This search is small and illustrative, not a claim that conductance alone defines optimal community structure. The weighted edges are similarities (larger means stronger), and conductance is evaluated on the original graph G rather than the filtered SNN graph H.

Leave a Reply