| This thesis studies five problems of network properties from a unified local-to-global viewpoint of statistical physics: (1) We propose an algorithm that allows the discovery of communities within graphs of arbitrary size, based on Kirchhoff theory of electric networks. Its time complexity scales linearly with the network size. We additionally show how this algorithm allows for the swift discovery of the community surrounding a given node without having to extract all the communities out of a graph. (2) We present a dynamical theory of opinion formation that takes explicitly into account the structure of the social network in which individuals are embedded. We show that the weighted fraction of the population that holds a certain opinion is a martingale. We show that the importance of a given node is proportional to its degree. We verify our predictions by simulations. (3) We show that, when the information transmissibility decays with distance, the epidemic spread on a scale-free network has a finite threshold. We test our predictions by measuring the spread of messages in an organization and by numerical experiments. (4) Suppose users can switch between two behaviors when entering a queueing system: one that never restarts an initial request and one that restarts infinitely often. We show the existence of two thresholds. When the system load is below the lower threshold, it is always better off to be impatient. When above, it is always better off to be patient. Between the two thresholds there exists a homogeneous Nash equilibrium with non-trivial properties. We obtain exact solutions for the two thresholds. (5) We study the endogenous dynamics of reputations in a system consisting of firms with long horizons that provide services with varying levels of quality, and customers who assign to them reputations on the basis of the quality levels that they experience when interacting with them. We show that the dynamics can lead to either well defined equilibria or persistent nonlinear oscillations in the number of customers visiting a firm, implying unstable reputations. We establish the stable criteria. |
