Graph Mining: Misc. Topics to Learn: Misc. Resources to Learn From

• Influence/Virus/Label Propagation
  • Resources to learn fromPage
  • A presentation on Influence/Virus PropagationURL
• Big Data Graph Databases
  • Resources to Learn FromPage
  • Graph DatabaseURL
  • Neo4jPage
• Big Data Graph Processing
  • Resources to Learn FromPage
  • ToolURL
  • Techniques, Tools and Applications of Graph AnalyticURL
  • Graph Processing with HadoopURL
  • Graph Processing: GraphX, GraphFramesPage
• Social Network Analysis
  • Learn From: Social Network AnalysisURL
  • Some other topics before relates to this topic. https://hpi.de/fileadmin/user_upload/fachgebiete/mueller/courses/graphmining/GraphMining-02-Social-Network-Analysis.pdf
• Querying Graphs: Isomorphic Graphs
  • Learn From: Querying Graphs: Isomorphic GraphsURL
  • https://hpi.de/fileadmin/user_upload/fachgebiete/mueller/courses/graphmining/GraphMIning-03-Querying-Graphs.pdf
• Mining graph patterns
  • Learn From: Mining graph patternsURL
  • https://hpi.de/fileadmin/user_upload/fachgebiete/mueller/courses/graphmining/GraphMining-04-FrequentSubgraph.pdf
• Graph Mining and Classifications
  • Resources to Learn FromPage
  • Resources to Learn From: All topics belowPage
  • Graph Classifications: Resources to Learn FromPage
  • Graph Kernel (Based Classifications) : ResourcesPage
• Tools and Examples
  • List 1: Top 30 Social Network Analysis and Visualization ToolsURL
  • Commetrix, Cuttlefish, Cytoscape, EgoNet, Gephi, Graph-tool, GraphChi, Graphviz
  • List 2: Graph Analytics ToolsURL igraph, NetworkX, graph-tool, Gephi, SNAP, JUNG, Mathematica, D3.js, Cytoscape
• Probable Assignments
  • Graph Datasets for Assignments and Projects; also for researchPage
  • You will see many datasets on the URL: You can apply your implementation on a dataset/graph of your choice though make sure the properties (directed/undirected/weighted/unweighted/connected/not-connected and others) match with the question.
  • Python or R Libraries for Graph Mining ImplementationsPage
  • https://networkx.github.io/documentation/latest/_downloads/networkx_reference.pdfhttps://networkx.github.io/documentation/stable/reference/introduction.html
    
    
  • List 1: Implement the following algorithms and apply on large graphs (in Plain Python or R without Graph Libraries)Page
  • Click the above link for details: BFS, DFS, Single Source Shortest Path, All pair shortest path, Karger’s Algorithm, Min-Cut Algorithm, Cliques Algorithms, Dijiktra’s Shortest Path implementation (for shortest paths or the longest paths)
    More will be added later .. any algorithm that you will come across can be an assignment as well. You might try to study and implement the most important algorithms that are used practically and are famous (or solve important problems)
  • List 2: Use Graph Algorithms provided by NetworkX (Python, R) librariesPage
  • Assignments related to demonstrating the capability to be able to use the Graph Algorithms provided in the NetworkX library. Such as find the related library methods/algorithm as mentioned in list 1 and apply on the same datasets : do you get the same results.
  • List 3: Spanning Tree, Connected SubgraphsPage
  • In Short: Implement Spanning Tree, and Highly Connected Subgraphs
  • List 4: Based on Graph Properties and ConceptsPage
  • Given a graph (use a data-set or a small graph first) then apply on large graphs. Write Python or R code to Identify the isolated nodes in the graph, count  bi-directional edges in the graph,  identify top 10 vertices based on in-degrees, identify top 100 vertices based on their out-degrees, count the number of cliques in the Graph, identify number of disconnected subgraphs.
    
  • List 5: Centrality-PageRank-Betweenness
  • For a Graph/graph-dataset such as political blogs (see example dataset section), implement Vertex Betweenness, Edge Betweenness, Closeness Centrality.
    
    Implement Page ranking Algorithms such as HITS and Anchor/Hubs
• Potential Project Ideas
  • List 1: Project Ideas with real life applicationsPage
  • From: https://cs.stanford.edu/people/jure/talks/www08tutorial/, you need to find datasets to implement these ideas. Check the above URLs for DataSets (I did not check yet)
    
    Part 4: Case studies
    • Communication patterns of MSN Messenger. The application of above mentioned tools and algorithms to a large network of communication on MSN Instant Messenger (30 billion conversations, 240 million people).
    • Detecting fraud on eBay. How to find fraudulent people on eBay. We present a belief propagation method that is able to find fraudulent people in large networks.
    • Monitoring social and communication networks over time — intrusion and outlier detection. An application of tensor decomposition techniques to monitor multiple time series over time and detect outliers and abnormal events
    • Web projections. Exploiting the structure of web graph to predict the quality of search results, user intention to reformulate queries and to find spam search results.
    • Connection subgraphs and CenterPiece subgraphs.
  • List 2: Check the Data Science Competitions to get Project IdeasPage
  • Click above and Check the Data Science Competitions to get Project Ideas. For example, can you map current dengue spread into a graph, and predict the path for how the disease will spread?
  • List 3: Take a Google Function Area in Graph Mining and Apply on Very Large Graphs and see what insight you can getPage
  • You can as well do research in any of these areas to improve the algorithms and performance as well as apply on new problems/challenges.Google Job Areas: 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
