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