Transcript Search in Networks - Computer Science and Engineering

Lecture 28:
Search in structured networks
CS 765 Complex Networks
Slides are modified from Lada Adamic
How do we search?
Mary
Who could
introduce me to
Richard Gere?
Bob
Jane
2
Poisson graph
number of
nodes found
93
19
15
11
7
3
1
3
power-law graph
number of
nodes found
94
67
63
54
2
6
1
4
How would you search for a node here?
http://ccl.northwestern.edu/netlogo/models/run.cgi?GiantComponent.884.534
5
What about here?
http://projects.si.umich.edu/netlearn/NetLogo4/RAndPrefAttachment.html
6
gnutella network fragment
7
Gnutella network
50% of the files in a 700 node network can be found in < 8 steps
cumulative nodes found at step
1
0.8
0.6
0.4
0.2
0
high degree seeking 1st neighbors
high degree seeking 2nd neighbors
0
20
40
60
80
100
step
8
here?
9
And here?
10
Small world experiments review
MA
NE
Source: undetermined
Source: NASA, U.S. Government;
http://visibleearth.nasa.gov/view_rec.php?id=2429
Milgram (1960’s), Dodds, Muhamad, Watts (2003)
Given a target individual and a particular property, pass the message to a
person you correspond with who is “closest” to the target.
Short chain lengths – six degrees of separation
Typical strategy – if far from target choose someone geographically closer,
if close to target geographically, choose someone professionally closer
Why are small worlds navigable?
Source: Watts, D.J., Strogatz, S.H.(1998) Collective dynamics of 'small-world' networks. Nature 393:440-442.
How are people are able to find short paths?
How to choose among hundreds of acquaintances?
Strategy:
Simple greedy algorithm - each participant chooses correspondent
who is closest to target with respect to the given property
Models
geography
Kleinberg (2000)
hierarchical groups
Watts, Dodds, Newman (2001), Kleinberg(2001)
high degree nodes
Adamic, Puniyani, Lukose, Huberman (2001), Newman(2003)
13
Reverse small world experiment







Killworth & Bernard (1978):
Given hypothetical targets (name, occupation, location, hobbies, religion…)
participants choose an acquaintance for each target
Acquaintance chosen based on
(most often) occupation, geography
only 7% because they “know a lot of people”
Simple greedy algorithm: most similar acquaintance
two-step strategy rare
Source: 1978 Peter D. Killworth and H. Russell Bernard. The Reverse Small World Experiment Social Networks 1:159–92.
How many hops actually separate any two
individuals in the world?
 People use only local information
 not perfect in routing messages
 “The accuracy of small world chains in social networks”
Peter D. Killworth, Chris McCarty, H. Russell Bernard & Mark House:
 Analyzed 10,920 shortest path connections between 105
members of an interviewing bureau,
 together with the equivalent conceptual, or ‘small world’
routes, which use individuals’ selections of
intermediaries.
 study the impact of accuracy within small world chains.
 The mean small world path length (3.23) is 40% longer
than the mean of the actual shortest paths (2.30)
 Model suggests that people make a less than optimal choice
more than half the time.
15
review: Spatial search
Kleinberg, ‘The Small World Phenomenon, An Algorithmic Perspective’
Proc. 32nd ACM Symposium on Theory of Computing. (Nature 2000)
“The geographic movement of the [message]
from Nebraska to Massachusetts is striking.
There is a progressive closing in on the target
area as each new person is added to the
chain”
S.Milgram ‘The small world problem’,
Psychology Today 1,61,1967
nodes are placed on a lattice and
connect to nearest neighbors
r
d
additional links placed with puv~ uv
16
the network otherwise known as sample.gdf
Strategy 1: High degree search
Power-law degree distribution of all senders of email passing through HP labs
10
0
outdegree distribution
 = 2.0 fit
of senders
proportionfrequency
10
10
10
10
-2
-4
-6
-8
10
0
10
1
10
2
10
3
10
4
outdegree
number of recipients
sender has sent email to
18
Filtered network
(at least 6 messages sent each way)
Degree distribution no longer power-law, but Poisson
35
10
0
p(k)
25
p(k)
30
10
-2
20
15
10
10
-4
0
20
40
k
60
80
5
0
0
20
40
60
number of email correspondents, k
80
It would take 40 steps on average (median of 16) to reach a target!
19
Strategy 2:
Geography
20
Communication across corporate geography
1U
1L
87 % of the
4,000 links are
between individuals
on the same floor
4U
2U
3U
2L
3L
21
Cubicle distance vs. probability of being linked
0
10
measured
1/r
proportion of linked pairs
1/r2
-1
10
-2
10
optimum for search
-3
10
2
10
3
10
distance in feet
source: Adamic and Adar, How to search a social network, Social Networks,
22
Age distribution
LiveJournal
13 18483
14 87505
 basic statistics
 Users (stats from April 2006)






Total accounts:
9,980,558
... active in some way:
1,979,716
... that have ever updated:6,755,023
... update in last 30 days: 1,300,312
... update in last 7 days:
751,301
... update in past 24 hours: 216,581
15 211445
16 343922
17 400947
18 414601
19 405472
20 371789
21 303076
22 239255
 Male: 1,370,813 (32.4%)
 Female: 2,856,360 (67.6%)
 Unspecified: 1,575,389
