Popularity vs Similarity in Growing Networks¶

Background¶

Why are we interested in networks? Because a enormous categories of phenomena can be modeled using networks. Internet, society, physics, biology, ecology, economy, even the evolution of the universe are essentially networks.

Scaling in Networks¶

People have found a lot of scaling phenomena in networks.

arXiv:cond-mat/0008465 for the scaling in internet links. What they find is that the distribution of degrees is power-law, i.e., with . arXiv:cond-mat/0009090 provides a better explanation. The explanation is simply popular is more attractive.

• Barabasi et al found that in random networks, scaling appears also [2].

Scaling of connectivities. Barabasi (1999).

• And some theories like [3], etc.

Popularity¶

In the example of internet links, popular is attractive can be modeled by a dynamic generation of network following some rules.

1. At each step we have links distributed.

2. The probability of attaching to some node with degree is

where serves as an initial attractiveness since it tells us the probability of attachment when the degree .

Dorogovtsev et al proved that this model gives us the final distribution of degrees

where [1].

### Similarity

The problem about popularity is that we are all aware that popularity is not the only factor.

Consider the following examples.

1. You write a blog about neuroscience. In the past people usually put links on the blog, which is called blogroll or something. In the links, what you would include is something like facebook, google, maybe nature/science, and most likely some blogs or resources about neuroscience eventhough these websites may not be very popular. However, these links have similar contents as yours.
2. We could also check the link you used in your articles and they are very likely to point to some websites that is also neuroscience.

In some cases similar is also important.

Popularity and Similarity Together¶

What we would expect is that larger popularity and small similarity (more similar) are the preferable connections. Thus competitions between the two determines the overall connection probability.

To combine the two factors, we use the metric . Even though there is a competition between popularity and similarity, small values of are more preferable connections, which takes similarity more seriously.

A simple model to demonstrate this is to build a space of disc. The radius is time , while angles are the measure of similarity. A smaller angler distance indicates a smaller similarity. Using this mapping, we are able to show the dynamics of networks, since we can tell the history of the nodes.

Mathematically speaking, the similarity is measured as

System Message: WARNING/2 ($$\theta_{ij} = \lvert \theta_i - \theta_j \rvert.$$)

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.16 (TeX Live 2015/Debian) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2016/02/01> Babel <3.9q> and hyphenation patterns for 81 language(s) loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2014/09/29 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/utf8x.def)) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucs.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/data/uni-global.def)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the ?' option. (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amstext.sty (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsopn.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amscls/amsthm.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amssymb.sty (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amsfonts.sty)) (/usr/share/texlive/texmf-dist/tex/latex/anyfontsize/anyfontsize.sty) (/usr/share/texlive/texmf-dist/tex/latex/tools/bm.sty) (./math.aux) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucsencs.def) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.fd) ! LaTeX Error: Bad math environment delimiter. See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.16 \end{split} ! You can't use \eqno' in math mode. \endmathdisplay@a ...\df@tag \@empty \else \veqno \alt@tag \df@tag \fi \ifx ... l.16 \end{split} ! Missing \endgroup inserted. <inserted text> \endgroup l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! LaTeX Error: \begin{split} on input line 16 ended by . See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! Missing \cr inserted. <inserted text> \cr l.16 \end{split} ! Missing { inserted. <inserted text> { l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! Missing { inserted. <inserted text> { l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! LaTeX Error: \begin{equation*} on input line 13 ended by \end{split}. See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Misplaced alignment tab character &. \math@cr@@@ ->\ifst@rred \nonumber \fi & \relax \make@display@tag \ifst@rred ... l.16 \end{split} ! Misplaced \cr. \math@cr@@@ ...fi \global \advance \row@ \@ne \cr l.16 \end{split} ! Extra }, or forgotten $. \gmeasure@ ...savetaglength@ \crcr #1\math@cr@@@ } }\restorecounters@ \if@fle... l.16 \end{split} ! Extra }, or forgotten$. \gmeasure@ ...avetaglength@ \crcr #1\math@cr@@@ }} \restorecounters@ \if@fleq... l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Display math should end with $$. <to be read again> \endgroup l.16 \end{split} ! Package amsmath Error: \begin{split} won't work here. See the amsmath package documentation for explanation. Type H <return> for immediate help. ... l.16 \end{split} ! Missing number, treated as zero. <to be read again> \relax l.17 \end{equation*} ! Illegal unit of measure (pt inserted). <to be read again> \relax l.17 \end{equation*} ! Too many }'s. \endmathdisplay@a ...@ \totwidth@ \egroup \egroup l.17 \end{equation*} ! LaTeX Error: \begin{document} ended by \end{equation*}. See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.17 \end{equation*} ! Missing  inserted. <inserted text>  l.17 \end{equation*} ! Display math should end with$$. <to be read again> \endgroup l.17 \end{equation*} ! Extra \endgroup. <recently read> \endgroup l.17 \end{equation*} [1] (./math.aux) ) (see the transcript file for additional information) Output written on math.dvi (1 page, 428 bytes). Transcript written on math.log.

