23

Where can I find graphs relevant to real-life problems?

Two repositories I know of are:

Yaroslav Bulatov
  • 4,701
  • 1
  • 25
  • 39
  • 1
    A similar question: Data for testing graph algorithms. – Sadeq Dousti Dec 01 '10 at 01:22
  • similar, I think synthetically generated graphs should go there – Yaroslav Bulatov Dec 01 '10 at 05:16
  • 1
    Nitpick: It should be Bodlaender. – gphilip Dec 01 '10 at 20:18
  • 1
    There are some large graphs from real-life, in DIMACS Benchmarks for Shortest Path Problem: http://www.dis.uniroma1.it/~challenge9/download.shtml#benchmark – Arman Feb 23 '11 at 21:17
  • 2
    You might find the answers to this question useful: http://cstheory.stackexchange.com/questions/3409/graphs-from-real-life-problems – Aaron Sterling Feb 23 '11 at 22:24
  • @Fixee, it seems to me that this is an exact duplicate of the question linked by Aaron Sterling. (if you want smaller graphs than those mentioned in that question then use their subgraphs of suitable size.) I vote (virtually) to close as exact duplicate. – Kaveh Feb 24 '11 at 06:27
  • @Kaveh: My question asks for a graph derived from a source familiar to students (so that the topic might pull them in). The graphs referenced by Aaron's link are the usual kinds of abstract graphs that I was trying to avoid. – Fixee Feb 25 '11 at 01:34
  • @Fixee, the title of his question is "graphs from real-life problems", the question is not looking for abstract examples, so it seems to me that the questions are the same and the answers should be in one place not separated between different questions. – Kaveh Feb 25 '11 at 02:42
  • @Kaveh: I deliberately chose not to put "Large graphs that resonate with the 20-something crowd" in the title because it seems a bit ungainly. Maybe I should have asked more specifically for "graphs based on social media" but I didn't want to restrict to that domain. In any event, I got an excellent answer so I'm quite happy. I'll let the mods decide if they want to close/merge/kill the question from here. Cheers. – Fixee Feb 25 '11 at 03:26
  • @Fixee, answers to the question you have asked is also answer to the question link above and the question are close enough, the more general question would include the answers to your intended unasked question (i.e. resonating with students), so I don't see any reason to have answers get divided between two question. Merging answer of this question with the other question and closing this question will not kill it, your question will still be here (and can be upvoted), but if a user wants to add a new answer, they have to post it under the other question which will be linked from your question – Kaveh Feb 25 '11 at 03:57
  • it is better to have the answers in one place to avoid repetition. (See this post for more information about merging.) – Kaveh Feb 25 '11 at 04:00
  • Moderator notice: Note: the comment above are moved from this question as a result of merging: Large real-world graphs for teaching use? – Kaveh Feb 25 '11 at 04:11

8 Answers8

13

The UCI Network Data Repository has a collection of social networks, with additional attributes (not just vertices and edges). They also have a set of links to similar collections elsewhere.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
8

I found the following two sources useful to analyze my betweenness centrality algorithms. These are more biased towards being "social". You will find more data by searching "protein interaction networks" on google.

Shiva Kintali
  • 10,578
  • 41
  • 74
5

Information related to test problems for the Traveling Salesman Problem (TSP) can be found here:

http://www.tsp.gatech.edu/data/index.html

Joseph Malkevitch
  • 1,319
  • 6
  • 7
5

There are some real benchmark instances for Frequency Assignment problem on: http://fap.zib.de/problems/

Arman
  • 934
  • 8
  • 14
5

The comments have some good data sets. There's also some Facebook data here.

SNAP has some interesting data

mhadley
  • 295
  • 2
  • 7
5

You might try checking this page on data sets from the "International network for social network analysis":

http://www.insna.org/software/data.html

If you have access to either "Networks, Crowds, and Markets" (Easley and Kleinberg, 2010) or "Social and Economic Networks" (Jackson, 2008), they're both full of references to datasets in the literature.

Edit: You can find a pre-publication draft of Networks, Crowds, and Markets at:

http://www.cs.cornell.edu/home/kleinber/networks-book/

Chapter 2 contains a section called "Network Datasets" that might give you some ideas.

Dan
  • 51
  • 1
  • 2
2
Marcus Ritt
  • 1,450
  • 14
  • 21
1

467 million Twitter posts from 20 million users covering a 7 month period from June 1 2009 to December 31 2009:

http://snap.stanford.edu/data/twitter7.html