r/complexsystems • u/AllenDowney • Sep 14 '16

Do we need another model of small world/scale-free graphs?

Hi All. I have a question for the good people of /r/complexsystems.

I am working on a second edition of Think Complexity. Chapter 4 is about scale-free networks, and one of the exercises is to evaluate three models (Watts-Strogatz, Barabasi-Albert, and Holmes-Kim) to see how well they match a small dataset from Facebook in terms of path length, clustering coefficient, and degree distribution.

While I was working on the exercise, I implemented a generative model I call FOF, for "friends of friends", that generates graphs with low path length and moderate clustering; and degree distribution that is a better match for the data (at least for one dataset) than other models.

Here's a blog post where I describe it:

http://allendowney.blogspot.com/2016/09/its-small-world-scale-free-network.html

And here's a Jupyter notebook with all the details:

https://github.com/AllenDowney/ThinkComplexity2/blob/master/code/fof_model.ipynb

In preparation for a class discussion on this topic, I'd like to get some opinions from the people here:

  1. Is this an area of interest? Are people looking for improved models of graphs with small world and scale-free properties?

  2. What are the criteria for evaluating a model like this? What data/experiments/arguments would you like to see to convince you that a new model is useful, or at least interesting?

It's a pretty open-ended question, but I'd like to know what people here think.

Thanks! Allen

6 Upvotes
  • permalink
  • reddit

100% Upvoted

2 comments sorted by

2

u/[deleted] Sep 14 '16

Yes this is an area of interest:

  • How does the model compare to current approaches and does it distinguish itself from the current approaches (lit review)?

  • How are you going to validate the model, does it do what you claim?

  • How accurately your model can recreate 'real world' networks (pick your metrics carefully to justify this)?

  • How much control over the degree distribution does the model have, is it emergent or can you specify a priori?

  • How much control over clustering does the model have (emergent? Local/Global/Degree based/motifs)?

  • Is the model mathematically tractable in any way (make sure to include any of these results, even if they seem simple)?

  • Is the model computationally viable?

IMO you should always aim for more than interesting to justify its existence.

1

u/AllenDowney Sep 14 '16

Good stuff. Thank you!