Transcript An Algorithmic Approach to Computer Vision

GETTING CONNECTED:
SOCIAL SCIENCE IN THE AGE OF
NETWORKS
CAPSTONE PRESENTATION
Presenters: David Easley, Jon Kleinberg, Kathleen O’Connor,
Michael Macy, Dan Huttenlocher
Rest of the Team: John Abowd, Larry Blume, Geri Gay,
Jeffrey Prince, David Strang
Team Postdocs: Mary Still, Ted Welser
April 23, 2008
The Cornell Networks Team
 From across Cornell: Arts & Sciences, CALS, CIS,
ILR, Johnson School
2
What are Networks?
Transportation Network
3
Social Networks
with Data Collected by Hand
Nodes-people, Edges-friendships
Friendships in a 34-person karate club that split apart---Zachary, 1977
4
Social Network Discovered from Traces
of Online Data
Email communication between 436 employees in HP Research
Lab—Adamic and Adar, 2005
5
Social Science and Networks
Trade flows between countries
Krempel+Plumper, 2003
Structure and Power
Blume, Easley, Kleinberg+Tardos, 2007
6
Cascades, the Spread of Rumors,
the Reliability of Information
Links between political blogs prior to 2004 election---Adamic+Glance, 2005
7
Networks are Everywhere
 The study of networks integrates ideas
from the social sciences and computer
science, as well as information science,
statistics, biology, physics…
 The growth of the Internet has provided
us with data that previously was difficult
or impossible to obtain
 Cornell is a leader in this area
8
Networks and the ISS
 Encourage collaboration across disciplinary
boundaries
– Ongoing research between economists,
sociologists, psychologists, and computer and
information scientists
 Engage the Cornell community (faculty,
graduate students and undergrads) in
cutting-edge research
– Post docs
– Graduate students
– New undergrad courses with large enrollment
9
Theme Project Activities
 Workshops, seminars, reading groups
 Educational initiatives
 Funding and recruiting opportunities
 New inter-disciplinary research directions
10
Conferences
 Ran conferences on aspects of project
theme
– “Search and Diffusion in Social Networks”
– “Symposium on Self-Organizing Online
Communities” (co-sponsored by Microsoft)
 Brought national leaders from academia
and industry to campus
– E.g., Ron Burt, Nosh Contractor, Paul Dimaggio, Matt
Jackson, Michael Kearns, Bob Kraut, Peter Monge, Duncan
Watts, Barry Wellman …
11
Educational Initiatives
 New courses in all project areas, from
introductory to graduate
– Network material incorporated into existing
courses
– ECON, SOC, COMM, ILR, CIS, JGSM
 “Networks”: new intro undergrad course
– Cross-listed in ECON, SOC, CS, INFO
– This spring: 280 students from 33 different
majors
12
Networks
(ECON/SOC/CS/INFO 204)
High-school dating (Bearman, Moody, & Stovel 2004)
A course on how the social,
natural, and technological
worlds are connected, and
how the study of networks
shed light on these
connections. Topics include:
how opinions, fads, and
political movements spread
through society; the
robustness and fragility of
food webs and financial
markets; and the technology,
economics, and politics of
Web information and on-line
communities.
Corporate e-mail (Adamic and Adar, 2005)
13
Networks Class Blog
14
Recruiting and Funding
 Networks activity on campus enhanced
many other efforts
 Recruiting directions related to networks
in Sociology, Communication, and CIS
 Large-Scale NSF funding
– Cyberinfrastructure tools (2005-present)
– New proposals being pursued by expanded
version of project team
15
New Research Directions
 Networks activity drew in many faculty
beyond original project team
 New research informed by perspectives
from multiple areas
 Next: two examples (out of many)
– Social cognition and individual behavior
– Social contagion and on-line communities
16
Social Networks Represent
Relationships Among People
People work collaboratively, share opinions, create new knowledge through
their decisions to build a relationship (or not)
How do people understand and navigate their social environments to gain
resources they care about—ideas, opinions, social support, political allies,
status, for example? (Stephen Sauer and Ted Welser)
17
Micro-Foundations of Social Networks
 Systematic investigations into factors that
