Graph Mining – 1 | 03. Small World Networks and Random Graphs — Part 2 (Q&A)

AI Generated Answers. The questions originated on this blog and are attributed to Sayed Ahmed. New AI-generated explanatory content and original examples are provided for reuse without copyright restrictions asserted by this blog. Check sources and code before use; third-party materials have their own licenses.

Course index: Graph Mining – 1. Original questions: Small World Graphs & Random Graph Generators. This part covers questions 03.20–03.38.

Q03.20. How can you relate Power Law Distribution to Github network?

Answer. On GitHub, a graph might link contributors to repositories (bipartite), users to followers, or repositories to dependencies. Some degree distributions may be heavy-tailed due to popular repositories, but this must be measured and fitted; GitHub as a whole is not automatically a single power-law network.

Q03.21. What is power law in statistics?

Answer. In statistics, a power law describes a variable whose probability or frequency scales as a negative exponent over a range: f(x) ∝ x^(−α). Verify a proposed power law against alternatives such as lognormal distributions; a straight line on a log-log plot alone is insufficient.

Q03.22. Can you name some Random Graph Generators? What is the purpose? What will they do actually in general? Why will you use these generators.

Answer. Generators include Erdős–Rényi, Watts–Strogatz, Barabási–Albert, random geometric graphs, and stochastic block models. They sample synthetic networks to test hypotheses, algorithms, and structural expectations, with controllable n, density, or community structure.

Q03.23. When edges are created between vertices with probability p : what is this mode of generation called? Is it a Random Graph? Why?

Answer. That is the G(n,p) Erdős–Rényi independent-edge model. Every possible edge is a Bernoulli trial with probability p. The result is random even if n and p stay the same.

Q03.24. What happens when p = probability is closer to 0? what when p is closer to 1?

Answer. At p near 0, graphs are usually sparse with many isolated vertices. At p near 1, almost every pair is connected and the graph approaches a complete graph. These are tendencies, not claims about every sample.

Q03.25. What is weight in a random graph Generator for example in the above case?

Answer. Probability p controls edge existence, not numerical weight. A basic G(n,p) graph is unweighted. To create weighted random graphs, sample an additional weight for each realized edge from a specified distribution.

Q03.26. When a Graph is generated using the probability approach – what is the order of the maximum size graph?

Answer. For n vertices, at most n(n−1)/2 undirected edges exist in a simple graph, so maximum E is Θ(n²). Its adjacency matrix contains n² entries. The expected edge count in G(n,p) is p·n(n−1)/2.

Q03.27. Can you represent the graph generated above as G(n, p)? n = number of vertices, p = probability

Answer. Yes: G(n,p) denotes the random graph distribution with n labeled vertices and each undirected edge included independently with probability p, 0≤p≤1.

Q03.28. For the above case, what happens when np < 1 ?

Answer. For sparse Erdős–Rényi graphs with p≈c/n and c=np<1 fixed, the graph is subcritical. With high probability all connected components are small, and the largest typically has size O(log n).

Q03.29. For the above case, what happens when np = 1 ? Can np be > 1?

Answer. At c=np≈1, the model approaches the critical threshold; the largest component has order n^(2/3). Yes, np can exceed 1: for c>1, a giant component containing a positive fraction of the vertices emerges in the large-n limit.

Q03.30. 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

Answer. In the classical subcritical regime p=c/n with fixed c<1, the largest component has order O(log n) with high probability. It is also o(n). Critical c=1 is different: size is of order n^(2/3), not O(log n).

Q03.31. 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?

Answer. Erdős–Rényi refers to mathematicians Paul Erdős and Alfréd Rényi and to random-graph models such as G(n,p); it is a model family, not a small-world property or a probability law named after a single scalar.

Q03.32. For Erdos Renyi, is the average path length short?

Answer. For sufficiently connected, nontrivial sparse ER graphs above the giant-component threshold, typical distances within the giant component are on the order of log n. But below threshold many pairs are disconnected; do not report one average path length over all pairs without specifying a component.

Q03.33. For Erdos Renyi, do they exhibit local clustering?

Answer. ER graphs generally have low clustering when p is small: expected local clustering is approximately p. Unlike Watts–Strogatz, they do not preserve tight local neighborhoods.

Q03.34. Is local clustering a property of small world graphs?

Answer. Yes. A standard small-world criterion compares clustering to a comparable random network and expects distinctly higher local clustering while paths remain short.

Q03.35. For Erdos Renyi, does it show Skewed degree distribution i.e. skewed power law distribution?

Answer. No in the standard sparse ER model. Degrees are approximately Poisson for fixed average degree, not a heavy-tailed power law. A finite sample can still show some variation.

Q03.36. For Erdos Renyi, does it show poission distribution?

Answer. Approximately yes in the sparse regime p≈c/n: degrees follow Binomial(n−1,p), approaching Poisson(c) as n grows. For arbitrary p, the exact distribution remains binomial, so do not always claim Poisson.

Q03.37. What is poission distribution? anyway?

Answer. The Poisson distribution models nonnegative event counts with rate λ: P(X=k)=e^(−λ)·λ^k/k!. Its mean and variance both equal λ. It can approximate binomial rare-event counts or arrivals under particular assumptions.

Q03.38. Can you relate poission distribution to Banks or a Diagnostic Center?

Answer. Examples: number of calls arriving at a bank desk during a fixed interval or number of lab samples arriving per hour, when independent events occur at a roughly constant rate. Actual service queues may violate independence or constant-rate assumptions.

Worked calculation: G(n,p)

For n=100 vertices and p=0.02, expected edges = 0.02×100×99/2 = 99. Expected degree = 99×0.02 = 1.98. These are expectations, not exact outcomes of each random draw. A random sample may have fewer or more edges.

Leave a Reply