15
$\begingroup$

Consider the graph $G$ whose vertices are MO questions and edges are links between the questions. What does $G$ look like?

I'm happy to define a "link" in the same way the SE software seems to -- if a hyperlink to Question A is written anywhere in the text of Question B or its answers, or the comments to either Question B or its answers, then Question A will pop up in the "Linked Questions" sidebar on Question B, and also Question B will pop up in the "Linked Questions" sidebar on Question A (the graph is undirected).

  • $G$ is very far from connected. It has many nodes (perhaps the majority?) with no edges at all.

  • What is the largest connected component of $G$? Are the component sizes distributed according to a power law or something?

  • What is the maximum degree of a node in $G$? How are the degrees of nodes distributed?

  • How does this graph structure compare to the tag structure or the user structure (I'm not sure of the best way to make this question precise)?

  • What happens if we add to $G$ nodes for arxiv preprints or journal articles and links from MO questions to them?

I think that studying the structure of $G$ will not shed as much light on the structure of MO as, say, studying the link structure of the Internet as a whole sheds on the Internet, since links as defined here are not the only way questions can be related. But it still seems interesting.

Probably these sorts of questions have been considered thoroughly by the developers at SE, as the structure of $G$ is presumably an important ingredient in generating the "Related Questions" sidebar.

$\endgroup$
3
11
$\begingroup$

I can answer this part of the question with the Stack Exchange Data Explorer.

What is the maximum degree of a node in $G$? How are the degrees of nodes distributed?

This query shows a list of questions with the most links.

Here is a graph showing the distribution (NOTE: the y-axis is logarithmic):

enter image description here

Please note that SEDE is updated once a week, on Sunday morning.


as the structure of $G$ is presumably an important ingredient in generating the "Related Questions" sidebar.

No, that would be nice but it isn't. It's based on a similarity algorithm in Elastic, the 'database' powering Stack Exchange search. See How are "related" questions selected? for more information.

$\endgroup$
4
  • $\begingroup$ I see that the query uses UNION to solve the problem that the PostLinks table is not symmetric (+1). $\endgroup$ – Martin Sleziak Feb 16 at 12:54
  • $\begingroup$ I just wanted to check whether I understand correctly understand the PostLinks table - it contains only the questions shown as the linked posts, not all links, right? Linked questions can be missing for various reasons, in the case of MO this is likely the case for many posts before 2013. $\endgroup$ – Martin Sleziak Feb 16 at 12:56
  • $\begingroup$ @MartinSleziak I remember I had to ask rene why my cross-site query with UNION did not work as expected. It turns out I needed UNION ALL ... And your observation about old linked posts is correct. I'm pretty sure that's not doable without scraping the website / API and extract all the links. $\endgroup$ – Glorfindel Feb 16 at 13:01
  • 1
    $\begingroup$ All roads lead to polymath, it seems. But that just might be a common false belief. In either case, that seems like an open problem that is easy to explain, and solving it would involve important formulas from combinatorics. $\endgroup$ – Asaf Karagila Feb 16 at 19:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .