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.

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

Graph Mining – 002: SMALL WORLD GRAPHS & RANDOM GRAPH GENERATORS

Graph Mining: SMALL WORLD GRAPHS & RANDOM GRAPH GENERATORS: Learn by finding answers to the following questions.

Can you answer the following?

What is a Graph?

Can you define graph formally?

What are the components in a Graph?

What are edges and nodes or vertices in a Graph?

Can you provide examples of Graphs? in Areas such as Science, Engineering, Medical, Biology, Social Sciences, Internet Applications, Social Media?

Can you draw a simple graph?

What is a Random Graph?

What do you use to answer questions about the properties of typical graphs?

What is the purpose of a Random Graph?

What types of graphs you use to answer questions about the properties of typical graphs?

How can you generate a Random Graph?

What is known as Small World Properties for Graphs?

Give some examples of Real Graphs

What is the connection between Real Graphs and Small World Properties?

What are some properties of Small World Networks?

Can you give examples of Non Small World Networks?

For small World Graphs – what will be the average path lengths (count of vertices) – a large number of a small number?

Are small world graphs sparse or dense?

What is power law distribution? How does that related to Small World Graphs?

How can you relate Power Law Distribution to Github network?

What is power law in statistics?

Can you name some Random Graph Generators? What is the purpose? What will they do actually in general? Why will you use these generators.

When edges are created between vertices with probability p : what is this mode of generation called? Is it a Random Graph? Why?

What happens when p = probability is closer to 0? what when p is closer to 1?

What is weight in a random graph Generator for example in the above case?

When a Graph is generated using the probability approach – what is the order of the maximum size graph?

Can you represent the graph generated above as G(n, p)? n = number of vertices, p = probability

For the above case, what happens when np < 1 ?

For the above case, what happens when np = 1 ? Can np be > 1?

When a Graph G(n, p) is generated using the probability approach as mentioned above – and when np < 1, what is the order of the size of a connected component? is it O(n), or o(n), O(log(n)), O(Olog(n)). Check answer section

What is Erdos Renyi? Is it the name of a Random Graph Generator or the name of a small world property or a statistical law?

For Erdos Renyi, is the average path length short?

For Erdos Renyi, do they exhibit local clustering?

Is local clustering a property of small world graphs?

For Erdos Renyi, does it show Skewed degree distribution i.e. skewed power law distribution?

For Erdos Renyi, does it show poission distribution?

What is poission distribution? anyway?

Can you relate poission distribution to Banks or a Diagnostic Center?

What is Watts–Strogatz model for Random Graph Generation? How does it work?

Does Watts–Strogatz model create a directed graph or an undirected graph?

For Watts–Strogatz model, if the desired Node count is N, then what will be the output edge count? You can introduce and define a new parameter if required.

For Watts–Strogatz, is the average path length short?

For Watts–Strogatz, do they exhibit local clustering?

Is local clustering a propery of small world graphs?

For Watts–Strogatz, does it show Skewed degree distribution i.e. skeweed power law distribution?

For Watts–Strogatz, does it show poission distribution?

how does Watts–Strogatz relate to Dirac Delta Function?

what is Barabási–Albert (BA) model? Is it the name of a Random Graph Generator or the name of a small world property or a statistical law?

How does Barabási–Albert (BA) model work? i.e. the steps i.e. the methods

For Barabási–Albert (BA) model, how is a new node added?

For Barabási–Albert (BA) model, does it start with an empty graph or with an already connected graph?

For Barabási–Albert (BA) model, how a new node is connected to an existing node? What does it depend upon? How does a probability play a role?

For Barabási–Albert (BA) model, which nodes will accumulate more links quickly?

For Barabási–Albert (BA) model, which nodes will starve for new links?

For Barabási–Albert (BA) model, is the average path length short?

For Barabási–Albert (BA) model, do they exhibit local clustering?

