Job Prospect for Graph Mining

Industry Job Prospect for Graph Mining

Sample Jobs

https://www.careerbuilder.com/jobs-graph-mining

https://www.indeed.com/q-Graph-Mining-jobs.html

For example, Google works in the following areas of Graph Mining. Google has jobs for such. Also, Facebook and any other social networking site will have jobs in relation to Graph Mining. Computational Biology, Medicine Research, Drug Discovery, Disease Diagnosis, Transportation, Scheduling, Shipping Scheduling will have applications and jobs for Graph Mining. 

Job Areas:

The general Mining (data based) jobs and Machine/Deep/Reinforcement Learning jobs will require Graph Mining expertise sometimes such as positions (real) : Research Intern - Deep Learning for Graphs, ML Engineer - Siri Knowledge Graph

Computer Networks, Network/Cyber Security application development (also R & D) positions might ask for Graph Mining expertise.

Graph Mining will have applications and jobs in Biological, Chemistry, Drug Design areas also in Transportation

Social Network Mining will always involve Graph Mining. Applications: Friend Recommendation

Trajectory Data Mining Jobs at Microsoft

https://www.microsoft.com/en-us/research/publication/trajectory-data-mining-an-overview/
Graph Mining Jobs (areas) at Google:
https://ai.google/research/teams/algorithms-optimization/graph-mining/

"Large-Scale Balanced Partitioning: Example Google Maps Driving Directions, Large-Scale Clustering:clustering graphs at Google scale, Large-Scale Connected Components, Large-Scale Link Modeling: similarity ranking and centrality metrics:  link prediction and anomalous link discovery., Large-Scale Similarity Ranking: Personalized PageRank, Egonet similarity, Adamic Adar, and others, Public-private Graph Computation, Streaming and Dynamic Graph Algorithms, ASYMP: Async Message Passing Graph Mining, Large-Scale Centrality Ranking, Large-Scale Graph Building"

More Related Jobs:

Tools in Jobs/Jobs--https://www.researchgate.net/post/Can_you_suggest_a_graph_mining_tool

--https://www.linkedin.com/jobs/gephi-jobs/

--https://bit.ly/2Nwlnrp Data Scientist 2

-- https://bit.ly/2r04wFP Graph Jobs

-- https://indeedhi.re/2oHkOmo
Last modified: Sunday, 19 January 2020, 10:06 PM

Shop Online: https://www.ShopForSoul.com/

8112223 Canada Inc./JustEtc: http://JustEtc.net

Linkedin: https://ca.linkedin.com/in/sayedjustetc

Courses: http://Training.SitesTree.com (Big Data, Cloud, Security, Machine Learning)

Blog: http://Bangla.SaLearningSchool.com, http://SitesTree.com

Medium: https://medium.com/@SayedAhmedCanada

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.

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