influence people’s
– Cognitions about their social networks
– Intentions to create relationships (ties)
– Efforts to create relationships
 Goals
– Understanding how networks evolve
– A psychological account of the spread of
influence and ideas in social systems
18
People and their Network Positions
 Personality psychology perspective
– People are endowed with traits that are
heritable, unaffected by external influences,
and stable across the life span
 Links between people’s traits and their
positions in their social networks (Klein,
Lim, Saltz, & Mayer, 2004)
– People who are high in neuroticism tend to be
less central in their networks (advice and
friendship)
19
A Novel Social Network on Second Life
Mark
(UK)
James
(beard)
Jill
(pink)
Ben
(glasses)
Emma
(penguin)
Mary
(brown
pants)
Scene from Second Life
20
Where We Are Going
 How do people understand and navigate their
social environments to gain resources they care
about?
 Develop interventions to teach people strategies
to make them more effective
– Better able to spot opportunities to build social
capital
– Better able to translate those opportunities
into advantageous network positions
 New forms of social engagement and interaction
give us new (and improved?) ways of studying
social cognition and social behavior
21
It certainly
is a That’s
amazing
youLeads to Small Talk…
A Chance
Encounter
in a Distant
Land
small world!know my Uncle Charlie!
22
Six Degrees of Separation
The planet
is very
large: 6.5b!
Yet the world
is small: 6˚
How is this possible?
23
Adding to the Mystery…
 Easy to explain if the social ties were
random
 But friendships tend to be highly clustered
B
A
C
24
Solved by Watts & Strogatz
 A few long-range ties
– Create “shortcuts” between
otherwise distant nodes
– While preserving the
clustering of a social
network
26
The “Strength of Weak Ties”
 Long-range ties tend to be relationally
weak
– Less frequent interaction
– Lower trust and influence
 But structurally strong
– Access to new ideas and information
– Accelerate the spread of disease
27
Weak Ties Are Key
“Whatever is to be diffused can reach a larger number of
people, and traverse a greater social distance, when passed
through weak ties rather than strong.”
-- Mark Granovetter, 1973
 A truism across the social & information sciences
 But there are some intriguing anomalies...
28
The Chain-Letter Paradox*
If most people are separated by only six degrees,
why are chain letters hundreds of links long?
Sequence of signatures on e-mail chain letter protesting the Iraq war, with
18,119 nodes, median depth is 288.
*Liben-Nowell & Kleinberg 2008, “Tracing information flow on a global
scale using Internet chain-letter data,” PNAS 105:4633-38.
29
The Problem of “Critical Mass”
 If an epidemic can quickly leap continents
and reach millions of people in a few days,
why do social movements often spread
spatially and incrementally prior to
reaching a “take-off” point?
30
Why Are Communities Clustered?
 A cluster is a dense “cloud” of mutual
friends
 How do these form?
– Conventional wisdom: people join communities
and then become mutual friends
– Maybe it is actually the other way around:
people join communities to be with mutual
friends?
31
Social Cloud Formation
 875 LiveJournal (blogging) communities
 Individuals one degree removed
 Joining as a function of
– Number of friends who are already members
– Clustering among friends
*Backstrom, Huttenlocher, Kleinberg, Lan, 2006. “Group Formation in
Large Social Networks: Membership, Growth, & Evolution,” Proc. 12th
ACM SIGKDD Intl. Conf. on Knowledge Discovery & Data Mining.
32
Number and clustering of friends
A
B
C
Time 1
33
Number and clustering of friends
A
B
C
Time 2
34
Number and clustering of friends
A
B
C
Time 3
35
Number and clustering of friends
A
B
C
Time 4
36
Number and clustering of friends
A
B
C
Time 5
37
Number and clustering of friends
A
B
C
Time 6
38
Number and clustering of friends
A
B
C
Time 7
39
Number and clustering of friends
A
B
C
Time 8
40
Why is Clustering Important?
 Chain-letters and social movements seem
