Dynamic Social Network Modeling and Analysis Workshop Summary and Papers (2003) / Chapter Skim
Currently Skimming:
Predictability of Large-Scale Spatially Embedded Networks
Predictability of Large-Scale Spatially Embedded Networks
Pages 313-323
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 313... ...
Here, it is shown that upper bounds on the marginal edge probabilities for far-flung dyads can be used to place a lower bound on the predictive power of distance, and one such bound Is derived. Application of this bound to the special case of uniformly placed vertices on the plane suggests that only modest constraints are required for distance effects to dominate at large physical scales.
|
From page 314... ...
are likely to be attainable in practice for moderate to large physical scales, and thus that it is reasonable to expect that large-scare spatially embedded social networks will be readily predictable from vertex position data. 2 Notation en c} Basic Assumptions For the results which follow, we will focus exclusively on the case of a loopless undirected graph G = (V, E)
|
From page 315... ...
Specifically, we are interested in the extent to which knowledge of vertex positions within $ reduces our uncertainty regarding the edge set of G A natural measure of uncertainty - and the one which we shall employ here - is the Shannon entropy, which can be interpreted as the expected length of an optimally encoded signal expressing the value of a random variable.
|
From page 316... ...
Furthermore, when this bound on marginal edge probability becomes small, the predictive power of the position set becomes bounded by the probability that the distance between two randomly selected vertices will exceed the critical threshold. Thus, where the threshold 316 DYNAMIC SOCIAL NETWORK MODELING AND ANALYSIS
|
From page 317... ...
where population distributions and some crude estimates of the distanceiedge probability relationship may be all that is available. They also serve to reinforce the argument that the predictive power of distance is robust to varying assumptions about the precise determinants of network structure.
|
From page 318... ...
. For the distribution function of a Triangular deviate with lower bound a, upper bound b, and mode c we have FT (X)
|
From page 319... ...
1 _ 2 (b—>/~) 2bb b_ Aft I_ b2 To obtain the associated density function, fr2 (X)
|
From page 320... ...
2x {2z t~—~ + ~b4 ~ O < ~ < b = 2 - 1 2b2_ 2 _ 4 2b2_ 2 2x it sin (I) ~ (b ~ + b4 ~ b < x < Mob LO otherwise To arrive at the distribution function of d, we need merely integrate fame over the desired 320 DYNAMIC SOCIAL N~:TWORK MODELING AND ANAl~YSIS
|
From page 321... ...
+8(22_b2) 2 =4 1 b3 b4 x > Mob Substitution of ~ for x and e for b completes the proof 4.2 Predictability x < 0 O ~ x < b b < x < Mob x > pub [1 Using Lemma ~ together with Theorem 1, we may determine the maximum rC value needed to guarantee that a given fraction of the uncertainty in G can be accounted for by the euclidean distances between vertex positions; these threshold values are shown in Table I
|
From page 322... ...
Although it may be possible to obtain more predictive power using these or other models than Table ~ would suggest, the lower bounds alone indicate that physical layout has the potential to account for the overwhelming majority of network structure at even modest spatial scales. 5 Conclusion To summarize, then, it would seem that even a very modest null mode]
|
From page 323... ...
InDennis,W.,editor, Current Trends in Social Psychology, pages 163-217. University of Pittsburgh Press, Pittsburgh, PA.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.