HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Create a random graph based on the Degree Distribution and Clustering Coefficient Distribution

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
randomdegreethegraphcreatecoefficientbasedanddistributionclustering

Problem

I am currently working with a very large Social Network and I want to recreate this graph with a smaller dimension, using the original Degree Distribution and Clustering Coefficient Distribution.

The degree distribution is the relative frequency of vertexes in the original graph that have a certain degree.

The clustering coefficient distribution is the relative frequency for each vertex degree of two neighbours (of a vertex with that degree) to have a link between them.

Does anybody know any literature and algorithm to do this? The stuff I have found was always very theoretical..

Thanks!

Solution

You may want to have a look at the block two-level Erdos-Renyi model (BTER). The usual preferential attachment mechanism for generating scale-free networks doesn't capture the clustering coefficient right, and small-world networks aren't scale-free; the BTER model can capture both scale-free and clustering behavior. I think they have some way to make it work for an arbitrary degree distribution (not just scale-free). The link I gave above has code for generating BTER graphs too.

Context

StackExchange Computer Science Q#26148, answer score: 3

Revisions (0)

No revisions yet.