while time is the radius with at the center of the disc.

Disc of similarity. This figures shows the measure of similarity. 2 & 3 are more similar, given the fact that their angular distance is smaller that either or . Papadopoulos et al (2012).

Now we are going to dynamically generate a network. The updating rules are listed bellow.

1. We create a node at each time step and label them with numbers. For example, node 3 means it was created at time step 3. We denote the time of the th node as and its angle on the disc as .
2. As the node is created at time , it is connected to previous nodes.
3. The node is connected to node ’s if are the smallest. In this measure is the popularity of node and is the similarity of the two nodes.

Illustration of the disc model. The radial coordinate measure the creation time of the node, while the angular distance measures the similarity.

The key transformation of this problem is to define a new radial coordinate system , so that the distance becomes log scale. Then we define the disc to be on a hyperbolic space so that the distance between any two points is calculated as [4]

Minimizing becomes equivalent to minimizing when dealing with the connectivity from a new born node . The competition between popularity and similarity is simply the minimization of distance between two nodes on a hyperbolic plane.

Illustration of the disc model. The radial coordinate measure the creation time of the node, while the angular distance measures the similarity. The shaded region is the a region enclosed by a equal distance line. Papadopoulos et al (2012).

Why is this definition of distance far superior than the previous measure of ? Or why do I care? Because the universe/nature itself measures distance on hyperbolic space, i.e., Minkowski space. It also shows us the hint that by choosing a proper metric we might be able to define distance between any nodes in any systems. The only question becomes which geometry.

This result is astonishing also because a discrete system is most likely generated dynamically according to some laws. The method of mapping nodes to a hyperbolic space provides a convenient metric or distance for us to find out the closest nodes. In other words, a node always connect to it’s nearest neighbors if the metric/distance is well defined.

Variations and Emergent Models¶

In many real networks, early nodes are more popular. However, popularity decreasing with time can also be modeled. The idea is simple. We allow the nodes to drift away from the center along its own radial direction according to the restraint

