5 ms·

This essay feels like an instant classic. It's a very thoughtful blend of prose and code, in service of teaching some wildly relevant lessons about networks. O

This essay feels like an instant classic. It's a very thoughtful blend of prose and code, in service of teaching some wildly relevant lessons about networks. One eye opener is the extent that the "Degree" parameter reduces the critical threshold. > The degree of a node is the number of neighbors it has. Up to this point, we’ve been looking at networks of degree 4. But what happens when we vary this parameter? And here's the power of this interactive essay, you can try it yourself. It's a toy model but makes a visceral argument. It adds up to the kind of media we dreamed of for the world wide web. The degree parameter has exploded via social networks, greatly lowering the critical threshold of idea transmission. Our cultural DNA is being revised at a supercritical pace. This piece helps make a little sense of it in a way that static words couldn't.

atemerev 7y ago
Real networks are not lattices; they have varied degree distributions. The famous result of Marián Boguña and Alessandro Vespignani shows, that for scale-free networks (which closely resemble the networks we see in the real world), the epidemic threshold could be arbitrarily low: https://arxiv.org/pdf/cond-mat/0208163.pdf https://arxiv.org/pdf/cond-mat/0208163.pdf. I have also published some research among these lines: https://arxiv.org/pdf/1403.5815.pdf https://arxiv.org/pdf/1403.5815.pdf
- antt 7y ago
  Real social networks aren't even networks, they are simplexes.
  - swsieber 7y ago
    Ok. I don't know the word simplex, but after brief googling, it looks like simplexes are a type of network. Could you explain what you mean a little bit more?
  - arcticfox 7y ago
    Why are they simplexes? I'm reading about simplexes, and having a hard time visualizing how they map to social networks
    - antt 7y ago
      The hyper volumes between vertices can have single weights. Say you have a pump that is contaminated with cholera. You can either model the pump as a node on the graph with every person drinking from it being connected by an edge, allow an arbitrary number of edges between any two nodes, or allow for a relationship that can connect an arbitrary number of nodes. I built a rather sophisticated simplex based trade analyser for one of my contracts for a broker trader. From what I've heard it's given them an edge since no one even knows about it. It's been three years so my NDA and non-compete are finished. I might get around to writing it up if I don't get hired to do another one.
      - wnkrshm 7y ago
        With hypervolumes you mean all the (n-1)-dimensional 'faces' (n > 1) formed by a vertex and its neighbours in an n-dimensional simplex or a mesh of those? To assign unique weights to all interactions between a vertex and up to n-1 of its neighbours, I assume.
        antt 7y ago
        Yeah. And because they are sparse the representation is both tiny and stupidly powerful.
        kian 7y ago
        Would you care to share some pointers to materials where one could learn about simplicial representations of things traditionally modeled by networks?
        antt 7y ago
        There aren't any I could find, I had to do everything from first principles and the notebooks were left with my employer.
  - kmill 7y ago
    Maybe you mean something like a simplicial complex? I don't understand how you can do very much with a single simplex (which is a generalization of a triangle and a tetrahedron in the language I'm used to).
    - therein 7y ago
      I think he is talking about a simplex tree.
  - dredmorbius 7y ago
    Your comment informs little. Do you mean that real social networks are to networks as tensors are to vectors? More dimensions? If so, what do those dimensions represent? Or am I missing your point (which is ... not very clearly made).
paob 7y ago
Regarding the importance of the degree distribution, we have pretty solid theoretical results on how it's actually the spectrum of the adjacency matrix which acts as a global metric for how well epidemics spread. I always like to recommend Ganesh et al.'s article [1] for how we came to understand this phenomenon but also Prakash et al.'s paper [2] for their theorem which holds for a very large class of epidemic models. What's pretty interesting is that the largest eigenvalue of the adjacency matrix of an undirected graph lies between the average degree and the maximum degree so the gut feeling you get when playing with the degree of a graph is legitimate. I will jump on the opportunity do shamelessly self-plug our most recent work [3] on how to modify the topology of a network to have the epidemic go subcritical and quickly disappear. The basic idea in our paper is to keep the maximum number of edges from the original graph under the constraint that the adjacency spectrum is bounded. Since that's a NP-hard problem we go for an approximation algorithm. In any case, Melting Asphalt's essays are really an example to follow! A gold standard for expository material! [1] Ganesh et al. https://ieeexplore.ieee.org/abstract/document/1498374 https://ieeexplore.ieee.org/abstract/document/1498374 [2] Prakash et al. https://link.springer.com/article/10.1007/s10115-012-0520-y https://link.springer.com/article/10.1007/s10115-012-0520-y [3] Bazgan et al. https://link.springer.com/chapter/10.1007/978-3-030-04651-4_8 https://link.springer.com/chapter/10.1007/978-3-030-04651-4_...