• Potential Research Topics
  • List 1: Research on Google Job/Function areas in Graph MiningPage
  • Take one of these Google job/function areas in Graph Mining and improve the algorithms for performance as well as apply on new problems/challenges.Google Job Areas: 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
• Example Projects in Graph Mining
  • My Implementation: Louvian Algorithm for Community Detection in Large Graph NetworksURL
  • https://github.com/sayedum/spark-implementation-louvian-modularity.git.
    This is a private repository. I might give access to it to selected participants. You have to request for it. I need to know what will you do with it. This utilized PySpark, Spark GraphFrames on Hadoop Platforms. There is a non-spark, non-parallel, Python implementation as well. With some extensions and trying to answer the right question – this has the potential to become a research publication as well.
  • GraphX Implementation of Louvian Modularity Algorithm for Community DetectionURL
  • https://github.com/Sotera/spark-distributed-louvain-modularity.Not my implementation. GraphX is kind of older than GraphFrame.
  • PageRank Algorithm ImplementationURL
  • https://www.geeksforgeeks.org/page-rank-algorithm-implementation/ . Not my implementation. I might share code blocks from my implementation.
  • Centrality and Betweenness or similar concept implementation.URL
  • https://www.geeksforgeeks.org/betweenness-centrality-centrality-measure/However, it will be the best, first you try to implement on your own. Better that you just don’t memorize; however, try to earn the capability to convert textual concept/algorithm (mathematics) into code.

• Dijkstra’s shortest path algorithmURL
• https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
• Floyd Warshall Algorithm | All pair Shortest PathURL
• https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/
• Karger’s mincut algorithm in PythonURL
• Details: http://goatleaps.xyz/programming/kargers-algorithm.html Code File: http://goatleaps.xyz/assets/code/kargers_mincut.py

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

Graphs are everywhere. https://pdfs.semanticscholar.org/144b/130323cb94d618c2c5e66982a56f31d36396.pdf
Click https://pdfs.semanticscholar.org/144b/130323cb94d618c2c5e66982a56f31d36396.pdf link to open resource.

Learn From: Anomaly Detection and Graph Mining

https://hpi.de/fileadmin/user_upload/fachgebiete/mueller/courses/graphmining/GraphMining-13a-AnomalyDetection.pdf
Click https://hpi.de/fileadmin/user_upload/fachgebiete/mueller/courses/graphmining/GraphMining-13a-AnomalyDetection.pdf link to open resource.

Graph based Anomaly Detection and Description: A Survey

Graph based Anomaly Detection and Description: A Survey
Click https://www.andrew.cmu.edu/user/lakoglu/pubs/14-dami-graphanomalysurvey.pdf link to open resource.

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

To Learn From: Time Evolving GraphsURL

https://link.springer.com/article/10.1007/s41019-019-00105-0

Learn by finding the answers to the following questions from the given/external resources?

Time Dependent Graphs

What is a time dependent graph?

Can you name a time dependent graph that you interact with everyday? Or that a good number of people interact everday/very often?

True or False? Time Dependent Graphs change over time?

True or False? Edge weights of Time Dependent Graphs change over time?

Give examples of real-life scenarios that can be modeled very effectively using Time Dependent Graphs?

What is time-dependent relationship?

Give some examples of Allen’s time-dependent relationships in Graphs.

Visualize Allen’s time-dependent relationships in Graphs. i.e. Show in Graphs.

What are the approaches to model the data provided through a time dependent graphs?

Can you give examples on how you might be able to utilize time dependent graphs in your domain?

How do you represnt time dependent graphs in Neo4j? Show/visualize an example?

More questions will be added later….

Some Answers:
Give examples of real-life scenarios that can be modeled very effectively using Time Dependent Graphs?

Ans: bioinformatics networks, transportation networks, and social networks

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

Resources to Learn From

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

Read the resources above to find answers. Shared Nearest Neighbors : Clustering : Community Detection

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

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

Resources to Learn From

Resources:
Defining and identifying communities in networks
https://www.pnas.org/content/101/9/2658


Community Structure:
https://en.wikipedia.org/wiki/Community_structure

Graph Clustering:
https://www.csc2.ncsu.edu/faculty/nfsamato/practical-graph-mining-with-R/slides/pdf/Graph_Cluster_Analysis.pdf

Read the resources above to find answers. Community Detection: Learn by finding answers to the following questions. Can you answer the following questions on Community Detection?

Graph Mining: Community Detection: Learn by finding answers to the following questions. Can you answer the following questions on Community Detection?

What is a community anyway? Describe from your real-world/social understanding of it?

Can you relate it to the Graphs concept in Computer Science?

In your daily life do you interact with a community in a real world? or in your communication with others using technologies?

