Graph Mining – 1: Course archive and question bank. This is an AI-formatted reproduction of the previously compiled Word document from this blog. The original graph-mining questions and source posts are attributed to Sayed Ahmed. Follow the source-post links for original context. New AI-generated answers appear in separate numbered course lessons.
Free reuse: The new AI-written instructional text in this course is made available for reuse without copyright restrictions asserted by this blog; linked third-party images, papers, and quotations retain their own rights and terms.
Graph Mining Blog Archive and Question Bank
Open Education | November 2026
The Open Education archive contains 33 posts focused on graph mining. Nineteen contain topic questions or exercises. Six repeat sets available on other posts, leaving 13 distinct sets with 415 numbered prompts.
The post index links to all source articles, including reposts. The question bank keeps the source order and retains example graphs and task instructions. Published answer notes are collected separately so you can try the exercises first.
Post index · Question bank · Published answer notes · Original Graph Mining category
Question Set Map
Post Index
The index covers the 24 published posts in the Graph Mining category and nine graph-mining posts found elsewhere on the blog. Related graph theory, visualization, and graph machine-learning material appears separately.
Posts with Questions or Exercises
Graph Mining: What is Graph Mining? Learn by finding answers to the following questions. Can you answer the following questions? [16311]
Oct 9, 2019. Definitions, disciplines, applications, and modeling real systems as graphs. Question set 01
Graph Mining: Introducing Graphs: Learn by finding answers to the following questions? [16312]
Oct 10, 2019. Graph types, isomorphism, matrix and list representations, and temporal tensors. Question set 02
Graph Mining: Introducing Graphs: Learn by finding answers to the following questions? #Root [26231]
Apr 20, 2021. Also published with the same question set on post 16312. Question set 02
Graph Mining: SMALL WORLD GRAPHS & RANDOM GRAPH GENERATORS: Learn by finding answers to the following questions. [16299]
Oct 7, 2019. Small-world properties and the Erdős–Rényi, Watts–Strogatz, and Barabási–Albert models. Question set 03
Graph Mining: Hits. Learn by finding Answers to the Following Questions. Can you answer the following questions? [16322]
Oct 12, 2019. Hub and authority scores, matrix updates, normalization, use cases, and implementation. Question set 04
Graph Mining: HITS Pagerank HUBS Anchors and Graph Theories [22879]
Mar 21, 2021. Also published with the same question set on post 16322. Question set 04
Graph Mining: Community Detection: Learn by finding answers to the following questions. Can you answer the following questions on Community Detection? [16300]
Oct 7, 2019. Communities, subgraphs, clustering, applications, algorithms, and evaluation. Question set 05
Graph Mining: Community and Cluster Detection [22883]
Mar 21, 2021. Also published with the same question set on post 16300. Question set 05
Graph Mining: Shared Nearest Neighbors : Clustering : Community Detection [16302]
Oct 7, 2019. Neighbor overlap, thresholds, weighted graphs, conductance, and implementation. Question set 06
Graph Mining: Shared Nearest Neighbors – Community Detection [22885]
Mar 21, 2021. Also published with the same question set on post 16302. Question set 06
Graph Mining: Betweenness Based Clustering: Learn by finding answers to the following questions. Can you answer the following? [16305]
Oct 8, 2019. Vertex and edge betweenness and cluster splits. Question set 07
Graph Mining: Node Importance [22881]
Mar 21, 2021. Also published with the same question set on post 16305. Question set 07
Graph Mining: K-Spanning Trees: Learn by finding answers to the following questions. Can you answer the questions? [16306]
Oct 8, 2019. Spanning trees, Prim’s method, and cutting heavy tree edges to make clusters. Question set 08
Graph Mining: Highly Connected Subgraph Clustering: Learn by finding answers to the following questions. [16324]
Oct 14, 2019. Edge connectivity, highly connected components, and Karger’s random contraction. Question set 09
Graph Mining: Louvian Modularity: Learn by finding answers to the following questions. Can you answer the following questions? [16323]
Oct 13, 2019. Modularity, Louvain phases, parallelization, termination, and resolution. Question set 10
Graph Mining: Louvian Modularity: Learn by finding answers to the following questions. Can you answer the following questions? #Root [26233]
Apr 20, 2021. Also published with the same question set on post 16323. Question set 10
Graph Mining: Link Prediction. Learn by finding answers to the following questions. [16297]
Oct 6, 2019. Local and global similarity, link scoring, use cases, and evaluation. Question set 11
Graph Mining: Time Evolving Graphs [22887]
Mar 21, 2021. Temporal edges and relationships, interval relations, and Neo4j modeling. Question set 12
Graph Mining: Misc. Topics to Learn: Misc. Resources to Learn From [22891]
Mar 21, 2021. Graph algorithm implementations, library comparison, graph properties, and project ideas. Question set 13
Other Graph Mining Posts
Spearman Correlation Coefficient and Graph Mining [76091]
May 19, 2024. Stock-forecasting code that builds graphs from correlations and news and applies a graph neural-network model.
Join a Graph Mining Course #Root [26235]
Apr 20, 2021. Repost of the course invitation and proposed format.
Graph Mining: Graph Mining Use Cases [22889]
Mar 21, 2021. Reading links on graph use cases and graph-based anomaly detection.
Graph Mining: Resources to Learn From [22877]
Mar 21, 2021. Pointers to introductory graph and network material, bipartite graphs, and trees.
Potential Learning Outcome from a Graph Mining Course [22875]
Mar 21, 2021. Learning outcomes for graph analysis, Python or R, graph tools, ethics, and teamwork.
Graph Mining: Learning Resources [22873]
Mar 21, 2021. Index of older blog exercises. Its question-shaped link titles are not new prompts.
Graph Mining: Possible Course Topics [22871]
Mar 21, 2021. Suggested syllabus from graph fundamentals and node scores to temporal graphs, anomaly detection, graph databases, and processing.
Graph Mining: Job Prospect [22869]
Mar 21, 2021. Historical career examples in large-scale graph mining and related research.
Course Introduction [22867]
Mar 21, 2021. Introduces the intended advanced undergraduate or graduate audience and course format.
Industry Job Prospect for Graph Mining [16680]
Jan 24, 2020. Historical career post on graph-mining domains and job areas.
Industry Job Prospect for Graph Mining [16673]
Jan 21, 2020. Historical career post with sample roles and graph-mining functions.
20 January, 2020 08:01 [16672]
Jan 20, 2020. Timestamp-titled post on prerequisites including algorithms, networks, and optional ML or big-data background.
Industry Job Prospect for Graph Mining [16345]
Nov 2, 2019. Earlier career post with graph-mining job areas and examples.
Join a Graph Mining Course [16333]
Oct 23, 2019. Course invitation and outline of conceptual topics, resources, and discussion.
Related Graph and Graph Learning Posts
CS101 – Discrete Mathematics – Graph Theory (গ্রাফ থিওরী) [13803]
Nov 1, 2017. Bengali and English labels for a discrete-mathematics graph theory video.
NETWORK VISUALIZATION : Data Visualization [16089]
Sep 6, 2019. References on visualizing networks, graph types, and adjacency representations.
NETWORK VISUALIZATION : Data Visualization #Root [26174]
Apr 18, 2021. Repost of the network-visualization resource list.
Discuss: Dynamic Multiscale Graph Neural Networks for 3D Skeleton Based Human Motion Prediction [74417]
Apr 27, 2022. Video discussion of a graph neural-network model for 3D skeleton motion prediction.
Library Import in Python for ML/Graph ML [76086]
May 19, 2024. Python imports for StellarGraph, GNN layers, preprocessing, and ML tools.
Python/ML Correlation Coefficients [76087]
May 19, 2024. Constructs and draws a NetworkX graph from a thresholded Pearson correlation matrix.
1. Libraries used for the project: Predict Future Stock Price using Graph Theory, Machine Learning and Deep Learning) [76436]
Dec 4, 2024. Imports for a stock prediction project using graph and machine-learning libraries.
Question Bank — All Original Prompts
Each section points to the original source and any matching repost. A numbered prompt may contain more than one question. The same topic can recur in different sets where the original posts asked about it in a different context.
01 Graph Mining Foundations
Source posts Open post 16311 · Topic map
01.01 What is Graph Mining?
01.02 What is a Graph anyway?
01.03 Is Graph mining just a kind of Machine Learning? i.e. is Machine Learning the only primary component of Graph Mining?
01.04 Does Graph Mining involve Only Statistics? Or Statistics can help?
01.05 Does Graph Mining involve Only Graph Theory? Or Graph Theory can help?
01.06 Is Graph Theory primarily relates to Computer Science or Math/Statistics or Machine Learning?
01.07 Does Graph Mining involve Only Machine Learning? Or Machine Learning is just one component?
01.08 To be great at Graph Mining – what are the areas that you need to master?
01.09 What are the applications of Graph Mining?
01.10 How the hackers can use/utilize Graph Mining?
01.11 What is the Origin of Graph Theory?
01.12 What is the first paper in Graph Theory? What does it try to solve?
01.13 What (where) are the applications of the Graph Algorithm named: Seven Bridges of König
01.14 Why is Graph and Graph Mining Important? Why do we care?
01.15 What are some application areas of Graph Mining?
01.16 How can you model Social Network to be a Graph?
01.17 Give an example of Graphs in Biology?
01.18 What is a Semantic Graph? Give examples.
01.19 Give an example of Graphs from Non-Graph Data.
01.20 Network vs. Graph?
02 Graph Types and Representations
Source posts Open post 16312 · Open post 26231 · Topic map
02.01 What is a Graph?
02.02 Give an example of a Graph?
02.03 What are the different Types of Graphs? i.e. Try to give some examples of different ways how Graphs are classified?
02.04 What is a directed Graph?
02.05 What is an undirected Graph?
02.06 What are Labeled Graphs?
02.07 What are Weighted Graphs?
02.08 What are the unweighted Graphs?
02.09 What are the Bipartite Graphs?
02.10 What is a Tree?
02.11 What is a Signed Graph?
02.12 What is a Looped Graph? i.e. What is a loop?
02.13 Compare Static and Time-evolving Graphs.
02.14 What is an Isomorphic Graph?
02.15 What does Isomorphism mean when it comes to Graphs?
02.16 What are different ways to represent Graphs? i.e. when implementing Graph Algorithms?
02.17 How to store a Graph data in programming languages?
02.18 Describe the Adjacency Matrix approach of Graph Representation.
02.19 Give a small example graph then represent it using the Adjacency Matrix approach of Graph Representation.
02.20 Represent the following Graph using Adjacency Matrix approach of Graph Representation
Edges: {0, 1} {0, 4} {1, 2} {1, 3} {1, 4} {2, 3} {3, 4}
02.21 What are the advantages/pros of the Adjacency Matrix Representation?
02.22 What are the disadvantages/cons of the Adjacency Matrix Representation?
02.23 Describe the Adjacency List approach of Graph Representation.
02.24 Give a small example graph then represent it using the Adjacency List approach of Graph Representation.
02.25 Represent the following Graph using Adjacency List approach of Graph Representation
Edges: {0, 1} {0, 4} {1, 2} {1, 3} {1, 4} {2, 3} {3, 4}
02.26 What are the advantages/pros of the Adjacency List Representation?
02.27 What are the disadvantages/cons of the Adjacency List Representation?
02.28 Describe the Adjacency Tensor approach of Graph Representation.
02.29 Give a small example graph then represent it using the Adjacency Tensor approach of Graph Representation.
02.30 Represent the following Graph using Adjacency Tensor approach of Graph Representation
Edges: {0, 1} {0, 4} {1, 2} {1, 3} {1, 4} {2, 3} {3, 4}
02.31 What are the advantages/pros of Adjacency Tensor Representation?
02.32 What are the disadvantages/cons of Adjacency Tensor Representation?
02.33 True or False? Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph.
02.34 Can the Adjacency Matrix represent weighted graphs?
02.35 How easy it is you think to represent graphs using Adjacency Matrix?
02.36 What is the complexity of removing an edge from Adjacency Matrix representation?
02.37 What is the complexity of queries such as whether there is an edge between vertex a and b for Adjacency Matrix representation?
02.38 What is the Space complexity for Adjacency Matrix representation? Use vertex count to represent.
02.39 What is the complexity of adding an edge from Adjacency Matrix representation?
02.40 For the Adjacency List approach, how many total lists are there? How many vertices each list can have at best?
02.41 For the Adjacency List approach, how many lists are there for one vertex?
02.42 How much Space does the Adjacency List approach take?
02.43 How many elements does an Adjacency list contain for an undirected graph? Represent using E = edge count. For the complete representation of the Graph.
02.44 Why the complete representation of an undirected Graph using Adjacency List will have 2|E| number of elements?
02.45 How many times does an edge appear in the complete representation of the Undirected Graph using the Adjacency List?
02.46 Why the complete representation of the Directed Graph using Adjacency List will have |E| number of elements?
02.47 How many times does an edge appear in the complete representation of the Directed Graph using the Adjacency List?
02.48 How many dimensions will an Adjacency Tensor have for Tensor? What is this for Dynamic Graphs?
03 Small World Networks and Random Graphs
Source posts Open post 16299 · Topic map
03.01 What is a Graph?
03.02 Can you define graph formally?
03.03 What are the components in a Graph?
03.04 What are edges and nodes or vertices in a Graph?
03.05 Can you provide examples of Graphs? in Areas such as Science, Engineering, Medical, Biology, Social Sciences, Internet Applications, Social Media?
03.06 Can you draw a simple graph?
03.07 What is a Random Graph?
03.08 What do you use to answer questions about the properties of typical graphs?
03.09 What is the purpose of a Random Graph?
03.10 What types of graphs you use to answer questions about the properties of typical graphs?
03.11 How can you generate a Random Graph?
03.12 What is known as Small World Properties for Graphs?
03.13 Give some examples of Real Graphs
03.14 What is the connection between Real Graphs and Small World Properties?
03.15 What are some properties of Small World Networks?
03.16 Can you give examples of Non Small World Networks?
03.17 For small World Graphs – what will be the average path lengths (count of vertices) – a large number of a small number?
03.18 Are small world graphs sparse or dense?
03.19 What is power law distribution? How does that related to Small World Graphs?
03.20 How can you relate Power Law Distribution to Github network?
03.21 What is power law in statistics?
03.22 Can you name some Random Graph Generators? What is the purpose? What will they do actually in general? Why will you use these generators.
03.23 When edges are created between vertices with probability p : what is this mode of generation called? Is it a Random Graph? Why?
03.24 What happens when p = probability is closer to 0? what when p is closer to 1?
03.25 What is weight in a random graph Generator for example in the above case?
03.26 When a Graph is generated using the probability approach – what is the order of the maximum size graph?
03.27 Can you represent the graph generated above as G(n, p)? n = number of vertices, p = probability
03.28 For the above case, what happens when np < 1 ?
03.29 For the above case, what happens when np = 1 ? Can np be > 1?
03.30 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
03.31 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?
03.32 For Erdos Renyi, is the average path length short?
03.33 For Erdos Renyi, do they exhibit local clustering?
03.34 Is local clustering a property of small world graphs?
03.35 For Erdos Renyi, does it show Skewed degree distribution i.e. skewed power law distribution?
03.36 For Erdos Renyi, does it show poission distribution?
03.37 What is poission distribution? anyway?
03.38 Can you relate poission distribution to Banks or a Diagnostic Center?
03.39 What is Watts–Strogatz model for Random Graph Generation? How does it work?
03.40 Does Watts–Strogatz model create a directed graph or an undirected graph?
03.41 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.
03.42 For Watts–Strogatz, is the average path length short?
03.43 For Watts–Strogatz, do they exhibit local clustering?
03.44 Is local clustering a propery of small world graphs?
03.45 For Watts–Strogatz, does it show Skewed degree distribution i.e. skeweed power law distribution?
03.46 For Watts–Strogatz, does it show poission distribution?
03.47 how does Watts–Strogatz relate to Dirac Delta Function?
03.48 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?
03.49 How does Barabási–Albert (BA) model work? i.e. the steps i.e. the methods
03.50 For Barabási–Albert (BA) model, how is a new node added?
03.51 For Barabási–Albert (BA) model, does it start with an empty graph or with an already connected graph?
03.52 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?
03.53 For Barabási–Albert (BA) model, which nodes will accumulate more links quickly?
03.54 For Barabási–Albert (BA) model, which nodes will starve for new links?
03.55 For Barabási–Albert (BA) model, is the average path length short?
03.56 For Barabási–Albert (BA) model, do they exhibit local clustering?
03.57 For Barabási–Albert (BA) model, does it show Skewed degree distribution i.e. skeweed power law distribution?
04 HITS and PageRank
Source posts Open post 16322 · Open post 22879 · Topic map
04.01 What is HITS algorithm in Graph Mining esp. for Web?
04.02 What does HITS stand for?
04.03 What is another similar Algorithm?
04.04 What are different between the PageRank algorithm and HITS?
04.05 What is the PageRank algorithm? What is the purpose?
04.06 Where and how PageRank is used?
04.07 Where and how HITS is used?
04.08 Describe HITS?
04.09 Describe the PageRank algorithm.
04.10 What are the two core concepts in HITS algorithm?
04.11 Web-pages that serves as large directories of other pages with useful information – what are they called in HITS algorithm?
04.12 Web-pages that serves to provide information on Specific topics – what are they called in the HITS algorithm?
04.13 What are HUBs in HITS algorithm? What purpose do they serve?
04.14 What are Authorities in HITS algorithm? What purpose do they serve?
04.15 Compare HITS and PageRank.
04.16 A web-page containing links to Top 1000 Universities in the world – is this a HUB or Authority in HITS?
04.17 What is the Govt. of Canada website that provides information on all Govt. Services? Is this a Hub or an Authority?
04.18 How do you measure a Good Hub?
04.19 How do you measure a Good Authority?
04.20 Can a web-page be both Hub and Authority? Can you assign both measures to a page irrespective of how good or bad?
04.21 What are the two scores that HITS assign to a web-page?
04.22 What is authority score for a web-page?
04.23 What is the hub score for a web-page?
04.24 What does hub score measure?
04.25 What does authority score measure?
04.26 What are the three matrices that are used for HITS algorithm? i.e. when you want to implement HITS algorithm.
04.27 What is a Transition Matrix in HITS?
04.28 What is a HUB vector? What does it contain initially?
04.29 What is an Authority vector? What does it contain initially?
04.30 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}
04.31 For the same graph above, explain your transition matrix?
If Transition Matrix is A, Hub Vector = h0, Authority Vector = a0.
04.32 How is Hub Score for a page is updated?, How is Authority Score for a page is updated? How long does this update happen?
04.33 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?
04.34 What is HITS normalization? i.e. after each iteration. Why it might be important.
04.35 Give steps/equations used for HITS normalization.
04.36 What are the two ways, you can make the HITS algorithm stop? i.e. stopping points.
04.37 True or False, Destiny of PageRank and HITS were different. What does it mean?
04.38 Can you stop the HITS algorithm after a certain number of iterations?
04.39 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?
04.40 What are contextual graphs, anyway?
04.41 Give example use cases for HITS and PageRank?
04.42 Can you think of the value aspect of these algorithms? i.e. how they affect people, communities, societies?
04.43 What are the programming languages where you will find libraries that implement the HITS and PageRank algorithm? Give the name of the libraries.
04.44 Implement the algorithms from scratch in Python or in R without using the libraries. What did you use to debug your implementation and how?
04.45 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).
05 Community Detection
Source posts Open post 16300 · Open post 22883 · Topic map
05.01 What is a community anyway? Describe from your real-world/social understanding of it?
05.02 Can you relate it to the Graphs concept in Computer Science?
05.03 In your daily life do you interact with a community in a real world? or in your communication with others using technologies?
05.04 What is Graph as defined in Computer Science Books/Practice? Can you formally represent a Graph? What are the components of a graph?
05.05 Is a whole Graph a Community? or Graphs can be subsets (Subgraph) as well?
05.06 What is a Sub-graph anyway?
05.07 Can you identify communities in real-world networks? i.e. real world networks that can be represented as graphs?
05.08 Give examples of real-world Graphs as well.
05.09 Can you detect a community in the tissues or the organs in the human body? Can you represent these as Graphs?
05.10 Can you detect a community in Friends on social media with similar interests? i.e. is it a community? Can you represent these/this as Graphs?
05.11 Can you detect/define a community for the Neighborhoods where a hurricane will likely pass? i.e. is it a community?
05.12 Is it a community: People that are likely to be affected by a contagious disease?
05.13 Will the properties of a community (subgraph) be the same like the whole graph (i.e. average properties of the whole graph)? or will it differ? When? How? Why? Examples?
05.14 How does the formation of communities affect? i.e. How does the existence or not of communities affect? You can provide generic answers or just explain with examples as well.
05.15 Do you think that you are a part/node of communities in online social networks such as Facebook, twitter? If so, how and when you are affected? If so, how and when you can affect others?
05.16 Can communities affect rumor spreading or disease spreading or epidemic spreading? Can you also identify how a rumor/disease will spread i.e. from the source i.e. which path will it take, how will it flow, who will get affected?
05.17 Is it that the spreading will only affect the nodes/parts of the communities? Do you see any limitations of this thought?
05.18 Who else can get affected? Can you predict that?
05.19 What is Link prediction? What are Link Prediction Algorithms?
05.20 Is it a possibility that current communities can be fine tuned? i.e. remove links/nodes and add new links/nodes? Why, why not? How? Is it the right thing to do? why, why not?
05.21 What is the difference between clustering and community detection?
05.22 What is thought to be of more real world entitities/geared? Community Detection or Clustering?
05.23 What is thought to be more geared towards structural Properties such as Min-Cut?
05.24 What is Min-Cut anyway?
05.25 For modeling, understanding and analysis purpose – can we consider them the same/similar? Community Detection or Clustering?
05.26 What is Cluster Analysis i.e. Community Detection process? i.e. what will be your process to identify clusters/communities?
05.27 Provide the names of some Community Detection Algorithms. Can you explain them as well? Can you formally define/represent and/or show pictorially what they do and how they work (steps as well)? Check the answer section, after you give it a try. You must have studied them in Computer Networks or related courses/concepts (Data Communication, CCNA, CCNP, Vehicle Routing)
05.28 How can you evaluate that the detected communities/clusters are good/great communities/clusters?
06 Shared Nearest Neighbor Clustering
Source posts Open post 16302 · Open post 22885 · Topic map
06.01 What is one another name of the algorithm: Shared Nearest Neighbors?
06.02 What is the purpose of the Algorithm: Shared Nearest Neighbors?
06.03 Can you name other Algorithms that serve the same or similar purpose?
06.04 What is the Criteria that SNN uses?
06.05 Is SNN Hierarchical? What does Hierarchical mean in the context of Clustering/Community detection?
06.06 How does SNN work? i.e. what is the algorithm? i.e. how does SNN create clusters/communities?
06.07 Give and explain the steps in SNN with a small example.
06.08 What is threshold τ in the SNN algorithm? Is it numeric? What can be the maximum and the minimum values?
06.09 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.
06.10 What is Node Similarity or Node Proximity between two nodes in SNN?
06.11 What is the output of SNN? i.e. on an undirected and unweighted Graph?
06.12 Will the output will have weights on the edges?
06.13 Give the pseudocode for SNN algorithm
06.14 Implement the SNN algorithm in Python or R or Matlab – whichever you prefer.
06.15 Can you apply SNN on weighted Graphs?
06.16 If you can apply SNN on weighted graphs, then how will you apply the Threshold, say theta?
06.17 What is the first step in applying theta – if that is doable?
06.18 What is the difference between tau (τ) and theta.
06.19 What is k in SNN algorithms (if Weighted)?
06.20 How do we know which tau(τ) or ”k” to choose?
06.21 What are some evaluation metrics for tau or k?
06.22 what is Conductance?
06.23 Conductance whose property is this? The input graph, the output graph or the possible communities (from where you select the final communities)
06.24 Is low value or high value of Conductance – that is used for the communities?
06.25 When comparing two k or tau values – which k or tau that you accept? Think in terms of Conductance.
06.26 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?
06.27 Write a Pseudo-code for SNN on Undirected Weighted Graphs. Find the optimal value for K and tau.
06.28 Implement SNN on Undirected Weighted Graphs. Print the optimal value for K and tau.
06.29 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
07 Betweenness Based Clustering
Source posts Open post 16305 · Open post 22881 · Topic map
07.01 What are the types of Betweenness?
07.02 What is Vertex Betweenness? i.e. the concept
07.03 What is Edge Betweenness? i.e. the concept
07.04 Describe Vertex Betweenness? maybe just giving an example
07.05 What does Vertex Betweenness clustering achieve? i.e. the output?
07.06 Give an Algorithm for Vertex Betweenness Clustering?
07.07 What is mu in the Algorithm for Vertex Betweenness Clustering?
07.08 Which vertex do you select at each step? i.e. the one with the highest betweenness or the lowest betweenness?
07.09 When you select a vertex at each step? Then what do you do (i.e. to create clusters)
07.10 Does the selected vertex go to all the clusters created around it?
07.11 What is the other name for Edge Betweenness?
07.12 Describe Edge Betweenness? maybe just giving an example
07.13 What does Edge Betweenness clustering achieve? i.e. the output?
07.14 Give an Algorithm for Edge Betweenness Clustering?
07.15 What is mu in the Algorithm for Edge Betweenness Clustering?
07.16 Which Edge do you select at each step? i.e. the one with the highest betweenness or the lowest betweenness?
07.17 When you select an Edge at each step? Then what do you do (i.e. to create clusters)
07.18 Does the selected Edge go to all the clusters created around it? or you just cut the graph at that edge and create clusters.
08 Minimum Spanning Trees and Clustering
Source posts Open post 16306 · Topic map
08.01 What is a Spanning Tree?
08.02 What is a Minimum Spanning Tree?
08.03 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}
08.04 What is a minimum spanning tree?
08.05 What is the minimum spanning tree for the graph as provided above?
08.06 What is Prim’s Algorithm for Spanning Trees?
08.07 Describe the steps as used in Prim’s Algorithm?
08.08 Give the Algorithm i.e. Prim’s Algorithm?
08.09 Write pseudo-code for Prim’s Algorithm?
08.10 Implement Prim’s Algorithm in Python, R, Matlab, or in any other language of your choice?
08.11 What is the initialization step in Prim’s Algorithm?
08.12 Can you choose any node to start with Prim’s Algorithm?
08.13 True or False, Prim’s algorithm does not include all nodes in the output?
08.14 How an edge/path is selected in Prim’s Algorithm?
08.15 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)?
08.16 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)?
08.17 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)?
08.18 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.
08.19 How long will you continue to add new edges to the MST? i.e. terminating condition for your algorithm.
08.20 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}
08.21 What is K-Spanning tree?
08.22 What are the steps in K-Spanning Tree?
08.23 Give the Algorithm for K-Spanning?
08.24 Write pseudo-code for K-Spanning?
08.25 Implement the K-Spanning tree algorithm in Python, R, Matlab, or in any other language of your choice?
08.26 What is K in the K-Spanning Tree algorithms?
08.27 How many edges do you remove to create k Clusters?
08.28 What is the first step in the K-Spanning tree?
08.29 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?
09 Highly Connected Subgraphs and Minimum Cuts
Source posts Open post 16324 · Topic map
09.01 How do you define: Highly Connected?
09.02 What is a Cluster?
09.03 What is Subgraph?
09.04 Does connectivity indicate the number of edges between clusters?
09.05 True or false: Highly connected clustering means: within a cluster, connectivity will be low. Across clusters, connectivity will be high.
09.06 True or false: Highly connected clustering means: within clusters, connectivity will be high. Across clusters, connectivity will be low.
09.07 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.
09.08 What are some of the core concepts/terms that are related to Highly connected clustering?
09.09 What is a Cut when it comes to Highly connected clustering?
09.10 What is a Minimum Edge Cut when it comes to Highly connected clustering?
09.11 Describe Edge Connectivity for Highly connected clustering?
09.12 Contrast Cut and Minimum Edge Cut for Highly connected clustering?
09.13 Identify is this a Cut or a Minimum Edge Cut: The edges whose removal will disconnect the Graph?
09.14 Identify is this a Cut or a Minimum Edge Cut: The minimum edges whose removal will disconnect the Graph?
09.15 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.
09.16 True or false: The more edges are there in a group of vertices – the more connected they are?
09.17 True or false: The more edges are there in a group of vertices – the more similar are the vertices?
09.18 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?
09.19 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
09.20 Is it a highly connected subgraph? For V vertices, the minimum edge cut contains less than V/2 edges? Why? or Why not?
09.21 Is it a highly connected subgraph? For V vertices, the minimum edge cut contains more than V/2 edges? Why? or Why not?
09.22 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}
09.23 What is the minimum edge cut for the above graph?
09.24 What is V/2 for the above Graph?
09.25 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?
09.26 Why we use V/2 to check for a Highly connected subgraph?
09.27 What is the maximum diameter of every single highly connected graph? Can you please explain.
09.28 What is the number of edges in a highly connected subgraph?
09.29 True or false: For highly connected subgraphs, the number of edges will be at least V^2/4?
09.30 True or false? explain: the number of edges in a highly connected subgraph is quadratic?
09.31 True or false: the number of edges in a highly connected subgraph is at most two?
09.32 Give and Describe the steps for creating/finding highly connected subgraphs.
09.33 Give the algorithm and pseudo-code Highly connected subgraphs?
09.34 What are the input and output for Highly connected subgraphs?
09.35 As we saw the definition of Min Edge Cut, can it be used in an algorithm for finding highly connected subgraphs?
09.36 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?
09.37 When will the Algorithm stop? i.e. Terminating Condition?
09.38 What are the algorithms to find the minimum edge cut for graphs?
09.39 Can you apply Karger’s algorithm for Minimum Cut to Weighted Graphs? if so, How? What was its intended purpose?
09.40 Can you apply Stoer-Wagner’s algorithm for Minimum Cut to Unweighted Graphs? if so, How? What was its intended purpose?
09.41 What is the core concept of Karger’s algorithm?
09.42 What is the “contraction of an edge” in Karger’s algorithm?
09.43 What is the number of edge reduction caused by “contraction of an edge”?
09.44 In Karger’s algorithm when you merge two nodes u and v, what happens to the edges that were previously connected to those nodes?
09.45 What is the complexity of Karger’s algorithm?
09.46 What is the complexity of Karger’s algorithm? is it O(E) or O(V) or O (Log(E))
09.47 Describe Karger’s algorithm?
09.48 Give the steps in Karger’s algorithm?
09.49 Describe Pseudo-code and Python/C++/R/Java code for Karger’s algorithm?
09.50 What is the input for Karger’s algorithm? What is the output?
09.51 What is the terminating condition for Karger’s algorithm?
09.52 Can you continue with Karger’s algorithm when there are <= 2 vertices left?
09.53 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
09.54 Will Karger’s algorithm? always create Min Cut?
09.55 What is the probability that Karger’s algorithm will create Min Cut?
09.56 For a 10 node graph, is the probability = 1/100?
09.57 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?
09.58 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)?
10 Louvain Modularity
Source posts Open post 16323 · Open post 26233 · Topic map
10.01 What is the primary problem that Louvain Modularity solved?
10.02 Is Louvain good at detecting small communities?
10.03 What is modularity in Graphs?
10.04 What is the range of values used to show the modularity of a Graph?
10.05 What is the equation for Modularity? You can just only explain conceptually – what are the parameters/parts – how do the parameters work?
10.06 Give the algorithm for Louvain Modularity? You can just describe or you can show the steps.
10.07 Give the Pseudo-code for Louvain Modularity and implement in Python or R or C/C++?
10.08 Is Louvain Modularity easily parallelize-able or it is more sequential?
10.09 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.
10.10 What is the first step in Louvain Algorithm?
10.11 True or False, at first step, all nodes are assigned to one community?
10.12 True or false, at first each node is assigned to it’s own community? i.e. no of vertices = no of communities
10.13 What are the two steps in Louvain Algorithm? What is the name of the steps?
10.14 What can be the terminating condition for the Louvain Algorithm?
10.15 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?
10.16 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)
10.17 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)?
10.18 What is Modularity Optimization in Louvain modularity? Describe the steps/process for this Optimization.
10.19 What is the second step/phase for the Louvain Algorithm? What it is called? What happens here? what are the steps/process?
10.20 Is the Louvain Algorithm supervised?
10.21 Is the Louvain Algorithm fast or slow?
10.22 How many passes do the Louvain Algorithm require to create the communities?
10.23 What is the resolution limit for the Louvain Algorithm?
10.24 When the resolution limit is low, do you get more/smaller communities?
10.25 When the resolution limit is high, do you get less/larger output communities?
10.26 What is the numerical range used for the resolution limit?
11 Link Prediction and Node Similarity
Source posts Open post 16297 · Topic map
11.01 What is Link Prediction in Graph Mining?
11.02 How can Link Prediction help? and where? can it help in social network, research co-authorship, or spread of disease
11.03 Give uses of Link Prediction in epidemiology or any medical/biology application?
11.04 Give uses of Link Prediction in Social Network?
11.05 Give uses of Link Prediction in co-authorship?
11.06 What are the steps in Link Prediction? i.e. define link prediction problem.
11.07 Define Link Prediction Problem formally i.e. with Notations i.e. with Graph notations i.e. Graph Representations.
11.08 How is node similarity related in Link Prediction?
11.09 What are possible Node Similarity algorithms that can be used for the purpose?
11.10 Which nodes are the most possible new links? think in terms of Node Similarity Index (Highest, Lowest)
11.11 What are the types of Node Similarity? Node proximity?
11.12 What is Node Similarity based upon? i.e. Network Topology
11.13 What is Local Structure for Node Similarity?
11.14 What is Global Structure for Node Similarity?
11.15 What are examples of Local Structure for Node Similarity?
11.16 What are examples of Global Structure for Node Similarity?
11.17 Define Node Neighborhoods. Is it local or global structure?
11.18 What is Preferential Attachment Index? Is it LocaL or global structure
11.19 What are the types of Node Neighborhoods?
11.20 If two nodes do not have any common node — what is the probable similarity (Node Neigh. aspect)?
11.21 What is Common Neighbors ? Is it local or global structure? is it Node Neighbor or Preferential Attachment? and why?
11.22 What is Jaccard Coefficient ? Is it local or global structure? is it Node Neighbor or Preferential Attachment? and why?
11.23 What is Adamic-Adar? Is it local or global structure? is it Node Neighbor or Preferential Attachment? and why?
11.24 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?
11.25 What is the name of the Node Similarity approach where the ratio of seize of set intersection to the set union is counted?
11.26 What is the name of the Node Similarity approach where the count of common nodes are used?
11.27 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?
11.28 When similarity scores are calculated based on global link structure of graph – what is this called local structure or global structure?
11.29 What is an example of Global Structure?
11.30 What are the examples of Global Structure?
11.31 What is Kartz Index for Global Structure?
11.32 What is Simrank for Global Structure?
11.33 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?
11.34 When Node Similarity is calculated as: two nodes are similar if they are referred by similar nodes. What is the name?
11.35 How can you measure if your implemented link prediction algorithm is great or not?
11.36 Can you use train and test concept for the measurement? Can you define the steps/problems formally? with Graph Notations?
11.37 What are some measures to calculate in the train/test approach?
12 Time Evolving Graphs
Source posts Open post 22887 · Topic map
12.01 What is a time dependent graph?
12.02 Can you name a time dependent graph that you interact with everyday? Or that a good number of people interact everday/very often?
12.03 True or False? Time Dependent Graphs change over time?
12.04 True or False? Edge weights of Time Dependent Graphs change over time?
12.05 Give examples of real-life scenarios that can be modeled very effectively using Time Dependent Graphs?
12.06 What is time-dependent relationship?
12.07 Give some examples of Allen’s time-dependent relationships in Graphs.
12.08 Visualize Allen’s time-dependent relationships in Graphs. i.e. Show in Graphs.
12.09 What are the approaches to model the data provided through a time dependent graphs?
12.10 Can you give examples on how you might be able to utilize time dependent graphs in your domain?
12.11 How do you represnt time dependent graphs in Neo4j? Show/visualize an example?
13 Assignments and Project Prompts
Source posts Open post 22891 · Topic map
13.01 Implement graph algorithms from scratch and apply them to a suitably chosen network.
The post lists BFS, DFS, single-source and all-pairs shortest paths, Dijkstra’s algorithm, minimum cuts including Karger’s method, and clique algorithms.
13.02 Run comparable graph-library implementations on the same datasets. Do they give the same results?
Use a library such as NetworkX in Python. Keep the graph and assumptions the same when comparing with your own implementation.
13.03 Implement spanning trees and highly connected subgraphs.
13.04 Run graph-property queries on small and large datasets.
Find isolated vertices, count bidirectional edges and cliques, find the 10 highest in-degrees and 100 highest out-degrees, and count disconnected subgraphs.
13.05 Implement vertex betweenness, edge betweenness, and closeness centrality on a graph dataset such as political blogs.
13.06 Implement page-ranking methods such as HITS and analyze hubs and authorities.
13.07 Choose a real graph-mining case study and identify a dataset suitable for reproducing the analysis.
The post lists communication patterns, fraud detection, changes in communication networks, web projections, and connection subgraphs.
13.08 Can you represent dengue case or contact observations as a graph and study possible patterns of spread?
13.09 Select a large-scale graph-mining function, apply it to a large graph, and investigate how an algorithm could be improved.
Examples in the post include graph partitioning, clustering, connected components, similarity and link models, streaming graphs, centrality, and graph construction.
Published Answer Notes and Checks
These notes summarize selected answers printed in the posts. They are not a complete answer key. Where a published answer conflicts with the graph or notation in its own example, the check is marked separately.
01 Graph Mining Foundations
Source posts Open post 16311
Definition and applications. The post defines graph mining as discovering and analyzing graph data. Examples include fraud detection, finding communities and influential nodes, and recommending connections. It names application areas including transport, biology, chemistry, chip design, computer networks, and the semantic web.
Modeling examples. In a social network, users are vertices and friend or follower relationships are edges. For protein interactions, proteins are vertices and physical interactions are edges. For a semantic graph, concepts are vertices and properties or relationships are edges. The post gives character co-occurrence and student enrolment as examples of turning nongraph data into a graph.
Network and graph. The post uses network for a real system of connected entities and graph for its mathematical representation. It notes that the terms are often used interchangeably.
02 Graph Types and Representations
Source posts Open post 16312 · Open post 26231
Graph classifications. The post lists directed and undirected, attributed and unattributed, weighted and unweighted, bipartite and more general, signed, static and evolving graphs. It also mentions trees, loops, multiple edges, and isomorphism.
Representations. It names adjacency matrices and adjacency lists for static graphs and a three-dimensional adjacency tensor for time-indexed graph data.
03 Small World Networks and Random Graphs
Source posts Open post 16299
Models and examples. The post names Erdős–Rényi, Watts–Strogatz, and Barabási–Albert. It describes adding edges at random and lists examples of real networks including food webs, power grids, social influence, and linked proteins.
Small-world properties. The post highlights short average paths and high local clustering. Its references also discuss examples of networks that lack these properties and introduce power-law relationships.
Model-specific quantities. For the Watts–Strogatz construction described, the edge total is NK/2 when each of N vertices begins with an even neighborhood degree K and edge rewiring preserves the count. With no rewiring, every node has degree K. The post gives n^(2/3) as a component-size order for the probability model. That order applies at the critical regime of the Erdős–Rényi model, not for every value of p.
04 HITS and PageRank
Source posts Open post 16322 · Open post 22879
Initial matrix and vectors. With row and column order Yahoo, Amazon, Microsoft, the blog gives adjacency rows [1, 1, 1], [1, 0, 1], [0, 1, 0]. Both initial vectors have all three entries set to one. Entry (i, j) is one when page i links to page j.
Checked direction of updates. With the source’s row-as-origin convention, a raw hub update is A times the authority vector. A raw authority update is the transpose of A times the hub vector. This spells out the source’s ambiguous wording about the incoming-link update.
05 Community Detection
Source posts Open post 16300 · Open post 22883
Communities and clustering. The post describes a community as a node subset with denser internal connections than connections to the rest of the network. It treats graph clustering as grouping nodes by a similarity criterion, with overlap possible in some methods.
Algorithm examples. The post lists maximal cliques, K-spanning-tree clustering, shared nearest neighbors, highly connected components, min-cut, betweenness methods, Louvain modularity, and CNM.
06 Shared Nearest Neighbor Clustering
Source posts Open post 16302 · Open post 22885
Shared neighbors. The post uses Jarvis–Patrick as a related shared-neighbor method and says the version it discusses is not hierarchical. It measures similarity by counting common neighbors and, in its weighted-graph example, retains k neighbors.
Alternative algorithms. The selected answers also list maximal-clique, tree-cut, min-cut, betweenness, Louvain, CNM, and highly connected component approaches.
07 Betweenness Based Clustering
Source posts Open post 16305 · Open post 22881
Vertex and edge betweenness. The post describes counting shortest paths through a vertex or an edge, with paths taken across node pairs. It names Girvan–Newman as an edge-betweenness clustering method.
08 Minimum Spanning Trees and Clustering
Source posts Open post 16306
Spanning trees and cut weights. The post defines a spanning tree as a connected, cycle-free subgraph containing all vertices. It describes Prim’s method for finding a minimum spanning tree. For clustering with distance weights, it says to remove the highest-weight tree edges.
Verified correction to the worked example. The post first calls its weight-17 tree a minimum spanning tree. It is a valid spanning tree, but not minimum. The later Prim sequence in the same post gives (5, 4, 4), (3, 4, 2), (3, 2, 3), and (1, 3, 2), with total weight 11. Those are the four lightest edges in the example, and they already form a spanning tree.
09 Highly Connected Subgraphs and Minimum Cuts
Source posts Open post 16324
Highly connected graph check. For the source’s nine-node fixture, the answer gives a minimum cut of 2 and a threshold of 9/2 = 4.5. Since 2 is not greater than 4.5, the graph does not pass the stated highly connected condition.
11 Link Prediction and Node Similarity
Source posts Open post 16297
Local similarity. The answers identify Adamic–Adar for inverse-log weighting of shared neighbors, Jaccard for intersection divided by union, common neighbors for the intersection count, and preferential attachment for the product of node degrees in the stated setup.
Global similarity and evaluation. The post names inverse shortest-path distance, the Katz index, and SimRank. It lists accuracy, F1 score, and sensitivity as candidate evaluation metrics.
12 Time Evolving Graphs
Source posts Open post 22887
Temporal settings. The post gives bioinformatics networks, transportation networks, and social networks as examples where time-dependent graphs are relevant.
Search Scope
The inventory combines the blog’s Graph Mining category with site-wide searches for Graph Mining and terms such as PageRank, Louvain, shared nearest neighbors, link prediction, community detection, and temporal graphs. Generic posts that only mention graph mining in a list are not counted. Posts that only link to a practice set are indexed as resources, not question-bearing sources.
Set
Topic
Prompts
01
Graph Mining Foundations
20
02
Graph Types and Representations
48
03
Small World Networks and Random Graphs
57
04
HITS and PageRank
45
05
Community Detection
28
06
Shared Nearest Neighbor Clustering
29
07
Betweenness Based Clustering
18
08
Minimum Spanning Trees and Clustering
29
09
Highly Connected Subgraphs and Minimum Cuts
58
10
Louvain Modularity
26
11
Link Prediction and Node Similarity
37
12
Time Evolving Graphs
11
13
Assignments and Project Prompts
9
