Graph Mining: Shared Nearest Neighbors : Clustering : Community Detection

Graph Mining: Shared Nearest Neighbors (SNN): Clustering : Community Detection: Learn by Finding Answers to the Following Questions.

Will use SNN sometimes.

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

What is the purpose of the Algorithm: Shared Nearest Neighbors?

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

What is the Criteria that SNN uses?

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

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

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

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

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.

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

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

Will the output will have weights on the edges?

Give the pseudocode for SNN algorithm

Implement the SNN algorithm in Python or R or Matlab - whichever you prefer.

Can you apply SNN on weighted Graphs?

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

What is the first step in applying theta - if that is doable?

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

What is k in SNN algorithms (if Weighted)?

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

What are some evaluation metrics for tau or k?

what is Conductance?

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

Is low value or high value of Conductance - that is used for the communities?

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

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?

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

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

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

Some Answers:
What is one another name of the algorithm: Shared Nearest Neighbors?
Ans: Jarvis-Patrick algorithm

Can you name other Algorithms that serve the same or similar purpose?
Ans: Maximal-Clique Enumeration, K- Spanning Tree, Shared Nearest Neighbor, Highly Connected Components, MinCut, Betweenness Based Algorithms, Louvain Modularity, CNM Algorithm

What is the Criteria that SNN uses?
Ans: Two nodes are similar if they share a lot of neighbors

Is SNN Hierarchical?
Ans: No

What is Node Similarity or Node Proximity between two nodes in SNN?
Ans: Count of the shared number of nodes/neighbors

What is k in SNN algorithms (if Weighted)?
retain its k neighbors

Resources:

Jarvis-Patrick Clustering
https://btluke.com/jpclust.html

Empirical Comparison of Algorithms for Network Community Detection
https://cs.stanford.edu/~jure/pubs/communities-www10.pdf

By

Sayed Ahmed

Linkedin: https://ca.linkedin.com/in/sayedjustetc

Blog: http://Bangla.SaLearningSchool.com, http://SitesTree.com
Online and Offline Training: http://Training.SitesTree.com

Not that this site is doing anything great work; However, if you want to contribute to the operation of this site (or charitable/non-profit work in education sector), you can donate to: safoundation using Paypal.

Affiliate Links:
Hottest Deals on Amazon USA: http://tiny.cc/38lddz

Hottest Deals on Amazon CA: http://tiny.cc/bgnddz

Hottest Deals on Amazon Europe: http://tiny.cc/w4nddz