I am interested in basic models of graphs (stochastic or deterministic) that are offered for real-life networks (like social networks, the Internet, neuron networks).
I will be thankful for answers that will describe the actual model and not just link to some reference. (Such links can be useful in comments.)
Complex networks is a young and active area of scientific research inspired largely by the empirical study of real-world networks such as computer networks, social networks, biological networks, ecological networks, telecommunication networks etc. A lot of interesting and important properties of complex networks were found by statistics such as sparsity, small world phenomenon (also called six degree separation, for example, from the ‘small world’ studies of Harvard sociologist Stanley Milgram[1], play of Guare [2], Hands shaking(Watt’s father remarks that he was only six handshakes away from the president of US) example of Watts[3]), power law distribution(also called long tail or heavy tail distribution or scale free, Barabási and Albert [4] noticed actor collaboration networks and World Wide Web had power law distribution).
The field continues to develop at a brisk pace, and has brought together researchers from many areas including mathematics, physics, biology, telecommunications, computer science, sociology, epidemiology, and others[5].
To set up the foundations of complex network, the first step is to define some new metrics. There are a lot of different metrics widely used in complex networks such as average degree, diameter, entropy, average distance, centrality, betweenness, density, clustering coefficient, transitivity, diffusion time etc.
How to model complex networks is one big issue in this area. Traditional well known model such as the popular Erdős-Rényi random network model does not fit on the real world network so well in most cases. For example, although Erdős-Rényi random network has small diameter, but have very few triangles, which is not like in social networks the friends of one person tend to be friends, too. Scientists are trying to find new mathematical models for complex networks.
For small world model, Watts and Strogatz [6] started from ring lattice with $n$ vertices and $k$ edges per vertex , and then rewired each edge with probability $p$, connecting one end to a vertex chosen at random, this can drastically reduce the diameter. Bollobás and Chung [7] added a random matching to a ring of $n$ vertices with nearest neighbor connections and showed the resulting graph had diameter $\sim\log n$. This model is called BC small world, however, this is weak in social network. Newman and Watts [8] (NW small world)added a Poisson number of shortcuts with mean $n\rho/2$ instead of rewiring edges, and then attaches them to randomly chosen pairs of sites. This results in a Poisson mean $\rho$ number of long distance edges per site.
For Power Law distribution model, Barabási and Albert [4] found some real world network such as actor collaboration networks and World Wide Web had degree distributions $p_k\sim Ck^{-\gamma}$ as $k\rightarrow \infty$. Usually $\gamma$ is between $2$ and $3$, but Liljeros et al. [9] found $\gamma_{male}=3.3$ and $\gamma_{female}=3.5$ by analyzing the data of sexual behavior of 4781 Swedes. Ebel et al. [10] found $\gamma=1.81$ by studying email network of Keil University. Newman[11][12][13] found the number of collaborators was better fit by a power law with an exponential cutoff $p_k\sim Ck^{-\tau}exp(-k/k_c)$ in collaboration network. Later, scholars found other values of $\gamma$. Barabási and Albert [4] introduced the preferential attachment model to give a mechanism explanation for power law distribution. Whether this model still keeps small world property? Bollobás and Riordan [14] showed for this model, the diameter $\sim \log n/(\log \log n)$. Chung and Lu[15][16] showed for their corresponding model (known as Chung-Lu model) has the distance between to randomly chosen vertices is $O(\log n/(\log \log n))$. Callaway, Hopcroft, Kleinberg, Newman and Strogatz [17] introduced CHKNS model inspired by Barabási and Albert [4].
Just name a few. Further details and more models are referenced to [18][19].
However, it is difficult to find a model which can fit perfectly on the real world networks in every aspect. Now the research in this area is usually data and application driven. For example, they study application problems such as influence maximization, community detection, rumor detection, recommender system, PageRank etc. , in which they design algorithm or mechanism and use some real world network data to make simulation to test the quality of algorithms, usually they don’t care too much about the model itself. But the big issue without an exact mathematical model is large scale data is hard to handle, thus some sparse optimization and large scale optimization techniques were introduced.
For other application such as the famous Kidney Exchange Long Chain mechanism of Al Roth, who won Nobel Prize, dynamic homogeneous random graph [20], Random compatibility graphs[21], sparse graphs [21]etc. were used. Those models are more mathematical than better fitting on the real world networks.
In communication networks, such as ad hoc sensor network, it is not small world nor power law distribution, random geometry network or other models are used.
[1] S. Milgram, “The small world problem,” Psychology Today, vol. 2, no. 1, pp.60–67, 1967.
[2] J. Guare, Six Degrees of Separation: A Play. New York: Vintage, 1990.
[3] Watts, Duncan J. Six degrees: The science of a connected age. WW Norton & Company, 2004.
[4] Barabási, Albert-László, and Réka Albert. "Emergence of scaling in random networks." science 286.5439 (1999): 509-512.
[5] A.E. Motter, R. Albert (2012). "Networks in Motion". Physics Today 65 (4): 43–48.
[6] Watts, Duncan J., and Steven H. Strogatz. "Collective dynamics of ‘small-world’networks." nature 393.6684 (1998): 440-442.
[7]Bollobás, Bela, and Fan R. K. Chung. "The diameter of a cycle plus a random matching." SIAM Journal on discrete mathematics 1.3 (1988): 328-333.
[8] Newman, Mark EJ, and Duncan J. Watts. "Renormalization group analysis of the small-world network model." Physics Letters A 263.4 (1999): 341-346.
[9]Liljeros, Fredrik, et al. "The web of human sexual contacts." Nature 411.6840 (2001): 907-908.
[10] Ebel, Holger, Lutz-Ingo Mielsch, and Stefan Bornholdt. "Scale-free topology of e-mail networks." Physical review E 66.3 (2002): 035103.
[11] Newman, Mark EJ. "The structure of scientific collaboration networks." Proceedings of the National Academy of Sciences 98.2 (2001): 404-409.
[12] Newman, Mark EJ. "Scientific collaboration networks. I. Network construction and fundamental results." Physical review E 64.1 (2001): 016131.
[13] Newman, Mark EJ. "Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality." Physical review E 64.1 (2001): 016132.
[14] Bollobás, Béla, and Oliver Riordan. "The diameter of a scale-free random graph." Combinatorica 24.1 (2004): 5-34.
[15] Chung, Fan, and Linyuan Lu. "Connected components in random graphs with given expected degree sequences." Annals of combinatorics 6.2 (2002): 125-145.
[16] Chung, Fan, and Linyuan Lu. "The average distance in a random graph with given expected degrees." Internet Mathematics 1.1 (2004): 91-113.
[17] Callaway, D. S., Hopcroft, J. E., Kleinberg, J. M., Newman, M. E., & Strogatz, S. H. (2001). Are randomly grown graphs really random?. Physical Review E, 64(4), 041902.
[18] Chung, Fan RK, and Linyuan Lu. Complex graphs and networks. Vol. 107. Providence: American mathematical society, 2006.
[19] Durrett, Richard. Random graph dynamics. Vol. 200. No. 7. Cambridge: Cambridge university press, 2007.
[20] Ashlagi, Itai, Patrick Jaillet, and Vahideh H. Manshadi. "Kidney exchange in dynamic sparse heterogenous pools." arXiv preprint arXiv:1301.3509 (2013).
[21] Ashlagi, Itai, et al. The need for (long) chains in kidney exchange. No. w18202. National Bureau of Economic Research, 2012.
There is considerable work on modeling automobile traffic flows via directed graphs. One high-level article is
Frank Kelly. "The mathematics of traffic in networks." The Princeton Companion to Mathematics (2008). (PDF download link.)
The graph modeling is not sophisticated: just a directed graph representing routes between (e.g.) towns. What is more interesting is modeling driver route choices. One natural model is to seek a Wardrop equilibrium: "Only when they cannot find alternative, quicker routes will drivers not have an incentive to change routes." The defining characteristic of a Wardrop equilibrium is that, "if a route $r$ is actively used, then it achieves the minimum delay over all routes serving its source–destination pair."
The result does not mean that average delays in the network will be minimal: a striking illustration of this fact is provided by Braess’s paradox.
But then Kelly goes on to argue that
with the imposition of appropriate tolls, it is possible for the self-interested behavior of drivers to lead to an equilibrium pattern of flow that minimizes total delay.
There are different models for terrorist or other criminal networks. I can only give references.
Roy H. A. Lindelauf (Royal Dutch Defense Academy) et al., "The Influence of Secrecy on the Communication Structure of Covert Networks" http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1096057
Steven Brams (New York University) et al., "Influence in Terrorist Networks: From Undirected to Directed Graphs" http://www.rit.edu/cos/sms/cmmc/literature/Brams_etal_2006.pdf
Jonathan David Farley, "Toward a Mathematical Theory of Counterterrorism" http://www.rit.edu/cos/sms/cmmc/literature/Proteus.pdf This model was actually used by the head of Jamaica's National Intelligence Bureau.
Mariagiovanna Baccara and Heski Bar-Isaac (New York University), "How to Organize Crime" http://apps.olin.wustl.edu/faculty/baccara/crimeRES.pdf