System Message: WARNING/2 ($$r_{j}(t) = \beta r_j + (1-\beta) r_{i},$$)

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.16 (TeX Live 2015/Debian) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2016/02/01> Babel <3.9q> and hyphenation patterns for 81 language(s) loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2014/09/29 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/utf8x.def)) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucs.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/data/uni-global.def)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the ?' option. (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amstext.sty (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsopn.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amscls/amsthm.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amssymb.sty (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amsfonts.sty)) (/usr/share/texlive/texmf-dist/tex/latex/anyfontsize/anyfontsize.sty) (/usr/share/texlive/texmf-dist/tex/latex/tools/bm.sty) (./math.aux) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucsencs.def) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.fd) ! LaTeX Error: Bad math environment delimiter. See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.16 \end{split} ! You can't use \eqno' in math mode. \endmathdisplay@a ...\df@tag \@empty \else \veqno \alt@tag \df@tag \fi \ifx ... l.16 \end{split} ! Missing \endgroup inserted. <inserted text> \endgroup l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! LaTeX Error: \begin{split} on input line 16 ended by . See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! Missing \cr inserted. <inserted text> \cr l.16 \end{split} ! Missing { inserted. <inserted text> { l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! Missing { inserted. <inserted text> { l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! LaTeX Error: \begin{equation*} on input line 13 ended by \end{split}. See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Misplaced alignment tab character &. \math@cr@@@ ->\ifst@rred \nonumber \fi & \relax \make@display@tag \ifst@rred ... l.16 \end{split} ! Misplaced \cr. \math@cr@@@ ...fi \global \advance \row@ \@ne \cr l.16 \end{split} ! Extra }, or forgotten $. \gmeasure@ ...savetaglength@ \crcr #1\math@cr@@@ } }\restorecounters@ \if@fle... l.16 \end{split} ! Extra }, or forgotten$. \gmeasure@ ...avetaglength@ \crcr #1\math@cr@@@ }} \restorecounters@ \if@fleq... l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Display math should end with $$. <to be read again> \endgroup l.16 \end{split} ! Package amsmath Error: \begin{split} won't work here. See the amsmath package documentation for explanation. Type H <return> for immediate help. ... l.16 \end{split} ! Missing number, treated as zero. <to be read again> \relax l.17 \end{equation*} ! Illegal unit of measure (pt inserted). <to be read again> \relax l.17 \end{equation*} ! Too many }'s. \endmathdisplay@a ...@ \totwidth@ \egroup \egroup l.17 \end{equation*} ! LaTeX Error: \begin{document} ended by \end{equation*}. See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.17 \end{equation*} ! Missing  inserted. <inserted text>  l.17 \end{equation*} ! Display math should end with$$. <to be read again> \endgroup l.17 \end{equation*} ! Extra \endgroup. <recently read> \endgroup l.17 \end{equation*} [1] (./math.aux) ) (see the transcript file for additional information) Output written on math.dvi (1 page, 448 bytes). Transcript written on math.log.

where is an old node and it drifts, is the node at current time. Why would we do this? As approaches 1, we fall back to the situation that the nodes are stationary and no drifting is allowed. On the other hand, approaches 0 means we have all the nodes drifting to the circle of current time.

Drift of nodes for . All nodes are moving to a circle of current time.

The drifting effectively decrease the connectivity of the old nodes since they are drifting away from the center. Another view of this fading is that the connection probability power law index is larger, i.e.,

System Message: WARNING/2 ($$\gamma = 1 + 1/\beta.$$ )

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.16 (TeX Live 2015/Debian) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2016/02/01> Babel <3.9q> and hyphenation patterns for 81 language(s) loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2014/09/29 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/utf8x.def)) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucs.sty (/usr/share/texlive/texmf-dist/tex/latex/ucs/data/uni-global.def)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the ?' option. (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amstext.sty (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsopn.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amscls/amsthm.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amssymb.sty (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amsfonts.sty)) (/usr/share/texlive/texmf-dist/tex/latex/anyfontsize/anyfontsize.sty) (/usr/share/texlive/texmf-dist/tex/latex/tools/bm.sty) (./math.aux) (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucsencs.def) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.fd) ! LaTeX Error: Bad math environment delimiter. See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.16 \end{split} ! You can't use \eqno' in math mode. \endmathdisplay@a ...\df@tag \@empty \else \veqno \alt@tag \df@tag \fi \ifx ... l.16 \end{split} ! Missing \endgroup inserted. <inserted text> \endgroup l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! LaTeX Error: \begin{split} on input line 16 ended by . See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! Missing \cr inserted. <inserted text> \cr l.16 \end{split} ! Missing { inserted. <inserted text> { l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! Missing { inserted. <inserted text> { l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! LaTeX Error: \begin{equation*} on input line 13 ended by \end{split}. See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Misplaced alignment tab character &. \math@cr@@@ ->\ifst@rred \nonumber \fi & \relax \make@display@tag \ifst@rred ... l.16 \end{split} ! Misplaced \cr. \math@cr@@@ ...fi \global \advance \row@ \@ne \cr l.16 \end{split} ! Extra }, or forgotten $. \gmeasure@ ...savetaglength@ \crcr #1\math@cr@@@ } }\restorecounters@ \if@fle... l.16 \end{split} ! Extra }, or forgotten$. \gmeasure@ ...avetaglength@ \crcr #1\math@cr@@@ }} \restorecounters@ \if@fleq... l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Missing } inserted. <inserted text> } l.16 \end{split} ! Missing $inserted. <inserted text>$ l.16 \end{split} ! Display math should end with $$. <to be read again> \endgroup l.16 \end{split} ! Package amsmath Error: \begin{split} won't work here. See the amsmath package documentation for explanation. Type H <return> for immediate help. ... l.16 \end{split} ! Missing number, treated as zero. <to be read again> \relax l.17 \end{equation*} ! Illegal unit of measure (pt inserted). <to be read again> \relax l.17 \end{equation*} ! Too many }'s. \endmathdisplay@a ...@ \totwidth@ \egroup \egroup l.17 \end{equation*} ! LaTeX Error: \begin{document} ended by \end{equation*}. See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.17 \end{equation*} ! Missing  inserted. <inserted text>  l.17 \end{equation*} ! Display math should end with$$. <to be read again> \endgroup l.17 \end{equation*} ! Extra \endgroup. <recently read> \endgroup l.17 \end{equation*} [1] (./math.aux) ) (see the transcript file for additional information) Output written on math.dvi (1 page, 308 bytes). Transcript written on math.log.
• Growth of Internet Autonomous System

