Graph Mining - 002: SMALL WORLD GRAPHS & RANDOM GRAPH GENERATORS
Graph Mining: SMALL WORLD GRAPHS & RANDOM GRAPH GENERATORS: Learn by finding answers to the following questions.
Can you answer the following?
What is a Graph?
Can you define graph formally?
What are the components in a Graph?
What are edges and nodes or vertices in a Graph?
Can you provide examples of Graphs? in Areas such as Science, Engineering, Medical, Biology, Social Sciences, Internet Applications, Social Media?
Can you draw a simple graph?
What is a Random Graph?
What do you use to answer questions about the properties of typical graphs?
What is the purpose of a Random Graph?
What types of graphs you use to answer questions about the properties of typical graphs?
How can you generate a Random Graph?
What is known as Small World Properties for Graphs?
Give some examples of Real Graphs
What is the connection between Real Graphs and Small World Properties?
What are some properties of Small World Networks?
Can you give examples of Non Small World Networks?
For small World Graphs - what will be the average path lengths (count of vertices) - a large number of a small number?
Are small world graphs sparse or dense?
What is power law distribution? How does that related to Small World Graphs?
How can you relate Power Law Distribution to Github network?
What is power law in statistics?
Can you name some Random Graph Generators? What is the purpose? What will they do actually in general? Why will you use these generators.
When edges are created between vertices with probability p : what is this mode of generation called? Is it a Random Graph? Why?
What happens when p = probability is closer to 0? what when p is closer to 1?
What is weight in a random graph Generator for example in the above case?
When a Graph is generated using the probability approach - what is the order of the maximum size graph?
Can you represent the graph generated above as G(n, p)? n = number of vertices, p = probability
For the above case, what happens when np < 1 ?
For the above case, what happens when np = 1 ? Can np be > 1?
When a Graph G(n, p) is generated using the probability approach as mentioned above - and when np < 1, what is the order of the size of a connected component? is it O(n), or o(n), O(log(n)), O(Olog(n)). Check answer section
What is Erdos Renyi? Is it the name of a Random Graph Generator or the name of a small world property or a statistical law?
For Erdos Renyi, is the average path length short?
For Erdos Renyi, do they exhibit local clustering?
Is local clustering a property of small world graphs?
For Erdos Renyi, does it show Skewed degree distribution i.e. skewed power law distribution?
For Erdos Renyi, does it show poission distribution?
What is poission distribution? anyway?
Can you relate poission distribution to Banks or a Diagnostic Center?
What is Watts–Strogatz model for Random Graph Generation? How does it work?
Does Watts–Strogatz model create a directed graph or an undirected graph?
For Watts–Strogatz model, if the desired Node count is N, then what will be the output edge count? You can introduce and define a new parameter if required.
For Watts–Strogatz, is the average path length short?
For Watts–Strogatz, do they exhibit local clustering?
Is local clustering a propery of small world graphs?
For Watts–Strogatz, does it show Skewed degree distribution i.e. skeweed power law distribution?
For Watts–Strogatz, does it show poission distribution?
how does Watts–Strogatz relate to Dirac Delta Function?
what is Barabási–Albert (BA) model? Is it the name of a Random Graph Generator or the name of a small world property or a statistical law?
How does Barabási–Albert (BA) model work? i.e. the steps i.e. the methods
For Barabási–Albert (BA) model, how is a new node added?
For Barabási–Albert (BA) model, does it start with an empty graph or with an already connected graph?
For Barabási–Albert (BA) model, how a new node is connected to an existing node? What does it depend upon? How does a probability play a role?
For Barabási–Albert (BA) model, which nodes will accumulate more links quickly?
For Barabási–Albert (BA) model, which nodes will starve for new links?
For Barabási–Albert (BA) model, is the average path length short?
For Barabási–Albert (BA) model, do they exhibit local clustering?
For Barabási–Albert (BA) model, does it show Skewed degree distribution i.e. skeweed power law distribution?
Answers:
How can you generate a Random Graph?
Start with n isolated vertices, Add successive edges between them at random
Give some examples of Real Graphs
Food webs, Electric power grids, Metabolite processing networks, Networks of brain neurons, Voter networks, Social influence networks, Co-occurrence networks, Networks of connected proteins
What are some properties of Small World Networks?
"Properties of small-world networks
Small-world networks tend to contain cliques, and near-cliques, meaning sub-networks which have connections between almost any two nodes within them. This follows from the defining property of a high clustering coefficient. Secondly, most pairs of nodes will be connected by at least one short path. This follows from the defining property that the mean-shortest path length be small. Several other properties are often associated with small-world networks. Typically there is an over-abundance of hubs – nodes in the network with a high number of connections (known as high degree nodes). These hubs serve as the common connections mediating the short path lengths between other edges. By analogy, the small-world network of airline flights has a small mean-path length"
Reference: https://en.wikipedia.org/wiki/Small-world_network#Examples_of_small-world_networks
Can you give examples of Non Small World Networks?
Ans: Check: Reference: https://en.wikipedia.org/wiki/Small-world_network#Examples_of_small-world_networks
What is power law in statistics?
"In statistics, a power law is a functional relationship between two quantities, where a relative change in one quantity results in a proportional relative change in the other quantity, independent of the initial size of those quantities: "
https://en.wikipedia.org/wiki/Power_law#Power-law_probability_distributions
Can you name some Random Graph Generators?
Erdős–Rényi model, Watts–Strogatz model, Barabási–Albert (BA) model
When a Graph is generated using the probability approach - what is the order of the maximum size graph? Check answer
n to the power 2/3
For Watts–Strogatz model, if the desired Node count is N, then what will be the output edge count? Ans: NK/2
Watts–Strogatz model
K = mean degree = an even number
B = a special parameter
N >> K >> ln(K) >> 1
Check degree distribution for Watts–Strogatz model at: https://en.wikipedia.org/wiki/Watts%E2%80%93Strogatz_model
"The degree distribution in the case of the ring lattice is just a Dirac delta function centered at {\displaystyle K}K. The degree distribution for {\displaystyle 0<\beta <1}0<\beta <1 can be written as:
Resources:
Graph mining - lesson 1: Introduction to graphs and networks
http://www.nathalievialaneix.eu/teaching/m2se/M2SE-network_1.pdf
Erdős–Rényi model
https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model
Random Graphs
https://en.wikipedia.org/wiki/Random_graph
Examples of small-world networks
https://en.wikipedia.org/wiki/Small-world_network#Examples_of_small-world_networks
Case Study: Small World Phenomenon
https://introcs.cs.princeton.edu/java/45graph/
Random Graphs: Model of Social Networks
http://www.pnas.org/content/99/suppl_1/2566
Power Law Distribution
https://en.wikipedia.org/wiki/Power_law#Power-law_probability_distributions
Poisson distribution
https://en.wikipedia.org/wiki/Poisson_distribution
Watts–Strogatz model
https://en.wikipedia.org/wiki/Watts%E2%80%93Strogatz_model
Dirac delta function
Everywhere it is zero except at zero
https://en.wikipedia.org/wiki/Dirac_delta_function
Barabási–Albert (BA):
https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model#Degree_distribution
Random Graph Generators in Python Libraries
https://networkx.github.io/documentation/networkx-1.10/reference/generators.html
Random Graph Generators in R Libraries
https://rpubs.com/lgadar/generate-graphs
By
Sayed Ahmed
Linkedin: https://ca.linkedin.com/in/sayedjustetc
Blog: http://Bangla.SaLearningSchool.com, http://SitesTree.com
Online and Offline Training: http://Training.SitesTree.com
Affiliate Links:
Hottest Deals on Amazon USA: http://tiny.cc/38lddz
Hottest Deals on Amazon CA: http://tiny.cc/bgnddz
Hottest Deals on Amazon Europe: http://tiny.cc/w4nddz