What is Graph as defined in Computer Science Books/Practice? Can you formally represent a Graph? What are the components of a graph?

Is a whole Graph a Community? or Graphs can be subsets (Subgraph) as well?

What is a Sub-graph anyway?

Can you identify communities in real-world networks? i.e. real world networks that can be represented as graphs?

Give examples of real-world Graphs as well.

Can you detect a community in the tissues or the organs in the human body? Can you represent these as Graphs?

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?

Can you detect/define a community for the Neighborhoods where a hurricane will likely pass? i.e. is it a community?

Is it a community: People that are likely to be affected by a contagious disease?

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?

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.

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?

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?

Is it that the spreading will only affect the nodes/parts of the communities? Do you see any limitations of this thought?

Who else can get affected? Can you predict that?

What is Link prediction? What are Link Prediction Algorithms?

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?

What is the difference between clustering and community detection?

What is thought to be of more real world entitities/geared? Community Detection or Clustering?

What is thought to be more geared towards structural Properties such as Min-Cut?

What is Min-Cut anyway?

For modeling, understanding and analysis purpose – can we consider them the same/similar? Community Detection or Clustering?
Ans: Yes

What is Cluster Analysis i.e. Community Detection process? i.e. what will be your process to identify clusters/communities?

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)

How can you evaluate that the detected communities/clusters are good/great communities/clusters?

Answers:
What is a community?
a subset of nodes within the graph such that connections between the nodes (in the subset) are denser than connections with the rest of the network (i.e. from the subset to the outer nodes)

What is Cluster Analysis i.e. Community Detection process? i.e. what will be your process to identify clusters/communities?
“The process of dividing nodes of a graph into possibly overlapping, subsets, where nodes in each subset are considered related by some similarity measure”

Provide the names of some Community Detection Algorithms
Maximal-Clique Enumeration, K- Spanning Tree, Shared Nearest Neighbor, Highly Connected Components, MinCut, Betweenness Based Algorithms, Louvain Modularity, CNM Algorithm

Resources:
Defining and identifying communities in networks
https://www.pnas.org/content/101/9/2658

Community Structure:
https://en.wikipedia.org/wiki/Community_structure

Graph Clustering:
https://www.csc2.ncsu.edu/faculty/nfsamato/practical-graph-mining-with-R/slides/pdf/Graph_Cluster_Analysis.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

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

Resources to Learn From

A Book.

Nagiza F. Samatova, William Hendrix, John Jenkins, Kanchana Padmanabhan, and Arpan Chakraborty. 2013. Practical Graph Mining with R. Chapman & Hall/CRC.

Read the resources above to find answers. Betweenness Based Clustering: Learn by finding answers to the following questions. Can you answer the following?

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)

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

Resources to Learn From

Resources:

HITS Algorithm
https://en.wikipedia.org/wiki/HITS_algorithm

http://pi.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture4/lecture4.html
Last modified: Thursday, 24 October 2019, 9:32 PM

Read the resources above and Learn by finding Answers to the Following Questions. Can you answer the following questions?

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
Last modified: Wednesday, 30 October 2019, 5:40 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

Resources to Learn From

Resources to Learn From

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

phpFox Features: Start your own Social Network
https://www.phpfox.com/features/

Bipartite graph
https://en.wikipedia.org/wiki/Bipartite_graph

Tree (data structure)
https://en.wikipedia.org/wiki/Tree_(data_structure)

Tree structure
https://en.wikipedia.org/wiki/Tree_structure

Signed graph
https://en.wikipedia.org/wiki/Signed_graph

Gene regulatory network
https://en.wikipedia.org/wiki/Gene_regulatory_network

Dynamic Influence Analysis in Evolving Networks (VLDB’16)
https://www.slideshare.net/todo314/dynamic-influence-analysis-in-evolving-networks-vldb16

Introduction to Graph Theory
https://www.csc2.ncsu.edu/faculty/nfsamato/practical-graph-mining-with-R/slides/ppt/Introduction_to_Graph_Theory.ppt

Graph and its representations
https://www.geeksforgeeks.org/graph-and-its-representations/

Representing graphs
https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

https://www.geeksforgeeks.org/graph-and-its-representations/

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

Learning Outcomes

Knowledge Based Outcome:

• Students will be able to Identify, Describe, and Apply Graph Mining Concepts and Algorithms to Real World challenges and applications
• Describe big data challenges when it comes to Graphs and Graph mining. Relate and explain, and discover solutions for mining big data graphs
• Define and explain fundamental Graph Concepts and Algorithms along with fundamental Graph Mining Concepts and Algorithms

Skills Based Outcome:

• Implement core Graph Mining algorithms in Python and/or R
• Practice tools and libraries such as NetworkX, Gephi for Graph Mining
• Familiarize and practice Jupiter Notebook, Eclipse Python IDE, R Studio for implementation

Value Based Outcome:

• Describe ethical and legal considerations when applying to real world changes i.e how that affect the people and society 
• Collaborative Group Work with respect to others and without authoritative interactions and attitudes; however, with caring and respectful attitude
• Take responsibility for ones’ actions and give proper credit to others where applicable

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