Graph Mining – 002: SMALL WORLD GRAPHS & RANDOM GRAPH GENERATORS<\/p>\n
Graph Mining: SMALL WORLD GRAPHS & RANDOM GRAPH GENERATORS: Learn by finding answers to the following questions.<\/p>\n
Can you answer the following?<\/p>\n
What is a Graph?<\/p>\n
Can you define graph formally?<\/p>\n
What are the components in a Graph?<\/p>\n
What are edges and nodes or vertices in a Graph?<\/p>\n
Can you provide examples of Graphs? in Areas such as Science, Engineering, Medical, Biology, Social Sciences, Internet Applications, Social Media?<\/p>\n
Can you draw a simple graph?<\/p>\n
What is a Random Graph?<\/p>\n
What do you use to answer questions about the properties of typical graphs?<\/p>\n
What is the purpose of a Random Graph?<\/p>\n
What types of graphs you use to answer questions about the properties of typical graphs?<\/p>\n
How can you generate a Random Graph?<\/p>\n
What is known as Small World Properties for Graphs?<\/p>\n
Give some examples of Real Graphs<\/p>\n
What is the connection between Real Graphs and Small World Properties?<\/p>\n
What are some properties of Small World Networks?<\/p>\n
Can you give examples of Non Small World Networks?<\/p>\n
For small World Graphs – what will be the average path lengths (count of vertices) – a large number of a small number?<\/p>\n
Are small world graphs sparse or dense?<\/p>\n
What is power law distribution? How does that related to Small World Graphs?<\/p>\n
How can you relate Power Law Distribution to Github network?<\/p>\n
What is power law in statistics?<\/p>\n
Can you name some Random Graph Generators? What is the purpose? What will they do actually in general? Why will you use these generators.<\/p>\n
When edges are created between vertices with probability p : what is this mode of generation called? Is it a Random Graph? Why?<\/p>\n
What happens when p = probability is closer to 0? what when p is closer to 1?<\/p>\n
What is weight in a random graph Generator for example in the above case?<\/p>\n
When a Graph is generated using the probability approach – what is the order of the maximum size graph?<\/p>\n
Can you represent the graph generated above as G(n, p)? n = number of vertices, p = probability<\/p>\n
For the above case, what happens when np < 1 ?<\/p>\n
For the above case, what happens when np = 1 ? Can np be > 1?<\/p>\n
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<\/p>\n
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?<\/p>\n
For Erdos Renyi, is the average path length short?<\/p>\n
For Erdos Renyi, do they exhibit local clustering?<\/p>\n
Is local clustering a property of small world graphs?<\/p>\n
For Erdos Renyi, does it show Skewed degree distribution i.e. skewed power law distribution?<\/p>\n
For Erdos Renyi, does it show poission distribution?<\/p>\n
What is poission distribution? anyway?<\/p>\n
Can you relate poission distribution to Banks or a Diagnostic Center?<\/p>\n
What is Watts\u2013Strogatz model for Random Graph Generation? How does it work?<\/p>\n
Does Watts\u2013Strogatz model create a directed graph or an undirected graph?<\/p>\n
For Watts\u2013Strogatz 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.<\/p>\n
For Watts\u2013Strogatz, is the average path length short?<\/p>\n
For Watts\u2013Strogatz, do they exhibit local clustering?<\/p>\n
Is local clustering a propery of small world graphs?<\/p>\n
For Watts\u2013Strogatz, does it show Skewed degree distribution i.e. skeweed power law distribution?<\/p>\n
For Watts\u2013Strogatz, does it show poission distribution?<\/p>\n
how does Watts\u2013Strogatz relate to Dirac Delta Function?<\/p>\n
what is Barab\u00e1si\u2013Albert (BA) model? Is it the name of a Random Graph Generator or the name of a small world property or a statistical law?<\/p>\n
How does Barab\u00e1si\u2013Albert (BA) model work? i.e. the steps i.e. the methods<\/p>\n
For Barab\u00e1si\u2013Albert (BA) model, how is a new node added?<\/p>\n
For Barab\u00e1si\u2013Albert (BA) model, does it start with an empty graph or with an already connected graph?<\/p>\n
For Barab\u00e1si\u2013Albert (BA) model, how a new node is connected to an existing node? What does it depend upon? How does a probability play a role?<\/p>\n
For Barab\u00e1si\u2013Albert (BA) model, which nodes will accumulate more links quickly?<\/p>\n
For Barab\u00e1si\u2013Albert (BA) model, which nodes will starve for new links?<\/p>\n
For Barab\u00e1si\u2013Albert (BA) model, is the average path length short?<\/p>\n
For Barab\u00e1si\u2013Albert (BA) model, do they exhibit local clustering?<\/p>\n
For Barab\u00e1si\u2013Albert (BA) model, does it show Skewed degree distribution i.e. skeweed power law distribution?<\/p>\n
Answers:<\/strong><\/p>\n How can you generate a Random Graph? Give some examples of Real Graphs What are some properties of Small World Networks? Can you give examples of Non Small World Networks? What is power law in statistics? Can you name some Random Graph Generators? When a Graph is generated using the probability approach – what is the order of the maximum size graph? Check answer For Watts\u2013Strogatz model, if the desired Node count is N, then what will be the output edge count? Ans: NK\/2<\/p>\n Watts\u2013Strogatz model Check degree distribution for Watts\u2013Strogatz model at: https:\/\/en.wikipedia.org\/wiki\/Watts%E2%80%93Strogatz_model<\/a> Resources:<\/strong> Erd\u0151s\u2013R\u00e9nyi model Random Graphs Examples of small-world networks Case Study: Small World Phenomenon Random Graphs: Model of Social Networks Power Law Distribution Poisson distribution Watts\u2013Strogatz model Dirac delta function Barab\u00e1si\u2013Albert (BA): Random Graph Generators in Python Libraries Random Graph Generators in R Libraries By Linkedin<\/strong>: https:\/\/ca.linkedin.com\/in\/sayedjustetc<\/a><\/p>\n Blog<\/strong>: http:\/\/Bangla.SaLearningSchool.com<\/a>, http:\/\/SitesTree.com<\/a> Affiliate Links:<\/strong> Hottest Deals on Amazon CA: http:\/\/tiny.cc\/bgnddz<\/a><\/p>\n
\nStart with n isolated vertices, Add successive edges between them at random<\/p>\n
\nFood webs, Electric power grids, Metabolite processing networks, Networks of brain neurons, Voter networks, Social influence networks, Co-occurrence networks, Networks of connected proteins<\/p>\n
\n"Properties of small-world networks
\nSmall-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 \u2013 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"
\nReference: https:\/\/en.wikipedia.org\/wiki\/Small-world_network#Examples_of_small-world_networks<\/a><\/p>\n
\nAns: Check: Reference: https:\/\/en.wikipedia.org\/wiki\/Small-world_network#Examples_of_small-world_networks<\/a><\/p>\n
\n"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: "
\nhttps:\/\/en.wikipedia.org\/wiki\/Power_law#Power-law_probability_distributions<\/a><\/p>\n
\nErd\u0151s\u2013R\u00e9nyi model, Watts\u2013Strogatz model, Barab\u00e1si\u2013Albert (BA) model<\/p>\n
\nn to the power 2\/3<\/p>\n
\nK = mean degree = an even number
\nB = a special parameter
\nN >> K >> ln(K) >> 1<\/p>\n
\n"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:<\/p>\n
\nGraph mining – lesson 1: Introduction to graphs and networks
\nhttp:\/\/www.nathalievialaneix.eu\/teaching\/m2se\/M2SE-network_1.pdf<\/a><\/p>\n
\nhttps:\/\/en.wikipedia.org\/wiki\/Erd%C5%91s%E2%80%93R%C3%A9nyi_model<\/a><\/p>\n
\nhttps:\/\/en.wikipedia.org\/wiki\/Random_graph<\/a><\/p>\n
\nhttps:\/\/en.wikipedia.org\/wiki\/Small-world_network#Examples_of_small-world_networks<\/a><\/p>\n
\nhttps:\/\/introcs.cs.princeton.edu\/java\/45graph\/<\/a><\/p>\n
\nhttp:\/\/www.pnas.org\/content\/99\/suppl_1\/2566<\/a><\/p>\n
\nhttps:\/\/en.wikipedia.org\/wiki\/Power_law#Power-law_probability_distributions<\/a><\/p>\n
\nhttps:\/\/en.wikipedia.org\/wiki\/Poisson_distribution<\/a><\/p>\n
\nhttps:\/\/en.wikipedia.org\/wiki\/Watts%E2%80%93Strogatz_model<\/a><\/p>\n
\nEverywhere it is zero except at zero
\nhttps:\/\/en.wikipedia.org\/wiki\/Dirac_delta_function<\/a><\/p>\n
\nhttps:\/\/en.wikipedia.org\/wiki\/Barab%C3%A1si%E2%80%93Albert_model#Degree_distribution<\/a><\/p>\n
\nhttps:\/\/networkx.github.io\/documentation\/networkx-1.10\/reference\/generators.html<\/a><\/p>\n
\nhttps:\/\/rpubs.com\/lgadar\/generate-graphs<\/a><\/p>\n
\nSayed Ahmed<\/strong><\/p>\n
\nOnline and Offline Training<\/strong>: http:\/\/Training.SitesTree.com<\/a><\/p>\n
\nHottest Deals on Amazon USA: http:\/\/tiny.cc\/38lddz<\/a><\/p>\n