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 a low number. Across clusters, connectivity will be high.

True or false: Highly connected clustering means: within clusters, connectivity will be high. Across clusters, connectivity will be a low number.

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.

What are some of the core concepts/terms that are related to Highly connected clustering?

What is a Cut when it comes to Highly connected clustering?

What is a Minimum Edge Cut when it comes to Highly connected clustering?

Describe Edge Connectivity for Highly connected clustering?

Contrast Cut and Minimum Edge Cut for Highly connected clustering?

Identify is this a Cut or a Minimum Edge Cut: The edges whose removal will disconnect the Graph?

Identify is this a Cut or a Minimum Edge Cut: The minimum edges whose removal will disconnect the Graph?

Edge removal and disconnecting the Graph: Does it mean we will have two clusters?

Assuming this is True: Highly connected clustering means: within a cluster, connectivity will be high. Across clusters, connectivity will be low.
— -True or false: The more edges are there in a group of vertices — the more connected they are?
— -True or false: The more edges are there in a group of vertices — the more similar are the vertices?
— -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?
— -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

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

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

Is it a highly connected subgraph? Undirected and Unweighted. why or why not?
Nodes: 0 to 8
Edges: {0–1} {0–2} {0–3} {1–2} {2–3} {2–4} {3–5} {4–5} {4–6} {4–7} {4–8}
{5–6} {5–7} {5–8} {6–7} {6–8} {7–8}

What is the minimum edge cut for the above graph?

What is V/2 for the above Graph?

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?

Why we use V/2 to check for a Highly connected subgraph?

What is the maximum diameter of every single highly connected graph? Can you please explain.

What is the number of edges in a highly connected subgraph?

True or false: For highly connected subgraphs, the number of edges will be at least V²/4?

True or false? explain: the number of edges in a highly connected subgraph is quadratic?

True or false: the number of edges in a highly connected subgraph is at most two?

Give and Describe the steps for creating/finding highly connected subgraphs.

Give the algorithm and pseudo-code Highly connected subgraphs?

What are the input and output for Highly connected subgraphs?

As we saw the definition of Min Edge Cut, can it be used in an algorithm for finding highly connected subgraphs?

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?

When will the Algorithm stop? i.e. Terminating Condition?

What are the algorithms to find the minimum edge cut for graphs?

Can you apply Karger’s algorithm for Minimum Cut to Weighted Graphs? if so, How? What was its intended purpose?

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

What is the core concept of Karger’s algorithm?

What is the “contraction of an edge” in Karger’s algorithm?

What is the number of edge reduction caused by “contraction of an edge”?

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

What is the complexity of Karger’s algorithm?

What is the complexity of Karger’s algorithm? is it O(E) or O(V) or O (Log(E))

Describe Karger’s algorithm?

Give the steps in Karger’s algorithm?

Describe Pseudo-code and Python/C++/R/Java code for Karger’s algorithm?

What is the input for Karger’s algorithm? What is the output?

What is the terminating condition for Karger’s algorithm?

Can you continue with Karger’s algorithm when there are <= 2 vertices left?

Give the minimum cut for the following Graph using Karger’s algorithm?
STEPS: 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.
Graph, Edges: {0, 1} {0, 2} {0, 3} {1, 3} {2, 3}
Also, show all the steps in picture or text

Will Karger’s algorithm? always create Min Cut?

What is the probability that Karger’s algorithm will create Min Cut?

For a 10 node graph, is the probability = 1/100?

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?

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)?

Some Answers:
What is the minimum edge cut for the above graph?
Ans: 2

What is V/2 for the above Graph? 4.5

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?
Ans: No, False, G is not a highly connected subgraph.

Resources

HCS clustering algorithm
https://en.wikipedia.org/wiki/HCS_clustering_algorithm

Karger’s algorithm for Minimum Cut | Set 1 (Introduction and Implementation)
https://www.geeksforgeeks.org/kargers-algorithm-for-minimum-cut-set-1-introduction-and-implementation/