23 194379
24 152569
25 127121
26 98900
27 73392
28 59188
29 48666
23
Geographic Routing in Social Networks
 David Liben-Nowell, Jasmine Novak, Ravi Kumar,
Prabhakar Raghavan, and Andrew Tomkins (PNAS’05)
 data used
 Feb. 2004
 500,000 LiveJournal users with US locations
 giant component (77.6%) of the network
 clustering coefficient: 0.2
24
Degree distributions
 The broad degree distributions we’ve learned to know
and love
 but more probably lognormal than power law
broader in degree than outdegree distribution
Source: http://www.cs.carleton.edu/faculty/dlibenno/papers/lj/lj.pdf
25
Results of a simple greedy geographical algorithm
 Choose source s and target t randomly
 Try to reach target’s city – not target itself
 At each step, the message is forwarded from the current message holder u
to the friend v of u geographically closest to t
stop if d(v,t) > d(u,t)
13% of the chains are completed
if d(v,t) > d(u,t)
pick a neighbor at random in the
same city if possible, else stop
80% of the chains are completed
26
the geographic basis of friendship
 d = d(u,v) the distance between pairs of people
 The probability that two people are friends given their
distance is equal to
 P(d) = e + f(d), e is a constant independent of geography
 e is 5.0 x 10-6 for LiveJournal users who are very far apart
27
the geographic basis of friendship
 The average user will have ~ 2.5 non-geographic friends
 The other friends (5.5 on average) are distributed according to an
approximate 1/distance relationship
 But 1/d was proved not to be navigable by Kleinberg, so what gives?
28
Navigability in networks of variable geographical density
 Kleinberg assumed a uniformly populated 2D lattice
 But population is far from uniform
 population networks and rank-based friendship
 probability of knowing a person depends not on absolute
distance but on relative distance
 i.e. how many people live closer Pr[u ->v] ~ 1/ranku(v)
29
what if we don’t have geography?
30
does community structure help?
31
Why search is fast in hierarchical topologies
R
R’
T
S
33
does it work in practice? back to HP Labs: Organizational hierarchy
Strategy 3:
Organizational Hierarchy
38
Email correspondence superimposed on the organizational hierarchy
39
Example of search path
distance 2
distance 1
distance 1
distance 1
hierarchical distance = 5
search path distance = 4
40
Probability of linking vs. distance in hierarchy
observed
fit exp(-0.92*h)
probability of linking
0.6
0.5
0.4
0.3
0.2
0.1
0
2
4
6
hierarchical distance h
8
10
in the ‘searchable’ regime: 0 <  < 2 (Watts, Dodds, Newman 2001)
41
Results
5
x 10
distance
hierarchy
geography
geodesic
org
random
median
4
7
3
6
28
mean
5.7 (4.7)
12
3.1
6.1
57.4
4
16000
number of pairs
number of pairs
14000
hierarchy
4
3
2
geography
12000
10000
8000
6000
4000
1
2000
0
0
5
10
15
number of steps in search
20
0
0
252
4
6
8
10
12
14
16
18
20
number of steps
source: Adamic and Adar, How to search a social network, Social Networks, 27(3), p.187-203, 2005.
42
Differences between data sets
HP labs email network
Online community
• complete image of
communication network
• partial information of
social network
• affinity not reflected
• only friends listed
Degree Distribution for Nexus Net
2469 users, average degree 8.2
200
number of users
number of users with so many links
250
150
2
10
1
10
0
10
0
10
100
1
10
number of links
2
10
50
0
0
20
40
60
number of links
80
100
source: Adamic and Adar, How to search a social network, Social Networks, 27(3), p.187-203, 2005.
Problem: how to construct hierarchies?
Probability of linking by separation in years
0.02
prob. two grads are friends
prob. two undergrads are friends
0.014
0.012
0.01
0.008
0.006
data
(x+1)-1.7 fit
0.015
0.01
0.005
0
0
1
2
3
4
separation in years
5
0.004
0.002
data
(x+1)-1.1 fit
0
0
1
2
3
separation in years
source: Adamic and Adar, How to search a social network, Social Networks, 27(3), p.187-203, 2005.
Hierarchies not useful for other attributes:
Geography
probability of being friends
0.06
0.05
0.04
0.03
0.02
0.01
0
0
100
200
300
400
500
600
distance between residences
Other attributes: major, sports, freetime activities, movie preferences…
source: Adamic and Adar, How to search a social network, Social Networks, 27(3), p.187-203, 2005.
Strategy using user profiles
prob. two undergrads are friends (consider simultaneously)
• both undergraduate, both graduate, or one of each
• same or different year
• both male, both female, or one of each
• same or different residences
• same or different major/department
strategy
random 133
high degree
profile
Results
median
390
39
21
mean
137
53
With an attrition rate of 25%, 5% of the messages get through at
an average of 4.8 steps,
=> hence network is barely searchable
conclusions
Individuals associate on different levels into groups.
Group structure facilitates decentralized search using social ties
Hierarchy search faster than geographical search
A fraction of ‘important’ individuals are easily findable
Humans may be more resourceful in executing search tasks:
making use of weak ties
using more sophisticated strategies
51