For Barabási–Albert (BA) model, does it show Skewed degree distribution i.e. skeweed power law distribution?

Answers:

How can you generate a Random Graph?
Start with n isolated vertices, Add successive edges between them at random

Give some examples of Real Graphs
Food webs, Electric power grids, Metabolite processing networks, Networks of brain neurons, Voter networks, Social influence networks, Co-occurrence networks, Networks of connected proteins

What are some properties of Small World Networks?
"Properties of small-world networks
Small-world networks tend to contain cliques, and near-cliques, meaning sub-networks which have connections between almost any two nodes within them. This follows from the defining property of a high clustering coefficient. Secondly, most pairs of nodes will be connected by at least one short path. This follows from the defining property that the mean-shortest path length be small. Several other properties are often associated with small-world networks. Typically there is an over-abundance of hubs – nodes in the network with a high number of connections (known as high degree nodes). These hubs serve as the common connections mediating the short path lengths between other edges. By analogy, the small-world network of airline flights has a small mean-path length"
Reference: https://en.wikipedia.org/wiki/Small-world_network#Examples_of_small-world_networks

Can you give examples of Non Small World Networks?
Ans: Check: Reference: https://en.wikipedia.org/wiki/Small-world_network#Examples_of_small-world_networks

What is power law in statistics?
"In statistics, a power law is a functional relationship between two quantities, where a relative change in one quantity results in a proportional relative change in the other quantity, independent of the initial size of those quantities: "
https://en.wikipedia.org/wiki/Power_law#Power-law_probability_distributions

Can you name some Random Graph Generators?
Erdős–Rényi model, Watts–Strogatz model, Barabási–Albert (BA) model

When a Graph is generated using the probability approach – what is the order of the maximum size graph? Check answer
n to the power 2/3

For Watts–Strogatz model, if the desired Node count is N, then what will be the output edge count? Ans: NK/2

Watts–Strogatz model
K = mean degree = an even number
B = a special parameter
N >> K >> ln(K) >> 1

Check degree distribution for Watts–Strogatz model at: https://en.wikipedia.org/wiki/Watts%E2%80%93Strogatz_model
"The degree distribution in the case of the ring lattice is just a Dirac delta function centered at {\displaystyle K}K. The degree distribution for {\displaystyle 0<\beta <1}0<\beta <1 can be written as:

Resources:
Graph mining – lesson 1: Introduction to graphs and networks
http://www.nathalievialaneix.eu/teaching/m2se/M2SE-network_1.pdf

Erdős–Rényi model
https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model

Random Graphs
https://en.wikipedia.org/wiki/Random_graph

Examples of small-world networks
https://en.wikipedia.org/wiki/Small-world_network#Examples_of_small-world_networks

Case Study: Small World Phenomenon
https://introcs.cs.princeton.edu/java/45graph/

Random Graphs: Model of Social Networks
http://www.pnas.org/content/99/suppl_1/2566

Power Law Distribution
https://en.wikipedia.org/wiki/Power_law#Power-law_probability_distributions

Poisson distribution
https://en.wikipedia.org/wiki/Poisson_distribution

Watts–Strogatz model
https://en.wikipedia.org/wiki/Watts%E2%80%93Strogatz_model

Dirac delta function
Everywhere it is zero except at zero
https://en.wikipedia.org/wiki/Dirac_delta_function

Barabási–Albert (BA):
https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model#Degree_distribution

Random Graph Generators in Python Libraries
https://networkx.github.io/documentation/networkx-1.10/reference/generators.html

Random Graph Generators in R Libraries
https://rpubs.com/lgadar/generate-graphs

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

Graph Mining: Link Prediction. Learn by finding answers to the following questions.

What is Link Prediction in Graph Mining?

How can Link Prediction help? and where? can it help in social network, research co-authorship, or spread of disease

Give uses of Link Prediction in epidemiology or any medical/biology application?

Give uses of Link Prediction in Social Network?

