One can model a social network as a long-range percolation model on a graph {0, 1, …, N}2. The edges (x, y) of this graph are selected with probability ≈ β/||x - ys if ||x - y|| 1, and with probability 1 if ||x - y|| = 1, for some parameters β, s 0. That is, people are more likely to be acquainted with their neighbors than with people at large distance. This model was introduced by Benjamini and Berger [2] and it resembles a model considered by Kleinberg in [6], [7]. We are interested in how small (probabilistically) is the diameter of this graph as a function of β and s, thus relating to the famous Milgram's experiment which led to the "six degrees of separation" concept. Extending the work by Benjamini and Berger, we consider a d-dimensional version of this question on a node set {0, 1, …, N}d and obtain upper and lower bounds on the expected diameter of this graph. Specifically, we show that the expected diameter experiences phase transitions at values s = d and s = 2d. We compare the algorithmic implication of our work to the ones of Kleinberg, [6].
展开▼
机译:可以将社交网络建模为图{0,1,…, N I>} 2 SUP>上的远程渗流模型。如果|| x-y ||,则以概率≈β/ || x-y s I> SUP>选择该图的边缘(x,y) > 1,并且|| x-y ||的可能性为1 = 1,对于某些参数β, s I>>0。也就是说,与相距较远的人相比,人们更容易结识邻居。该模型由Benjamini和Berger提出[2],类似于Kleinberg在[6],[7]中考虑的模型。我们感兴趣的是,该图的直径有多小(概率上)是β和 s I>的函数,因此与著名的米尔格拉姆(Milgram)实验相关,该实验导致了“六度分离”的概念。扩展Benjamini和Berger的工作,我们考虑在节点集{0,1,…, N I>} d I>维版本> d I> SUP>并获得此图的预期直径的上限和下限。具体来说,我们证明了预期的直径在值 s = d I>和 s = 2d时经历了相变。 I>我们将工作的算法含义与Kleinberg的算法含义进行比较,[ 6]。
展开▼