The Erdos graph for TeX.SE

Question

In the Erdös graph for TeX.SE two people are connected if they have contributed to (asked or answered or commented on or edited) the same question.

What does this graph look like?

Are the data available in a form that makes an answer possible?

Question prompted by the blog entry at http://tex.blogoverflow.com/2013/07/a-new-milestone/?cb=1 : egreg =? Erdös

See http://www.oakland.edu/enp/

Edit towards an answer, prompted by the comments.

The Erdos graph is a way to represent TeX.SE as a social network, so what's relevant are the connections between people that occur when they think about the same question, not the connections between questions and people. (That might be an interesting bipartite graph for another day.)

If the average number of answers per question is A then each question will generate (on average) A(A+1)/2 edges joining vertices (users) in the graph (counting self-answers, not counting comments or edits). This allows multiple edges between vertices (which happens frequently on TeX.SE).

There are about 43000 questions and about 32000 users. Since each edge joins two vertices (users) the average valence of a vertex (user) is about

2*(number of edges)/(number of vertices)

= A(A+1)(number of questions)/(number of users)

= A(A+1)*43,000/32,000

I'd guess that A is between 1 and 2, which implies an average valence between 3 and 8. Of course the distribution is far from uniform!

Whether or not to count comments or edits as creating a connection could be easily explored by tweaking the software that builds the graph input from the database.

A database query generating a 43,000 line csv file with one line for each question listing its asker and answerers would provide all the data needed to build the graph. Since I don't know SQL I can't follow up @texenthusiasts hope that a new query at http://data.stackexchange.com/tex/query/new might provide what's wanted.

Answer 1

Thanks for the pointer to the XML data dumps, @Charles Stewart. I used the June 2013 data dump (formerly here: http://www.clearbits.net/torrents/2141-jun-2013) and extracted the tex.se portion into a MongoDB database instance for easy querying. The dataset consisted of over 103K Post records and 27K User records. Every post has a type associated with it. The Post types we're interested in for this problem are "Question" and "Answer". There were over 40K Questions and 60K Answers in this dataset.

With these Question and Answer posts, a graph can be constructed, connecting two users from the dataset with an edge if those users contributed to the same question (by either posting the question or posting an answer to the question). This can be thought of as a co-authorship network. Once constructed, this co-authorship graph consisted of 13775 vertices and 67002 edges. For the sake of analysis, I only worked with the giant component (which I'll call "the graph" or "the network" from here onward). Some of the basic statistics of the graph are listed here:

• Number of Vertices: 13589
• Number of Edges: 66882
• Average Degree: 9.843
• Degree Assortativity Coeff.: -0.248
• Avg. Clustering Coeff.: 0.527
• Transitivity: 0.054

So Ethan's guess above was pretty close to the actual average degree for the network. The negative assortativity coefficient is interesting: in academic coauthorship networks (and other social networks), we usually see a positive assortativity measure, which indicates that network "hubs" tend to connect to other hubs (see http://prl.aps.org/abstract/PRL/v89/i20/e208701). The tex.se network exhibits the opposite tendancy: hubs tend to connect to "smaller" nodes. This property is probably desirable for this setting - it means that the more experienced TeX users in the community are interacting more often with the less experienced members, presumably helping to spread their knowledge throughout the community.

The Degree Distribution for the graph follows an approximately power-law distribution. Using the python power-law fitting package, a fit was obtained with alpha = 1.93 for minimum degree 4. The distribution looks like this:

We can also look at who the users with the highest degree are; the higher the degree of the user, the more posts the user has participated in as a "co-author". The top 20 users in the tex.se coauthorship network by degree are:

• egreg 2962
• Gonzalo Medina 2100
• Werner 2009
• David Carlisle 1784
• Herbert 1690
• lockstep 1207
• Peter Grill 1145
• Stefan Kottwitz 1140
• Martin Scharrer 1109
• Mico 944
• Joseph Wright 868
• Alan Munn 828
• Andrew Stacey 823
• Jake 805
• Marco Daniel 770
• Ulrike Fischer 766
• Yiannis Lazarides 764
• Harish Kumar 709
• Heiko Oberdiek 690
• percusse 678

For the sake of fancy visuals, the graph looks like this, although it's hard to draw much from this view (the nodes are colored and sized by degree, so the bigger and bluer a node is, the higher its degree):

I'm currently working on some more analysis, so helpfully a better "global view" of the tex.se network will be coming at some point in the near future, along with some other interesting findings. Thanks for reading, and thanks to Ethan for posting a fun question!

Answer 2

I don't think the Data Explorer (data.stackexchange.com) will help: you need the fixpoint of an operation over the graph and I don't think the query language supports that.

There are other options:

1. There is an API to query this content - https://stackapps.com/ - though hammering the API with recursive queries might get you in trouble, and
2. The whole database is periodically exported as some XML files at http://www.clearbits.net/creators/146-stack-exchange-data-dump (a huge file of all sites). I wrote some Lua code for reading these files - https://github.com/chalst/sxdatadump2lua - in principle this code should be faster at digesting the data than your unzip utility is at extracting it, but it has only been tested on small databases of discontinued sites. If you would rather not work with Lua, at least the code might help you understand the XML representation.