The subject of this monograph is to shed light on network-based phenomena in complex social environment. The author, abstracting from the modelling details of specific contexts (labor markets, technological diffusion, etc.). Instead he concentrates on some of the key common forces that underlie agents’ behavior in most of those cases. In particular, he focuses on diffusion, search, and play that are three essential forces at work in virtually all interesting network applications. Diffusion, play, and search are the central notions that help organize this monograph.
Firstly, he presents of the main concepts and basic tools of the modern theory of complex networks. The first step involves the introduction of the theoretical setup, certain key notions, and a collection of network characteristics of interest. Then, the framework that will act as a benchmark for a study of random networks: the so-called binomial model is discussed. Next, this framework is generalized to allow for arbitrary degree distributions (i.e. not just binomial or Poisson), although maintaining the assumption that the network is random and has no “structure” (i.e. no correlations, clustering, etc.). With this assumption the talk turns to the discussion of some of the most prominently studied networks with specific structure. In each case, main concern is to understand what are the implications of the different structures on key network characteristics such as average internode distance, clustering, and the distribution of connectivity. Specifically, the study of generalized random networks relies on generating-function methods to characterize induced distributions, and the study of small-world and a scale-free network applies the so-called mean-field approach. While the essence of these methods is discussed in the main text, the more technical discussion is gathered in Appendixes A and C.
Next chapter focuses on what we shall call epidemic diffusion. This refers to a type of diffusion that proceeds as biological infection, i.e. it is mediated by bilateral contact and grows with exposure but is unaffected by neighborhood (frequency-dependent) considerations. Depending on whether such “infection” is irreversible, may turn into recovery, or revert to the original susceptibility; it arrives at the SI, SIR, or SIS frameworks respectively. In the first two cases (SI and SIR), diffusion waves are unidirectional and the main questions of interest dwell on what is the range and resilience of their reach. These questions can be answered precisely (relating them, in particular, to the topology of the underlying network) by relying on a suitable adaptation of the generating-function techniques first used in previous part of the book. Analogous questions can be addressed as well within the bidirectional SIS framework. In that context, however, was obtained only approximate results by resorting to mean-field dynamic analysis. The results thus attained again underscore the point that, in general, the underlying network topology crucially affects the process of diffusion. In particular, the threshold for the diffusion rate beyond which long-run prevalence of infection obtains turns out to be bounded above zero for networks with a well-defined characteristic scale (e.g. networks with a Poisson degree distribution) but is zero otherwise (say. for broad scale-free networks). The network topology also has an important bearing on the way different policies (e.g. the “immunization” of selected nodes) may impinge on diffusion. Following up on the topic of diffusion, the author also studies how frequency-dependent diffusion is affected when the so-far maintained assumption that the underlying network displays no structure is dispensed with. In this respect, was outlined on a model that, by allowing for local structure, highlights the important role played bye some measure of network cohesion (or the lack thereof) in the reach of diffusion under neighborhood effects. In many applications, the decision problem faced by agents is not merely one of adoption (temporary or not) but concerns what particular behavior to choose among several possible. Then the considerations involved become “strategic” and, often, the problem is one of local coordination.
A useful framework to address this latter case is provided by the so-called Potts model in statistical physics – an extension of the classical Ising setup to an arbitrary finite number of possible node states. So , in next part the author shows the results of investigation that model both in the simplest scenario where the underlying network is a regular lattice and in the context where interaction occurs along an arbitrary (generalized) random network. Next key problem is the problem of search, an issue of primary importance in large social networks. The need to search arises, for example, when a node/agent is confronted with a problem that can only be solved through the concourse of some other specific (yet unknown) node/agent in the network. What algorithms or protocols will work effectively for this purpose if, given the complexity of the setup, nodes can rely only on local, or otherwise limited, information? This general question was studied under a number of different specifications of what is meant by information to be limited or local, and under different assumptions on the topology of the social network. For example, it turns out that if the network is scale-free and therefore includes a significant fraction of high-degree nodes, a search/communication protocol that biases the search path toward nodes with high degree is particularly effective. Or, if there is an underlying “geography” that can inform the direction of queries (e.g. a lattice network or some other coordinate system), search can take advantage of it to improve its performance substantially. In general, one should conceive search in a network as involving many simultaneous quests, proceeding in parallel (i.e. simultaneously) along different paths and with different objectives. This then raises the question of congestion. What happens if a particular node faces many concurrent queries at some point in time? If, due to a limited ability to process information, not all of those queries can be handled simultaneously, congestion-induced delays on the search process might ensue.
The last part of this chapter of a book addresses these questions formally and sheds some light on how the topology of the network impinges on the problem of congestion in search. This in turn leads to a corresponding network design problem that aims at identifying what topology of the network is optimal (minimizes delay), given the trade-offs involved (e.g. short distances versus lo congestion). Finally, the phenomena of search, diffusion, and play in social networks and brings them to bear on the crucial issue of (endogenous) network formation in a complex environment reconsiders. In contrast, when the environment is complex (say, because it is highly non-stationary), agents are best conceived as continuously groping for profitable links/opportunities. This search, of course, must then largely rely on the prevailing social network – it might be channelled, for example, through a collection of different dynamic models where the nonstationarity of the environment is made explicit and takes alternative forms. In conclude part the first approach to the problem of network evolution contemplates only quite basic considerations pertaining how payoffs and incentives bear on link formation. Also other scenarios discussed, but in all cases were found an interesting interplay between network architecture and strategic choice that eventually determines whether or not the society manages to build up and maintain a high level of overall connectivity. If this occurs, the population is also able to sustain, respectively, a high level of coordination, cooperation, or growth.