to avoid taking “shortcuts”
 It’s the mutual friends that seem to be key
to growth of communities
 If disease and information can take
“shortcuts,” why can’t social contagions?
41
A Simple Explanation*
 Social contagions differ from disease and
information
– Acquiring information is not the same thing as
acting on it
• The same information from two friends is redundant
• The same advice from two friends is not
– Credibility, legitimacy & utility of adoption usually
increase with the number of prior adopters
*Centola, D. and M. Macy. 2007. “Complex Contagions & the
Weakness of Long Ties.” American Journal of Sociology 113:702-34
42
Maybe It’s Not Such a Small World
After All?
 Information and disease benefit from
“weak ties” that create shortcuts
– A single contact is sufficient for transmission
– Clustering is therefore redundant
 Social contagions benefit from clustering
– “Redundancy” provides social reinforcement
– Long-range ties inform but do not persuade
43
1000000
Timesteps
100000
100000
Simple contagion that requires adoption by 1 neighbor
10000
0
(High
Clustering)
.1
.2
.3
.4
.5
.6
Proportion of Random Ties
.7
.8
.9
1
(No
Clustering)
Random ties promote the spread of information (lower is faster)
44
10000000
Social contagion that requires adoption by 3 neighbors
Phase transition in the social fabric:
Contagion can no longer spread
Social contagion that requires adoption by 2 neighbors
Timesteps
1000000
100000
Simple contagion that requires adoption by 1 neighbor
10000
0
(High
Clustering)
.1
.2
.3
.4
.5
.6
.7
Proportion of Random Ties
.8
.9
1
(No
Clustering)
But not the spread of social contagions
45
Small Worlds in a Bigger Picture
 Social life is hard to observe
 You can interview friends, but you cannot
interview a friendship
– Fleeting interaction
– In private
– Tedious to record over time, especially in large
groups
46
Why This is Changing
 Humans increasingly interact publicly
online
– Web pages, Facebook, blogs, wikis, games
– Computer-mediated interaction leaves digital
traces
– New era of “connectionist” social science?
•
•
•
•
Interactions among people, not just variables
Networks, not just aggregates of individuals
Dynamics, not just comparative statics
Links the talents & tools of social, computer, and
information scientists
47
 Some closing observations
 What’s next
48
Observations
 What does it mean to do interdisciplinary
work with a dozen faculty across such
broad range of fields?
– Sociology, economics, communications, social
psychology, information science, computer
science
 More than joint projects across disciplinary
boundaries – catalyst for research
– Investigations deeply informed and motivated
by research of members in other fields – but
published in established (disciplinary) venues
49
Observations
 Importance of residential year, with lead-in
and follow-up years
– Build deeper ties and understanding across
disciplines through seminars, visitors,
workshops, proposals, informal discussion
– Exposure to both classical literature and
current work in several areas
 Educational initiatives at both graduate
and undergraduate level also engage team
members in broader understanding
– Research that happened as a result
50
Observations
 Qualitative change in external visibility of
Cornell in networks area
– In both social sciences and computer science
– Had good basis for this in prior activities by
various individuals – both on team and others
– Institutional commitment and increased
activity level both important for the boost
 Holding interdisciplinary workshops with
the best people in the world – they leave
impressed with Cornell
51
What’s Next
 The team, plus a number of others, is
planning to continue working together
– The Information Science program provides a
natural inter-disciplinary venue for continued
interaction
 We are seeking large-scale external
funding for this research
– NSF CISE Expeditions proposal would be 5
years at $2M/yr
– Will pursue that program and others at similar
scale
52
What’s Next
 Build on the increased visibility and
momentum in research activity
– Long-term institutional impact
 Best way we see to do this is coordinated
faculty hiring in networks area
– Joint appointments, or joint recruiting
committees for single department hires
53
 We want to give our thanks to the ISS for
supporting this project!
 Thanks also to Microsoft for additional
support of postdocs and workshops
54