atemerev 7y ago

Real networks are not lattices; they have varied degree distributions. The famous result of Marián Boguña and Alessandro Vespignani shows, that for scale-free networks (which closely resemble the networks we see in the real world), the epidemic threshold could be arbitrarily low: https://arxiv.org/pdf/cond-mat/0208163.pdf https://arxiv.org/pdf/cond-mat/0208163.pdf. I have also published some research among these lines: https://arxiv.org/pdf/1403.5815.pdf https://arxiv.org/pdf/1403.5815.pdf

antt 7y ago
Real social networks aren't even networks, they are simplexes.
- swsieber 7y ago
  Ok. I don't know the word simplex, but after brief googling, it looks like simplexes are a type of network. Could you explain what you mean a little bit more?
- arcticfox 7y ago
  Why are they simplexes? I'm reading about simplexes, and having a hard time visualizing how they map to social networks
  - antt 7y ago
    The hyper volumes between vertices can have single weights. Say you have a pump that is contaminated with cholera. You can either model the pump as a node on the graph with every person drinking from it being connected by an edge, allow an arbitrary number of edges between any two nodes, or allow for a relationship that can connect an arbitrary number of nodes. I built a rather sophisticated simplex based trade analyser for one of my contracts for a broker trader. From what I've heard it's given them an edge since no one even knows about it. It's been three years so my NDA and non-compete are finished. I might get around to writing it up if I don't get hired to do another one.
    - wnkrshm 7y ago
      With hypervolumes you mean all the (n-1)-dimensional 'faces' (n > 1) formed by a vertex and its neighbours in an n-dimensional simplex or a mesh of those? To assign unique weights to all interactions between a vertex and up to n-1 of its neighbours, I assume.
      - antt 7y ago
        Yeah. And because they are sparse the representation is both tiny and stupidly powerful.
        kian 7y ago
        Would you care to share some pointers to materials where one could learn about simplicial representations of things traditionally modeled by networks?
        antt 7y ago
        There aren't any I could find, I had to do everything from first principles and the notebooks were left with my employer.
- kmill 7y ago
  Maybe you mean something like a simplicial complex? I don't understand how you can do very much with a single simplex (which is a generalization of a triangle and a tetrahedron in the language I'm used to).
  - therein 7y ago
    I think he is talking about a simplex tree.
- dredmorbius 7y ago
  Your comment informs little. Do you mean that real social networks are to networks as tensors are to vectors? More dimensions? If so, what do those dimensions represent? Or am I missing your point (which is ... not very clearly made).

paob 7y ago

Regarding the importance of the degree distribution, we have pretty solid theoretical results on how it's actually the spectrum of the adjacency matrix which acts as a global metric for how well epidemics spread. I always like to recommend Ganesh et al.'s article [1] for how we came to understand this phenomenon but also Prakash et al.'s paper [2] for their theorem which holds for a very large class of epidemic models. What's pretty interesting is that the largest eigenvalue of the adjacency matrix of an undirected graph lies between the average degree and the maximum degree so the gut feeling you get when playing with the degree of a graph is legitimate. I will jump on the opportunity do shamelessly self-plug our most recent work [3] on how to modify the topology of a network to have the epidemic go subcritical and quickly disappear. The basic idea in our paper is to keep the maximum number of edges from the original graph under the constraint that the adjacency spectrum is bounded. Since that's a NP-hard problem we go for an approximation algorithm. In any case, Melting Asphalt's essays are really an example to follow! A gold standard for expository material! [1] Ganesh et al. https://ieeexplore.ieee.org/abstract/document/1498374 https://ieeexplore.ieee.org/abstract/document/1498374 [2] Prakash et al. https://link.springer.com/article/10.1007/s10115-012-0520-y https://link.springer.com/article/10.1007/s10115-012-0520-y [3] Bazgan et al. https://link.springer.com/chapter/10.1007/978-3-030-04651-4_8 https://link.springer.com/chapter/10.1007/978-3-030-04651-4_...