Graph Mining: Shared Nearest Neighbors : Clustering : Community Detection<\/p>\n
Graph Mining: Shared Nearest Neighbors (SNN): Clustering : Community Detection: Learn by Finding Answers to the Following Questions.<\/p>\n
Will use SNN sometimes.<\/p>\n
What is one another name of the algorithm: Shared Nearest Neighbors?<\/p>\n
What is the purpose of the Algorithm: Shared Nearest Neighbors?<\/p>\n
Can you name other Algorithms that serve the same or similar purpose?<\/p>\n
What is the Criteria that SNN uses?<\/p>\n
Is SNN Hierarchical? What does Hierarchical mean in the context of Clustering\/Community detection?<\/p>\n
How does SNN work? i.e. what is the algorithm? i.e. how does SNN create clusters\/communities?<\/p>\n
Give and explain the steps in SNN with a small example.<\/p>\n
What is threshold \u03c4 in the SNN algorithm? Is it numeric? What can be the maximum and the minimum values?<\/p>\n
For the following Undirected and unweighted Graphs, show the steps and the final clusters.
\nEdges: {0, 1} {0, 2} {0, 3} {1, 2}, {1, 3} {2, 3} {2, 4} {3, 4}
\nYou can draw the graph first. You can use \u03c4 = 2.<\/p>\n
What is Node Similarity or Node Proximity between two nodes in SNN?<\/p>\n
What is the output of SNN? i.e. on an undirected and unweighted Graph?<\/p>\n
Will the output will have weights on the edges?<\/p>\n
Give the pseudocode for SNN algorithm<\/p>\n
Implement the SNN algorithm in Python or R or Matlab – whichever you prefer.<\/p>\n
Can you apply SNN on weighted Graphs?<\/p>\n
If you can apply SNN on weighted graphs, then how will you apply the Threshold, say theta?<\/p>\n
What is the first step in applying theta – if that is doable?<\/p>\n
What is the difference between tau (\u03c4) and theta.<\/p>\n
What is k in SNN algorithms (if Weighted)?<\/p>\n
How do we know which tau(\u03c4) or \u201dk\u201d to choose?<\/p>\n
What are some evaluation metrics for tau or k?<\/p>\n
what is Conductance?<\/p>\n
Conductance whose property is this? The input graph, the output graph or the possible communities (from where you select the final communities)<\/p>\n
Is low value or high value of Conductance – that is used for the communities?<\/p>\n
When comparing two k or tau values – which k or tau that you accept? Think in terms of Conductance.<\/p>\n
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?<\/p>\n
Write a Pseudo-code for SNN on Undirected Weighted Graphs. Find the optimal value for K and tau.<\/p>\n
Implement SNN on Undirected Weighted Graphs. Print the optimal value for K and tau.<\/p>\n
Why are we detecting communities and clusters anyway? What are the practical applications of such algorithms?
\nHint: Check notes on Introduction to Clustering\/Community detection<\/p>\n
Some Answers:<\/strong> Can you name other Algorithms that serve the same or similar purpose? What is the Criteria that SNN uses? Is SNN Hierarchical? What is Node Similarity or Node Proximity between two nodes in SNN? What is k in SNN algorithms (if Weighted)? Resources:<\/strong><\/p>\n Jarvis-Patrick Clustering Empirical Comparison of Algorithms for Network Community Detection By<\/strong><\/p>\n Sayed Ahmed<\/strong><\/p>\n Linkedin<\/strong>: https:\/\/ca.linkedin.com\/in\/sayedjustetc<\/a><\/p>\n Blog<\/strong>: http:\/\/Bangla.SaLearningSchool.com<\/a>, http:\/\/SitesTree.com<\/a> 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<\/strong>.<\/p>\n Affiliate Links:<\/strong> Hottest Deals on Amazon CA: http:\/\/tiny.cc\/bgnddz<\/a><\/p>\n
\nWhat is one another name of the algorithm: Shared Nearest Neighbors?
\nAns: Jarvis-Patrick algorithm<\/p>\n
\nAns: Maximal-Clique Enumeration, K- Spanning Tree, Shared Nearest Neighbor, Highly Connected Components, MinCut, Betweenness Based Algorithms, Louvain Modularity, CNM Algorithm<\/p>\n
\nAns: Two nodes are similar if they share a lot of neighbors<\/p>\n
\nAns: No<\/p>\n
\nAns: Count of the shared number of nodes\/neighbors<\/p>\n
\nretain its k neighbors<\/p>\n
\nhttps:\/\/btluke.com\/jpclust.html<\/a><\/p>\n
\nhttps:\/\/cs.stanford.edu\/~jure\/pubs\/communities-www10.pdf<\/a><\/p>\n
\nOnline and Offline Training<\/strong>: http:\/\/Training.SitesTree.com<\/a><\/p>\n
\nHottest Deals on Amazon USA: http:\/\/tiny.cc\/38lddz<\/a><\/p>\n