Give uses of Link Prediction in co-authorship?

What are the steps in Link Prediction? i.e. define link prediction problem.

Define Link Prediction Problem formally i.e. with Notations i.e. with Graph notations i.e. Graph Representations.

How is node similarity related in Link Prediction?

What are possible Node Similarity algorithms that can be used for the purpose?

Which nodes are the most possible new links? think in terms of Node Similarity Index (Highest, Lowest)

What are the types of Node Similarity? Node proximity?

What is Node Similarity based upon? i.e. Network Topology

What is Local Structure for Node Similarity?

What is Global Structure for Node Similarity?

What are examples of Local Structure for Node Similarity?

What are examples of Global Structure for Node Similarity?

Define Node Neighborhoods. Is it local or global structure?

What is Preferential Attachment Index? Is it LocaL or global structure

What are the types of Node Neighborhoods?

If two nodes do not have any common node — what is the probable similarity (Node Neigh. aspect)?

What is Common Neighbors ? Is it local or global structure? is it Node Neighbor or Preferential Attachment? and why?

What is Jaccard Coefficient ? Is it local or global structure? is it Node Neighbor or Preferential Attachment? and why?

What is Adamic-Adar? Is it local or global structure? is it Node Neighbor or Preferential Attachment? and why?

What is the name of the Node Similarity approach where Sum of the inverse logarithmic degree centrality of the neighbors shared by the two nodes are counted?

What is the name of the Node Similarity approach where the ratio of seize of set intersection to the set union is counted?

What is the name of the Node Similarity approach where the count of common nodes are used?

If node similarity score is counted as multiplication of the number/count of outgoing edges for a node pair. And then the higher results are assumed to create new links. What is this approach called?

When similarity scores are calculated based on global link structure of graph – what is this called local structure or global structure?

What is an example of Global Structure?

What are the examples of Global Structure?

What is Kartz Index for Global Structure?

What is Simrank for Global Structure?

When Node Similarity is calculated as: Sum of count of all paths between node pairs – what is this approach called? Then how is the link prediction made?

When Node Similarity is calculated as: two nodes are similar if they are referred by similar nodes. What is the name?

How can you measure if your implemented link prediction algorithm is great or not?

Can you use train and test concept for the measurement? Can you define the steps/problems formally? with Graph Notations?

What are some measures to calculate in the train/test approach?

Answers:
What is the name of the Node Similarity approach where Sum of the inverse logarithmic degree centrality of the neighbors shared by the two nodes are counted?
Ans: Adamic-Adar

What is the name of the Node Similarity approach where the ratio of seize of set intersection to the set union is counted?
Ans: Jaccard Coefficient

What is the name of the Node Similarity approach where the count of common nodes are used?
Ans: Common Neighbors

If node similarity score is counted as multiplication of the number/count of outgoing edges for a node pair. And then the higher results are assumed to create new links. What is this approach called?
Ans: Preferential Attachment Index

What is an example of Global Structure?
Ans: Path Length > 2

What are the examples of Global Structure?
Shortest Paths – use inverse of distance as similarity, Kartz Index, SimRank

What are some measures to calculate in the train/test approach?
Accuracy, F1-score, Sensitivity, Most metrics that would work for classification

Resources
Link Prediction
https://paperswithcode.com/task/link-prediction

Similarity Index based Link. Prediction Algorithms in Social Networks: A Survey
https://pdfs.semanticscholar.org/8e72/fa77f3d788f3c67da1e1c6347c3aaf280723.pdf

Proximity-based Methods for Link Prediction
https://cran.r-project.org/web/packages/linkprediction/vignettes/proxfun.html

Evaluating Link Prediction Methods
https://arxiv.org/pdf/1505.04094.pdf

Link Prediction Algorithm
http://be.amazd.com/link-prediction/

Evaluating link prediction methods
https://www3.nd.edu/~dial/publications/yang2015evaluating.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

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