18
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Characteristic times of biased random walks on complex networks

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We consider degree-biased random walkers whose probability to move from a node to one of its neighbors of degree \(k\) is proportional to \(k^{\alpha}\), where \(\alpha\) is a tuning parameter. We study both numerically and analytically three types of characteristic times, namely: i) the time the walker needs to come back to the starting node, ii) the time it takes to visit a given node for the first time, and iii) the time it takes to visit all the nodes of the network. We consider a large data set of real-world networks and we show that the value of \(\alpha\) which minimizes the three characteristic times is different from the value \(\alpha_{\rm min}=-1\) analytically found for uncorrelated networks in the mean-field approximation. In addition to this, we found that assortative networks have preferentially a value of \(\alpha_{\rm min}\) in the range \([-1,-0.5]\), while disassortative networks have \(\alpha_{\rm min}\) in the range \([-0.5, 0]\). We derive an analytical relation between the degree correlation exponent \(\nu\) and the optimal bias value \(\alpha_{\rm min}\), which works well for real-world assortative networks. When only local information is available, degree-biased random walks can guarantee smaller characteristic times than the classical unbiased random walks, by means of an appropriate tuning of the motion bias.

          Related collections

          Most cited references27

          • Record: found
          • Abstract: found
          • Article: found
          Is Open Access

          Assortative mixing in networks

          M. Newman (2002)
          A network is said to show assortative mixing if the nodes in the network that have many connections tend to be connected to other nodes with many connections. We define a measure of assortative mixing for networks and use it to show that social networks are often assortatively mixed, but that technological and biological networks tend to be disassortative. We propose a model of an assortative network, which we study both analytically and numerically. Within the framework of this model we find that assortative networks tend to percolate more easily than their disassortative counterparts and that they are also more robust to vertex removal.
            Bookmark
            • Record: found
            • Abstract: found
            • Article: found
            Is Open Access

            Mixing patterns in networks

            M. Newman (2002)
            We study assortative mixing in networks, the tendency for vertices in networks to be connected to other vertices that are like (or unlike) them in some way. We consider mixing according to discrete characteristics such as language or race in social networks and scalar characteristics such as age. As a special example of the latter we consider mixing according to vertex degree, i.e., according to the number of connections vertices have to other vertices: do gregarious people tend to associate with other gregarious people? We propose a number of measures of assortative mixing appropriate to the various mixing types, and apply them to a variety of real-world networks, showing that assortative mixing is a pervasive phenomenon found in many networks. We also propose several models of assortatively mixed networks, both analytic ones based on generating function methods, and numerical ones based on Monte Carlo graph generation techniques. We use these models to probe the properties of networks as their level of assortativity is varied. In the particular case of mixing by degree, we find strong variation with assortativity in the connectivity of the network and in the resilience of the network to the removal of vertices.
              Bookmark
              • Record: found
              • Abstract: found
              • Article: found
              Is Open Access

              Dynamical and correlation properties of the Internet

              The description of the Internet topology is an important open problem, recently tackled with the introduction of scale-free networks. In this paper we focus on the topological and dynamical properties of real Internet maps in a three years time interval. We study higher order correlation functions as well as the dynamics of several quantities. We find that the Internet is characterized by non-trivial correlations among nodes and different dynamical regimes. We point out the importance of node hierarchy and aging in the Internet structure and growth. Our results provide hints towards the realistic modeling of the Internet evolution.
                Bookmark

                Author and article information

                Journal
                12 July 2013
                2013-11-19
                Article
                10.1103/PhysRevE.89.012803
                1307.3430
                992dd347-23d7-4e93-8292-03000c3391c0

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                Phys. Rev. E 89, 012803 (2014)
                18 pages, 14 figures, 1 table
                physics.soc-ph cs.SI

                Comments

                Comment on this article