File:Critical 1000-vertex Erdős–Rényi–Gilbert graph.svg
| Uploaded by | David Eppstein |
|---|---|
| Upload date | 2022-02-09T07:33:05Z |
| MIME type | image/svg+xml |
| Dimensions | 1000 × 1000 px |
| File size | 78.6 KB |
Summary
| Description |
English: An Erdős–Rényi–Gilbert random graph with 1000 vertices at the critical edge probability , showing the largest connected component in the center. |
| Date | |
| Source | Own work |
| Author | David Eppstein |
| SVG development |
Licensing
I, the copyright holder of this work, hereby publish it under the following license:
 
|
This file is made available under the Creative Commons CC0 1.0 Universal Public Domain Dedication. |
| The person who associated a work with this deed has dedicated the work to the public domain by waiving all of their rights to the work worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law. You can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission.
|
Source code
from PADS.SVG import *
from PADS.StrongConnectivity import *
from random import random
from sys import stdout
# ===================================================
# Generate a random graph and random layout
# ===================================================
n = 1000
vertices = range(n)
edgeprob = 1./(n-1)
halfG = {v : set(w for w in vertices if v<w and random() < edgeprob) for v in vertices}
G = {v : set(w for w in vertices if v in halfG[w] or w in halfG[v]) for v in vertices}
# ===================================================
# Pull giant component in and push all the rest out
# ===================================================
weight = {}
SCC = StronglyConnectedComponents(G)
giant = max(len(C) for C in SCC)
for C in StronglyConnectedComponents(G):
for v in C:
if len(C) == giant:
weight[v] = giant
else:
weight[v] = -1
# ===================================================
# Social gravity
# ===================================================
D = {v : (random()-0.5) + 1j* (random()-0.5) for v in vertices}
natlength = n**(-0.5)
iterations = 150
increment = 0.01
for i in range(iterations):
social = 0.25
forces = {v : -D[v]*social for v in vertices}
for v in vertices:
for w in vertices:
if v != w:
forces[v] += (natlength/abs(D[v]-D[w]))**2*(D[v]-D[w])
for v in vertices:
for w in G[v]:
forces[v] += abs(D[v]-D[w])*(D[w]-D[v])/natlength
for v in vertices:
D[v] += increment * forces[v]
# ===================================================
# Renormalize
# ===================================================
minx = min(D[v].real for v in vertices)
miny = min(D[v].imag for v in vertices)
offset = minx + 1j*miny
for v in vertices:
D[v] -= offset
maxx = max(D[v].real for v in vertices)
maxy = max(D[v].imag for v in vertices)
rescale = 1./max(maxx,maxy)
for v in vertices:
D[v] *= rescale
# ===================================================
# Turn layout into drawing
# ===================================================
scale = 1000
radius = 6
margin = 9
bbox = scale*(1+1j)
def place(v):
return D[v]*(scale-2*margin) + margin*(1+1j)
drawing = SVG(bbox,stdout)
drawing.group(style={"stroke":"#000","stroke-width":"2"})
for v in vertices:
for w in halfG[v]:
drawing.segment(place(v),place(w))
drawing.ungroup()
drawing.group(fill=colors.red,stroke=colors.black)
for v in vertices:
drawing.circle(place(v),radius)
drawing.ungroup()
drawing.close()