{"id":16324,"date":"2019-10-14T14:52:45","date_gmt":"2019-10-14T18:52:45","guid":{"rendered":"http:\/\/bangla.salearningschool.com\/recent-posts\/graph-mining-highly-connected-subgraph-clustering-learn-by-finding-answers-to-the-following-questions\/"},"modified":"2019-10-17T17:08:43","modified_gmt":"2019-10-17T21:08:43","slug":"graph-mining-highly-connected-subgraph-clustering-learn-by-finding-answers-to-the-following-questions","status":"publish","type":"post","link":"http:\/\/bangla.sitestree.com\/?p=16324","title":{"rendered":"Graph Mining: Highly Connected Subgraph Clustering: Learn by finding answers to the following questions."},"content":{"rendered":"

Graph Mining: Highly Connected Subgraph Clustering: Learn by finding answers to the following questions.<\/strong><\/p>\n

How do you define: Highly Connected?<\/p>\n

What is a Cluster?<\/p>\n

What is Subgraph?<\/p>\n

Does connectivity indicate the number of edges between clusters?<\/p>\n

True or false: Highly connected clustering means: within a cluster, connectivity will be low. Across clusters, connectivity will be high.<\/p>\n

True or false: Highly connected clustering means: within clusters, connectivity will be high. Across clusters, connectivity will be low.<\/p>\n

True or false: For Highly connected clustering, it is usually assumed that there is no prior assumptions on the number of clusters in the Graph.<\/p>\n

What are some of the core concepts\/terms that are related to Highly connected clustering?<\/p>\n

What is a Cut when it comes to Highly connected clustering?<\/p>\n

What is a Minimum Edge Cut when it comes to Highly connected clustering?<\/p>\n

Describe Edge Connectivity for Highly connected clustering?<\/p>\n

Contrast Cut and Minimum Edge Cut for Highly connected clustering?<\/p>\n

Identify is this a Cut or a Minimum Edge Cut: The edges whose removal will disconnect the Graph?<\/p>\n

Identify is this a Cut or a Minimum Edge Cut: The minimum edges whose removal will disconnect the Graph?<\/p>\n

Edge removal and disconnecting the Graph: Does it mean we will have two clusters?<\/p>\n

Assuming this is True: Highly connected clustering means: within a cluster, connectivity will be high. Across clusters, connectivity will be low.
\n—True or false: The more edges are there in a group of vertices – the more connected they are?
\n—True or false: The more edges are there in a group of vertices – the more similar are the vertices?
\n—True or false: The more edges are there in a group of vertices – it is highly likely that they will form a highly connected cluster?
\n—True or false: For a group of vertices, the more edges we need to remove to create a disconnected subgraph — the more similar are the vertices<\/p>\n

Is it a highly connected subgraph? For V vertices, the minimum edge cut contains less than V\/2 edges? Why? or Why not?<\/p>\n

Is it a highly connected subgraph? For V vertices, the minimum edge cut contains more than V\/2 edges? Why? or Why not?<\/p>\n

Is it a highly connected subgraph? Undirected and Unweighted. why or why not?
\nNodes: 0 to 8
\nEdges: {0-1} {0-2} {0-3} {1-2} {2-3} {2-4} {3-5} {4-5} {4-6} {4-7} {4-8}
\n{5-6} {5-7} {5-8} {6-7} {6-8} {7-8}<\/p>\n

What is the minimum edge cut for the above graph?<\/p>\n

What is V\/2 for the above Graph?<\/p>\n

If EC(G) is the min-cut and V = 9, is EC(G) > V\/2? If it is not, then can we call the subgraph to be highly connected?<\/p>\n

Why we use V\/2 to check for a Highly connected subgraph?<\/p>\n

What is the maximum diameter of every single highly connected graph? Can you please explain.<\/p>\n

What is the number of edges in a highly connected subgraph?<\/p>\n

True or false: For highly connected subgraphs, the number of edges will be at least V^2\/4?<\/p>\n

True or false? explain: the number of edges in a highly connected subgraph is quadratic?<\/p>\n

True or false: the number of edges in a highly connected subgraph is at most two?<\/p>\n

Give and Describe the steps for creating\/finding highly connected subgraphs.<\/p>\n

Give the algorithm and pseudo-code Highly connected subgraphs?<\/p>\n

What are the input and output for Highly connected subgraphs?<\/p>\n

As we saw the definition of Min Edge Cut, can it be used in an algorithm for finding highly connected subgraphs?<\/p>\n

As we saw that for highly connected subgraphs: EC(G) > V\/2 i.e. Min Edge Cut > V\/2. Can we just find min edge cuts for graphs\/subgraphs that satisfy EC(G) > V\/2 and divide the graph to get clusters? Also, we can do the same to the clusters to find smaller clusters if any. Can these be sufficient (core) to find highly connected subgraphs?<\/p>\n

When will the Algorithm stop? i.e. Terminating Condition?<\/p>\n

What are the algorithms to find the minimum edge cut for graphs?<\/p>\n

Can you apply Karger’s algorithm for Minimum Cut to Weighted Graphs? if so, How? What was its intended purpose?<\/p>\n

Can you apply Stoer-Wagner’s algorithm for Minimum Cut to Unweighted Graphs? if so, How? What was its intended purpose?<\/p>\n

What is the core concept of Karger’s algorithm?<\/p>\n

What is the \u201ccontraction of an edge\u201d in Karger’s algorithm?<\/p>\n

What is the number of edge reduction caused by \u201ccontraction of an edge\u201d?<\/p>\n

In Karger’s algorithm when you merge two nodes u and v, what happens to the edges that were previously connected to those nodes?<\/p>\n

What is the complexity of Karger’s algorithm?<\/p>\n

What is the complexity of Karger’s algorithm? is it O(E) or O(V) or O (Log(E))<\/p>\n

Describe Karger’s algorithm?<\/p>\n

Give the steps in Karger’s algorithm?<\/p>\n

Describe Pseudo-code and Python\/C++\/R\/Java code for Karger’s algorithm?<\/p>\n

What is the input for Karger’s algorithm? What is the output?<\/p>\n

What is the terminating condition for Karger’s algorithm?<\/p>\n

Can you continue with Karger’s algorithm when there are <= 2 vertices left?<\/p>\n

Give the minimum cut for the following Graph using Karger’s algorithm?
\nSTEPS: while there are more than 2 vertices, pick a random edge (u, v), contract u and v into one vertex, reattach the edges of u and v to this new vertex, remove self-loops. Keep doing.
\nGraph, Edges: {0, 1} {0, 2} {0, 3} {1, 3} {2, 3}
\nAlso, show all the steps in picture or text<\/p>\n

Will Karger’s algorithm? always create Min Cut?<\/p>\n

What is the probability that Karger’s algorithm will create Min Cut?<\/p>\n

For a 10 node graph, is the probability = 1\/100?<\/p>\n

If Karger’s algorithm is not supposed to generate the min-cut always, how can you increase the probability of creating i.e. implement in such a way so that you increase your chances to find the min-cut before applying for Highly Connected Subgraph Clustering algorithm?<\/p>\n

Can running the Karger’s algorithm multiple\/sufficient times and then taking the least cut found so far will produce better min-cut and better highly connected clusters (than just running once)?<\/p>\n

Some Answers:<\/strong>
\nWhat is the minimum edge cut for the above graph?
\nAns: 2<\/p>\n

What is V\/2 for the above Graph? 4.5<\/p>\n

If EC(G) is the min-cut and V = 9, is EC(G) > V\/2? If it is not, then can we call the subgraph to be highly connected?
\nAns: No, False, G is not a highly connected subgraph.
\nResources<\/strong><\/p>\n

HCS clustering algorithm
\nhttps:\/\/en.wikipedia.org\/wiki\/HCS_clustering_algorithm<\/a><\/p>\n

Karger\u2019s algorithm for Minimum Cut | Set 1 (Introduction and Implementation)
\nhttps:\/\/www.geeksforgeeks.org\/kargers-algorithm-for-minimum-cut-set-1-introduction-and-implementation\/<\/a><\/p>\n

By
\nSayed 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>
\nOnline and Offline Training<\/strong>: http:\/\/Training.SitesTree.com<\/a><\/p>\n

Affiliate Links:<\/strong>
\nHottest Deals on Amazon USA: http:\/\/tiny.cc\/38lddz<\/a><\/p>\n

Hottest Deals on Amazon CA: http:\/\/tiny.cc\/bgnddz<\/a><\/p>\n

Hottest Deals on Amazon Europe: http:\/\/tiny.cc\/w4nddz
\n<\/a>
\n
\n<\/a>
\nNot that this site is doing any great work;<\/strong> However, if you want to contribute to the operation of this site (or charitable\/non-profit work in the education sector), you can financially contribute to: safoundation at salearningschool.com<\/a> using Paypal.<\/p>\n","protected":false},"excerpt":{"rendered":"

Graph Mining: Highly Connected Subgraph Clustering: Learn by finding answers to the following questions. How do you define: Highly Connected? What is a Cluster? What is Subgraph? Does connectivity indicate the number of edges between clusters? True or false: Highly connected clustering means: within a cluster, connectivity will be low. Across clusters, connectivity will be … <\/p>\n

Continue reading<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1905,182],"tags":[],"class_list":["post-16324","post","type-post","status-publish","format-standard","hentry","category-graph-mining","category---blog","item-wrap"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[{"id":22873,"url":"http:\/\/bangla.sitestree.com\/?p=22873","url_meta":{"origin":16324,"position":0},"title":"Graph Mining: Learning Resources","author":"Sayed","date":"March 21, 2021","format":false,"excerpt":"Resources: Public URLs Graph Mining: Introducing Graphs: Learn by finding answers to the following questions?\u00a0http:\/\/bangla.salearningschool.com\/recent-posts\/graph-mining-introducing-graphs-learn-by-finding-answers-to-the-following-questions\/ Graph Mining: What is Graph Mining? Learn by finding answers to the following questions. Can you answer the following questions?\u00a0http:\/\/bangla.salearningschool.com\/recent-posts\/graph-mining-what-is-graph-mining-learn-by-finding-answers-to-the-following-questions-can-you-answer-the-following-questions\/ Graph Mining: Shared Nearest Neighbors : Clustering : Community Detection.\u00a0http:\/\/bangla.salearningschool.com\/recent-posts\/graph-mining-shared-nearest-neighbors-clustering-community-detection\/ Graph Mining: Betweenness Based Clustering:\u2026","rel":"","context":"In "Graph Mining"","block_context":{"text":"Graph Mining","link":"http:\/\/bangla.sitestree.com\/?cat=1905"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":22883,"url":"http:\/\/bangla.sitestree.com\/?p=22883","url_meta":{"origin":16324,"position":1},"title":"Graph Mining: Community and Cluster Detection","author":"Sayed","date":"March 21, 2021","format":false,"excerpt":"Resources to Learn From Resources:Defining and identifying communities in networkshttps:\/\/www.pnas.org\/content\/101\/9\/2658Community Structure:https:\/\/en.wikipedia.org\/wiki\/Community_structureGraph Clustering:https:\/\/www.csc2.ncsu.edu\/faculty\/nfsamato\/practical-graph-mining-with-R\/slides\/pdf\/Graph_Cluster_Analysis.pdf Read the resources above to find answers. Community Detection: Learn by finding answers to the following questions. Can you answer the following questions on Community Detection? Graph Mining: Community Detection: Learn by finding answers to the following questions.\u2026","rel":"","context":"In "Graph Mining"","block_context":{"text":"Graph Mining","link":"http:\/\/bangla.sitestree.com\/?cat=1905"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":16300,"url":"http:\/\/bangla.sitestree.com\/?p=16300","url_meta":{"origin":16324,"position":2},"title":"Graph Mining: Community Detection: Learn by finding answers to the following questions. Can you answer the following questions on Community Detection?","author":"Sayed","date":"October 7, 2019","format":false,"excerpt":"Graph Mining: Community Detection: Learn by finding answers to the following questions. Can you answer the following questions on Community Detection? What is a community anyway? Describe from your real-world\/social understanding of it? Can you relate it to the Graphs concept in Computer Science? In your daily life do you\u2026","rel":"","context":"In "AI ML DS RL DL NN NLP Data Mining Optimization"","block_context":{"text":"AI ML DS RL DL NN NLP Data Mining Optimization","link":"http:\/\/bangla.sitestree.com\/?cat=1910"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":16305,"url":"http:\/\/bangla.sitestree.com\/?p=16305","url_meta":{"origin":16324,"position":3},"title":"Graph Mining: Betweenness Based Clustering: Learn by finding answers to the following questions. Can you answer the following?","author":"Sayed","date":"October 8, 2019","format":false,"excerpt":"Graph Mining: Betweenness Based Clustering: Learn by finding answers to the following questions. Can you answer the following? What are the types of Betweenness? What is Vertex Betweenness? i.e. the concept What is Edge Betweenness? i.e. the concept Describe Vertex Betweenness? maybe just giving an example What does Vertex Betweenness\u2026","rel":"","context":"In "Graph Mining"","block_context":{"text":"Graph Mining","link":"http:\/\/bangla.sitestree.com\/?cat=1905"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":22881,"url":"http:\/\/bangla.sitestree.com\/?p=22881","url_meta":{"origin":16324,"position":4},"title":"Graph Mining: Node Importance","author":"Sayed","date":"March 21, 2021","format":false,"excerpt":"Resources to Learn From A Book. Nagiza F. Samatova, William Hendrix, John Jenkins, Kanchana Padmanabhan, and Arpan Chakraborty. 2013. Practical Graph Mining with R. Chapman & Hall\/CRC. Read the resources above to find answers. Betweenness Based Clustering: Learn by finding answers to the following questions. Can you answer the following?\u2026","rel":"","context":"In "Graph Mining"","block_context":{"text":"Graph Mining","link":"http:\/\/bangla.sitestree.com\/?cat=1905"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":16302,"url":"http:\/\/bangla.sitestree.com\/?p=16302","url_meta":{"origin":16324,"position":5},"title":"Graph Mining: Shared Nearest Neighbors : Clustering : Community Detection","author":"Sayed","date":"October 7, 2019","format":false,"excerpt":"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:\u2026","rel":"","context":"In "Graph Mining"","block_context":{"text":"Graph Mining","link":"http:\/\/bangla.sitestree.com\/?cat=1905"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/posts\/16324","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=16324"}],"version-history":[{"count":1,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/posts\/16324\/revisions"}],"predecessor-version":[{"id":16328,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/posts\/16324\/revisions\/16328"}],"wp:attachment":[{"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=16324"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=16324"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=16324"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}