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 high.

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

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^2/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/

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

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



Not that this site is doing any great work; 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 using Paypal.

Graph Mining: Louvian/Louvain Modularity: Learn by finding answers to the following questions. Can you answer the following questions?

I have seen both: Louvian Modularity and Louvain Modularity. I will use Louvain Modularity

What is the primary problem that Louvain Modularity solved?

Is Louvain good at detecting small communities?

What is modularity in Graphs?

What is the range of values used to show the modularity of a Graph?

What is the equation for Modularity? You can just only explain conceptually – what are the parameters/parts – how do the parameters work?

Give the algorithm for Louvain Modularity? You can just describe or you can show the steps.

Give the Pseudo-code for Louvain Modularity and implement in Python or R or C/C++?

Is Louvain Modularity easily parallelize-able or it is more sequential?

Investigate if any other algorithm is there that works like Louvain (i.e. can be an extension/modification of Louvain) that are better suited for Parallelization.

What is the first step in Louvain Algorithm?

True or False, at first step, all nodes are assigned to one community?

True or false, at first each node is assigned to it’s own community? i.e. no of vertices = no of communities

What are the two steps in Louvain Algorithm? What is the name of the steps?

What can be the terminating condition for the Louvain Algorithm?

How a node i is merged to a neighbor node/community to create a community? What is the measure used? Can you use the modularity equation as the measure to see how and to what node/community node i will merge to? Can it happen that node i will not be merged with anything though initially, you wanted to merge/assign i to another node/community?

When you will leave a node i alone without merging with a neighbor node/community? In that case, what will be the value of the modularity i.e. modularity change (i alone or i merged with a node/community)

when you try to merge node i with a neighbor node/community, do you try to assign node i to all possible neighbor node/community and calculate modularity change? If so, to which node/community i will get assigned to (describe in terms of modularity change)?

What is Modularity Optimization in Louvain modularity? Describe the steps/process for this Optimization.

What is the second step/phase for the Louvain Algorithm? What it is called? What happens here? what are the steps/process?

Is the Louvain Algorithm supervised?

Is the Louvain Algorithm fast or slow?

How many passes do the Louvain Algorithm require to create the communities?

What is the resolution limit for the Louvain Algorithm?

When the resolution limit is low, do you get more/smaller communities?

When the resolution limit is high, do you get less/larger output communities?

What is the numerical range used for the resolution limit?

Resources:
Louvain: Fast and Memory efficient. A Parallel Alternative
https://phys.org/news/2015-01-fast-problems.html

Modularity_(networks)
https://en.wikipedia.org/wiki/Modularity_(networks)

Louvain Modularity
https://en.wikipedia.org/wiki/Louvain_Modularity

Fast unfolding of communities in large networks
https://arxiv.org/pdf/0803.0476.pdf

Resolution Limit
https://en.wikipedia.org/wiki/Modularity_%28networks%29#Resolution_limit

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 any great work; 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 (Justetc Social Services) 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

Graph Mining: Hits. Learn by finding Answers to the Following Questions.

What is HITS algorithm in Graph Mining esp. for Web?

What does HITS stand for?

What is another similar Algorithm?

What are different between the PageRank algorithm and HITS?

What is the PageRank algorithm? What is the purpose?

Where and how PageRank is used?

Where and how HITS is used?

Describe HITS?

Describe the PageRank algorithm.

What are the two core concepts in HITS algorithm?

Web-pages that serves as large directories of other pages with useful information – what are they called in HITS algorithm?

Web-pages that serves to provide information on Specific topics – what are they called in the HITS algorithm?

What are HUBs in HITS algorithm? What purpose do they serve?

What are Authorities in HITS algorithm? What purpose do they serve?

Compare HITS and PageRank.

A web-page containing links to Top 1000 Universities in the world – is this a HUB or Authority in HITS?

What is the Govt. of Canada website that provides information on all Govt. Services? Is this a Hub or an Authority?

How do you measure a Good Hub?

How do you measure a Good Authority?

Can a web-page be both Hub and Authority? Can you assign both measures to a page irrespective of how good or bad?

What are the two scores that HITS assign to a web-page?

What is authority score for a web-page?

What is the hub score for a web-page?

What does hub score measure?

What does authority score measure?

What are the three matrices that are used for HITS algorithm? i.e. when you want to implement HITS algorithm.

What is a Transition Matrix in HITS?

What is a HUB vector? What does it contain initially?