Internet AS on a hyperbolic disc. The radial coordinate is log of time, . Boguna et al (2010).

Boguna et al modeled the growth of internet AS using the popularity similarity method and it shows exactly the same statistical result as the actual internet AS data [6].

• Application to Cosmology

Krioukov et al came up with the idea that the whole universe can be mapped onto hyperbolic space and events are connected only to nearest neighbors. This in fact is already true in cosmology. Theories predicted that the matter density after inflation is power law, which can be explained by a dynamics generating of particle on a hyperbolic space. The authors created a map from the physical de Sitter space to hyperbolic space. Then the dynamic generation of the particles in the universe simple follows power law since the nodes generated this way has a power law distribution of degrees, i.e., a place that is dense initially is more likely to be dense after the inflation [5].

Map de Sitter space to hyperbolic space. Krioukov et al (2012).

What else?¶

1. Such a network is very probabily optimized for information storage in the real world, because it stores information both in the global network and the local connections. An analysis of the snapshot of a network at a certain time shows a hierarchical structure which contains information about the past. The key feature of dynamics is explicitly stored in the network structure and easily extracted so that information storage is robust. Small world network is efficient for information storage and processing. It doesn’t explore all possible connection of the network while allowing information to be propagated through the whole network efficiently. The power law feature is a logarithmic compression of information about the the real world, which keeps the large scale information (low degree nodes) of an object but neglects details (large degree nodes).
2. Does the brain follow the same law of dynamic generation of network? We know that the biological neural network is close to a small world network. Meanwhile, the popularityXsimilarity method models small world very well. As long as we find the proper metric/distance, we can confidently say that neural network always connect to the nearest neighbors.
3. Artificial neural networks? We have to think about Boltzmann machine rather than the layerized artificial neural network. The question is, will a Boltzmann machine with network modeled by the method be very common if it actually solves a realistic problem?

References and Notes¶

 [1] [arXiv:cond-mat/0009090](https://arxiv.org/abs/cond-mat/0009090v1).
 [2] Barabási, A.-L., & Albert, R. (1999). [Emergence of Scaling in Random Networks. Science, 286(5439), 509–512.](http://doi.org/10.1126/science.286.5439.509)
 [3] Krapivsky, P. L., Redner, S., & Leyvraz, F. (2000). [Connectivity of growing random networks. Physical Review Letters, 85(21), 4629–4632.](http://doi.org/10.1103/PhysRevLett.85.4629)
 [4] This express is specific for curvature . However, the final result of scaling doesn’t dependent on the curvature itself.
 [5] Krioukov, D., Kitsak, M., Sinkovits, R. S., Rideout, D., Meyer, D., & Boguñá, M. (2012). [Network Cosmology. Scientific Reports, 2, 793.](http://doi.org/10.1038/srep00793)
 [6] Boguñá, M., Papadopoulos, F., & Krioukov, D. (2010). [Sustaining the Internet with hyperbolic mapping. Nature Communications, 1(6), 1–8.](http://doi.org/10.1038/ncomms1063)

© 2018, Lei Ma| GitHub| | | Page Source| changelog| Created with Sphinx