The Structure of Geographical Threshold Graphs

被引：29
作者：
Bradonjic, Milan [1 ,2 ]
Hagberg, Aric [2 ]
Percus, Allon G. [3 ,4 ]
机构：
[1] UCLA, Dept Elect Engn, Los Angeles, CA 90095 USA
[2] Los Alamos Natl Lab, Math Modeling & Anal Grp, Theoret Div, Los Alamos, NM 87545 USA
[3] UCLA, Dept Math, Los Angeles, CA 90095 USA
[4] Claremont Grad Univ, Sch Math Sci, Claremont, CA 91711 USA
来源：
INTERNET MATHEMATICS | 2008年 / 5卷 / 1-2期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1080/15427951.2008.10129304
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We analyze the structure of random graphs generated by the geographical threshold model. The model is a generalization of random geometric graphs. Nodes are distributed in space, and edges are assigned according to a threshold function involving the distance between nodes as well as randomly chosen node weights. We show how the degree distribution, percolation and connectivity transitions, clustering coefficient, and diameter relate to the threshold value and weight distribution. We give bounds on the threshold value guaranteeing the presence or absence of a giant component, connectivity and disconnectivity of the graph, and small diameter. Finally, we consider the clustering coefficient for nodes with a given degree l, finding that its scaling is very close to 1/l when the node weights are exponentially distributed.
引用
收藏
页码：113 / 139
页数：27
相关论文
共 24 条
  • [1] Abello J., 2002, HDB MASSIVE DATA SET
  • [2] Aiello W., 2000, Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, P171, DOI 10.1145/335305.335326
  • [3] Alon N., 2004, PROBABILISTIC METHOD
  • [4] Emergence of scaling in random networks
    Barabási, AL
    Albert, R
    [J]. SCIENCE, 1999, 286 (5439) : 509 - 512
  • [5] The degree sequence of a scale-free random graph process
    Bollobás, B
    Riordan, O
    Spencer, J
    Tusnády, G
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2001, 18 (03) : 279 - 290
  • [6] BOLLOBAS B., 2001, RANDOM GRAPHS, V73
  • [7] Bonato A, 2005, LECT NOTES COMPUT SC, V3405, P159
  • [8] Bradonjic M, 2007, LECT NOTES COMPUT SC, V4863, P209
  • [9] Bradonjic Milan, 2007, 45 ANN ALL C COMM CO
  • [10] The volume of the giant component of a random graph with given expected degrees
    Chung, Fan
    Lu, Linyuan
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, 20 (02) : 395 - 411
123