What is an Authority vector? What does it contain initially?

For the graph below, provide the Initial Transition, Hub, Authority Vector/Matrices.

Directed Graph {Source, Destination}
Node: Yahoo, Amazon, Microsoft
Edges: {Yahoo, Yahoo} {Yahoo, Amazon} {Yahoo, Microsoft} {Amazon, Yahoo} {Amazon, Microsoft} {Microsoft, Amazon}

For the same graph above, explain your transition matrix?

If Transition Matrix is A, Hub Vector = h0, Authority Vector = a0.
How is Hub Score for a page is updated?, How is Authority Score for a page is updated? How long does this update happen?

The algorithm/steps as mentioned above: will the update converge to a state where Hub and Authority values will no longer change? Why, why not? if convergence does not happen what to do?

What is HITS normalization? i.e. after each iteration. Why it might be important.

Give steps/equations used for HITS normalization.

What are the two ways, you can make the HITS algorithm stop? i.e. stopping points.

True or False, Destiny of PageRank and HITS were different. What does it mean?

Can you stop the HITS algorithm after a certain number of iterations?

In real life, are HITS and PageRank used/applied for the whole graph i.e. whole Internet for example? Or majority of the times, they are applied on contextual graphs?

What are contextual graphs, anyway?

Give example use cases for HITS and PageRank?

Can you think of the value aspect of these algorithms? i.e. how they affect people, communities, societies?

What are the programming languages where you will find libraries that implement the HITS and PageRank algorithm? Give the name of the libraries.

Implement the algorithms from scratch in Python or in R without using the libraries. What did you use to debug your implementation and how?
What are the challenges that you faced to implement, how did you resolve? How did you represent the Graphs (i.e. on the graph you applied for testing).

Some Answers:
For the graph below, provide the Initial Transition, Hub, Authority Vector/Matrices.

Ans: Transition Matrix

A =[

1  1  1
1  0  1
0  1  0

]

Initial Hub Vector = h0
[
Yahoo
Amazon
Microsoft
]
=[
1
1
1]

Authority Vector: a0
[
Yahoo
Amazon
Microsoft
]

=
[
1
1
1
]

For the same graph above, explain your transition matrix?

First Row: Yahoo
2nd Row: Amazon
3rd Row: Microsoft

Columns: Yahoo —- Amazon — Microsoft

Transition Matrix

[Yahoo-> Yahoo, Yahoo-> Amazon, Yahoo-> Microsoft]
[Amazon->Yahoo, Amazon->Amazon, Amazon->Microsoft]
[Microsoft->yahoo, Microsoft->Amazon, Microsoft->microsoft]

using: 1 if page i links to page j, otherwise 0
[1,  1, 1 ]
[1,  0, 1]
[0,  1, 0]

If Transition Matrix is A, Hub Vector = h0, Authority Vector = a0.
How is Hub Score for a page is updated?, How is Authority Score for a page is updated?
A * a0 = h1 : Hub Score Update: based on authority score of outgoing links
transition(A) h1 = a1 : Authority Score Update : based on hub score of incoming links

Graph Mining: K-Spanning Trees: Learn by finding answers to the following questions. Can you answer the questions?

What is a Spanning Tree?

What is a Minimum Spanning Tree?

For the undirected Graph below, what is a Spanning Tree? First, draw the Graph, then Try to find the answer, and then check the answer below.
Edges with weights: {1, 2, 7} {1, 3, 2} {1, 4, 4} {2, 3, 3} {2, 4, 5} {3, 4, 2} {3, 5, 6} {4, 5, 4}

What is a minimum spanning tree?

What is the minimum spanning tree for the graph as provided above?

What is Prim’s Algorithm for Spanning Trees?

Describe the steps as used in Prim’s Algorithm?

Give the Algorithm i.e. Prim’s Algorithm?

Write pseudo-code for Prim’s Algorithm?

Implement Prim’s Algorithm in Python, R, Matlab, or in any other language of your choice?

What is the initialization step in Prim’s Algorithm?

Can you choose any node to start with Prim’s Algorithm?

True or False, Prim’s algorithm does not include all nodes in the output?

How an edge/path is selected in Prim’s Algorithm?

True or False, to proceed and when to select an edge, the edge does not need to belong to the already formed Minimum Spanning Tree (MST)?

True or False, to proceed and to select a new edge, the edge will need to have the highest weight outgoing from the MST or from the vertex under consideration)?

