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