True or False, to proceed and to select a new edge, the edge will need to have the minimum weight outgoing from the MST (or from the vertex under consideration)?

True or False? The new edge selection steps are as follows.
Step 1. For the new edge, exactly one of its vertices/edge-points will need to be in the MST already
Step 2. The new edge has the minimum weight that satisfies step 1.

How long will you continue to add new edges to the MST? i.e. terminating condition for your algorithm.

Apply Prim’s algorithm to find the MST in Graph given above/below: See the answer after you give it a try
Edges with weights: {1, 2, 7} {1, 3, 2} {1, 4, 4} {2, 3, 3} {2, 4, 5} {3, 4, 2} {3, 5, 6} {4, 5, 4}

What is K-Spanning tree?

What are the steps in K-Spanning Tree?

Give the Algorithm for K-Spanning?

Write pseudo-code for K-Spanning?

Implement the K-Spanning tree algorithm in Python, R, Matlab, or in any other language of your choice?

What is K in the K-Spanning Tree algorithms?

How many edges do you remove to create k Clusters?

What is the first step in the K-Spanning tree?

When you remove edges from an MST – which edges do you remove? Edges represent distance. The ones with the highest weights or the lowest weights?

Some Answers:

What is a Spanning Tree?
Ans: A connected subgraph with all vertices and no cycles

For the undirected Graph below, what is a Spanning Tree?
Edges with weights: {1, 2, 7} {1, 3, 2} {3, 4, 2} {3, 5, 6}
Weight: 17

What is a minimum spanning tree?
Ans: Spanning trees with the minimum sum of edge weights where weights indicate distances.

What is the minimum spanning tree for the graph as provided above?
Ans: the same spanning tree with weight sum = 17
i.e. {1, 2, 7} {1, 3, 2} {3, 4, 2} {3, 5, 6}

What is Prim’s Algorithm for Spanning Trees?
Ans: Finds the minimum spanning tree

Apply Prim’s algorithm to find the MST in Graph given above/below: See the answer after you give it a try
Edges with weights: {1, 2, 7} {1, 3, 2} {1, 4, 4} {2, 3, 3} {2, 4, 5} {3, 4, 2} {3, 5, 6} {4, 5, 4}
Draw the graph that will make things easier

Ans: Select node 5
Select (5, 4, 4) from {3, 5, 6} {4, 5, 4}
Add (5, 4) to the MST
select edge {3, 4, 2} from {3, 5, 6} {2, 4, 5} {3, 4, 2} {1, 4, 4}
MST: {5, 4, 4} {3, 4, 2}
Similarly: select (3, 2, 3) {1, 3, 2}
Final Output: {5, 4, 4} {3, 4, 2} (3, 2, 3) {1, 3, 2}

What is the K-Spanning tree?
Ans: Community/Clustering Algorithm

When you remove edges from an MST – which edges do you remove? Edges represent distance. The ones with the highest weights or the lowest weights?
Ans: highest

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

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



Not that this site is doing any great work; 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 using Paypal.

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 clustering achieve? i.e. the output?

Give an Algorithm for Vertex Betweenness Clustering?

What is mu in the Algorithm for Vertex Betweenness Clustering?

Which vertex do you select at each step? i.e. the one with the highest betweenness or the lowest betweenness?

When you select a vertex at each step? Then what do you do (i.e. to create clusters)

Does the selected vertex go to all the clusters created around it?

What is the other name for Edge Betweenness?

Describe Edge Betweenness? maybe just giving an example

What does Edge Betweenness clustering achieve? i.e. the output?

Give an Algorithm for Edge Betweenness Clustering?

What is mu in the Algorithm for Edge Betweenness Clustering?

Which Edge do you select at each step? i.e. the one with the highest betweenness or the lowest betweenness?

When you select an Edge at each step? Then what do you do (i.e. to create clusters)

Does the selected Edge go to all the clusters created around it? or you just cut the graph at that edge and create clusters.

Answers:

Describe Vertex Betweenness? maybe just giving an example
Ans: The total number of shortest paths that pass through the vertex = the Vertex Betweenness for that Vertex. i.e. Among All vertices to all vertices shortest paths.

What is the other name for Edge Betweenness Clustering?
Ans: Girvan & Newman Clustering

What is Edge Betweenness? i.e. the concept
Ans: For a given edge, the number of shortest paths that pass through the edge. (All pairs/nodes to all pairs/nodes shortest paths)

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

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





Not that this site is doing any great work; 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 using Paypal.