Transcript Social networks Example

Social Networks
as a Foundation
for Computer Science
Owen Astrachan, Jeff Forbes, Susan Rodger,
Casey Alt, Richard Lucic, Robert Duvall
http://www.cs.duke.edu/csed/harambenet
Social Networks and More: Harambenet 2006
1
Where are we going … Questions

What should our concerns be for those choosing to
major in Computer Science?
 courses, research, jobs, …

Should we be concerned by the precipitous decline
in those taking our courses or majoring or …?
 majors, technical students, non-technical …

What can we do to ensure the ongoing success of
our academic discipline?
 Look inward, look to others
Social Networks and More: Harambenet 2006
2
Acknowledgements


Social Networks/Broadening Participation group:
 Jeff Forbes helped with this talk
 Casey Alt, Richard Lucic, Susan Rodger
 Students: Ben Spain & Dametrious Peyton
Drawn from the work of:
 Michael Kearns, UPenn
 Eytan Adar, formerly of HP Labs
 John Breese, David Heckerman, Microsoft Research
 Jonathan Herlocker, Oregon State University
 Thomas Hoffman, Brown University
 Marti Hearst, UC Berkeley
 Jennifer Golbeck, University of Maryland
Social Networks and More: Harambenet 2006
3
Social Networks and More: Harambenet 2006
4
WWDD?
Social Networks and More: Harambenet 2006
5
Questions
If you gotta ask, you’ll never know
Louis Armstrong: “What’s jazz?”
If you gotta ask, you ain’t got it
Fats Waller: “What’s rhythm?”
What questions did you ask in school
today?
Arno Penzias via Isaac Isadore Rabi
Social Networks and More: Harambenet 2006
6
Questions and Answers

Judge a man by his questions rather
than by his answers
Voltaire
Social Networks and More: Harambenet 2006
7
Computer Science

What is the foundation of computer science?
 Historically, now, in the future

What changes are here, on the horizon?
 From theory to practice to education

Can we relate to what and how students learn?
 Is every generation different, the same, …
Social Networks and More: Harambenet 2006
8
History and Computer Science

Those who cannot remember the past are
condemned to repeat it.

Don’t know much about history, don’t know much
about biology, don’t know much about a science
book
Social Networks and More: Harambenet 2006
9
Who, when?
“No stretching … is required to envision computer
consoles installed in every home.
Everyone will have better access to the Library of
Congress than the librarian himself now has.
Full reports on current events, whether baseball
scores, the smog index in Los Angeles or the
minutes of the 178th Korean Truce Commission
will be available for the asking.”
John, McCarthy, Information, Chapter 1, 1966
Social Networks and More: Harambenet 2006
10
You win some, you lose some
People will soon become discontented with the
“canned” programs available; they will want to
write their own. The ability to write a computer
program will be as widespread as the ability to
drive a car.
Not knowing how to program will be like living in a
house full of servants and not speaking their
language.
Many people can write simple programs after an hour
or two of instruction. … Programming is far easier
to learn than a foreign language or algebra.
Social Networks and More: Harambenet 2006
11
kentlew.com
Then and Now
Bailey, SIGCSE 1972
It is remarkable that the majority of students can
indeed handle fairly complex (Fortran) I/O by the
end of the first six lessons, even though they have
not actually been formally taught how to do it.
Roberts et al, SIGCSE 2006
The problem most often cited by those attempting to
teach Java to novices is the lack of a simple input
mechanism,
Social Networks and More: Harambenet 2006
12
What has changed in 20 years?

Machines
 Characteristics and Availability

Internet
 Availability, IM, web, Google, …

Students
 Comfort with technology, Expectations
Social Networks and More: Harambenet 2006
13
Teaching Compsci in 1984






64K memory, 128K
extended
8-bit, 1 Mhz 6502 processor
5Mb drive: $3500
UCSD Pascal: >$100
Owen's machine: $3000
$677.80 in 1984 has $1200
"purchase power" in 2003

http://eh.net/hmit/ppowerusd/
Social Networks and More: Harambenet 2006
14
Typical machine in 2006?





Social Networks and More: Harambenet 2006
1 Gb memory
3 GHz, 32-bit chip
 Cache, …
160 Gb disk
Lots of free resources
 Good academic
pricing
Under $600 (priced 6/19/06)
15
The more things change…?
Assume I took your first
course(s) in 1984 and
understood the concepts
so completely that I could
still get a 100 on the final
from 1984 if I took it today
(e.g., I've been in a
cryogenic chamber). How
would I do on the 2004
final exam?
Social Networks and More: Harambenet 2006
16
What has changed in Physics?
"You'd get a 100 plus or minus sigma. Intro classical
physics hasn't really changed that much over the last
100 years. In graduate level e.g. E&M or quantum
classes I think ditto, although sigma would be bigger
(and might depend more on the instructor variation
than on any real variation in the material). The main
difference is, I think, that your chances of GETTING
100 now would be much higher."
Rob Brown,
Poohbah of Physics Instruction
Social Networks and More: Harambenet 2006
17
What has changed in Biology?
"The basic principles and concepts of biology haven't
changed much in 20 years. What has changed relates
to specific content, and in this arena the changes
have been enormous. 20 years ago, we barely knew
how to sequence DNA; today information of this kind
has had a major impact on just about every topic in
the biological sciences. Thus, some questions on an
exam today would address topics that would be
completely unfamiliar to a 1984 time-traveller. "
Greg Wray,
Director of Undergraduate Studies, Biology
Social Networks and More: Harambenet 2006
18
What has changed in Economics?
"… we now cover material that was only introduced in
an advanced or intermediate course in 1984. In 1984
we spent the bulk of the time dealing with the
Keynesian model and virtually no dialogue about
supply side policies. Now the Keynesian stuff is a
small subset of a much broader exposure to
Aggregate demand and supply… Also there is more
international coverage now - as opposed to 20 years
ago for obvious reasons."
Lori Leachman,
Director of Undergraduate Studies, Economics
Social Networks and More: Harambenet 2006
19
What has changed in Calculus?
We have two varieties of calculus courses, the lab courses and the
traditional ... The latter two have not changed significantly in
decades, and I think that a student who fared well on the 1984
exam in those courses would do well today, and vice versa.
[In the lab courses] You would ace about half the exam. The other
half would be unfamiliar to you. For example, you would
probably not know how to answer a problem on modeling a set
of data, creating an approximation using Euler's method,
interpreting derivatives in the context of applications in other
fields, or giving explanations of ideas …
Lewis Blake,
Supervisor of First-year Instruction
Social Networks and More: Harambenet 2006
20
Changes in Computer Science?
Social Networks and More: Harambenet 2006
21
Changing CS? Rock, Hard place

If Computer Science has changed drastically is it to
keep up with fads and stylistic changes or because
of fundamental changes in the discipline?

Are we leveraging the technological and intellectual
resources at our disposal

If we haven’t changed, is it because of a solid
bedrock of principles that endures? Or because
we’re lazy, good-for-nothing, …
Social Networks and More: Harambenet 2006
22
What is CS? Who wants to
study it? Why do they want
to?
Social Networks and More: Harambenet 2006
23
Social Networks and More: Harambenet 2006
24
NYTimes in 1984
Social Networks and More: Harambenet 2006
25
What is CS? Why study it?
Do we have Physics (Math, …) Envy?
“It's hard for voice over Internet Protocol or
e-commerce to compete with finding the age
of the universe,”
Peter Lee, CMU


Does familiarity breed contempt?
 What was different in 1984 than today?
Social Networks and More: Harambenet 2006
26
Social Networks and More: Harambenet 2006
27
What is Computer Science?
What is the central core of the subject? What
is it that distinguishes it from the separate
subjects with which it is related?
What is the linking thread
which gathers these
disparate branches into a
single discipline? My
answer to these questions
is simple --- it is the art of
programming a computer.
Social Networks and More: Harambenet 2006
28
Is this Computer Science?
public static void stuff(int n){
doit(n,0,1,2);
}
public static void
doit(int n,int f, int t, int a){
if (n == 1) move(n,f,t);
else {
doit(n-1,f,a,t);
move(n,f,t);
doit(n-1,a,t,f);
}
}
Social Networks and More: Harambenet 2006
29
Occupational Distribution of Projected S&E
Job Openings 2002-2012
Engineers
Information
Technology
Life
Scientists
Physical
Scientists
Natural
Science
Managers
Social Networks and More: Harambenet 2006
30
John Sargent, US Department of Commerce, 2004
Annual Degrees and Job Openings in Broad
S&E Fields
PhD
Master's
Bachelor's
Projected Job Openings
160,000
140,000
120,000
100,000
80,000
60,000
40,000
20,000
Physical Sciences
Engineering
Computer Sciences
Biological /
Agricultural Sciences
31
John Sargent, US Department of Commerce, 2004
Social Networks and More: Harambenet 2006
Demographics: 18 - 24 year olds
White
Asian/
Pacific
Islander
Hispanic
African
American
Native
American
2000
66%
4%
15%
14%
1%
2010
63%
5%
17%
14%
1%
2025
55%
7%
22%
15%
1%
32
Social Networks and More: Harambenet 2006
US Census Bureau
Bachelor’s Degrees from Doctoral
Institutions
Social Networks and More: Harambenet 2006
33
Social Networks and More: Harambenet 2006
34
Social Networks and More: Harambenet 2006
35
Social Networks and More: Harambenet 2006
36
COHFE
Amherst College, Barnard College, Brown
University, Bryn Mawr College, Carleton College,
Columbia University, Cornell University, Dartmouth
College, Duke University, Georgetown University,
Harvard University, Johns Hopkins University,
Massachusetts Institute of Technology, Mount
Holyoke College, Northwestern University, Oberlin
College, Pomona College, Princeton University, Rice
University, Smith College, Stanford University,
Swarthmore College, Trinity College, University of
Chicago, University of Pennsylvania, University of
Rochester, Washington University in St. Louis,
Wellesley College, Wesleyan University, Williams
College, Yale University
Social Networks and More: Harambenet 2006
37
Social Networks and More: Harambenet 2006
38
If you don’t take a course in
CS, you won’t major in it.
Why is the first year different from all other years?
Social Networks and More: Harambenet 2006
39
Who's going to College?
Social Networks and More: Harambenet 2006
40
Who's going to College?
Social Networks and More: Harambenet 2006
41
Who's going to College?
Social Networks and More: Harambenet 2006
42
How do we get Students
into the Compsci Tent?
Why is the first year different from all other years?
Social Networks and More: Harambenet 2006
43
Interdisciplinary minors

At Duke it is difficult to double major in sciences
 Too many requirements, 17 courses in biology

Students are interested in credentials
 No business major/minor, certificate program
(requires intro, capstone, six courses)

Minor requires five courses, double counting ok
 Three courses in CS, two in econ or biology
 From gene to social networks, data mining, …
Social Networks and More: Harambenet 2006
44
Genome Revolution Focus Course

Arts in Contemporay Society, Exploring the Mind,
Evolution and Humankind, 20th Century Europe,
Visions of Freedom, The Genome Revolution and
its Impact on Society, …
 Three of four courses, one writing, two others.
Interdisciplinary 0.5 credit seminar P/F
 Seminars, students live in same dorm
 600+ out of 1600 in FOCUS course

For Genome, 80 applicants for 30 slots, 65% women
 In CS Genomics course 8 women, 9 men
Social Networks and More: Harambenet 2006
45
Simple examples

Given strand of DNA, calculate CG ratio
 Potential source of proteins “CGGATTATC”

Given protein “HLVWW” calculate number of
different DNA strands that could code for it
 64 codons, 20 amino acids

Find heaviest protein in array of proteins
 Given atomic mass of amino acids

Interpret ORF data from NCBI website
Social Networks and More: Harambenet 2006
46
From Algorithms to Objects

Read DNA assumed to be in 5’ to 3’ orientation
 Use BioJava to read via http

Construct reverse complement (3’ to 5’)
 From CAATT produce AATTG

How big is the human genome?
 Runtime of algorithm O(1)
Social Networks and More: Harambenet 2006
47
Computer Science is filled
with real-world examples.
Why is the first year different from all other years?
Social Networks and More: Harambenet 2006
48
Teaching as …
English is not history and
history is not science and
science is not art and art is not
music, and art and music are
minor subjects and English,
history and science major
subjects, and a subject is
something you 'take' and when
you have taken it, you have
'had' it, and if you have 'had' it,
you are immune and need not
take it again." (The Vaccination
Theory of Education?)
Social Networks and More: Harambenet 2006
49
Back to the Future
How will we know when we get there?
Social Networks and More: Harambenet 2006
50
A Future for Computer Science?
Social Networks and More: Harambenet 2006
51
Is there a Science of Networks?

From Erdos numbers to random graphs to Internet
 From FOAF to Selfish Routing: apparent similarities between
many human and technological systems & organization
 Modeling, simulation, and hypotheses
 Compelling concepts
• Metaphor of viral spread
• Properties of connectivity has qualitative and quantitative effects


Computer Science?
From the facebook to tomogravity
 How do we model networks, measure them, and reason about
them?
 What mathematics is necessary?
 Will the real-world intrude?
Social Networks and More: Harambenet 2006
52
Physical Networks

The Internet
 Vertices: Routers
 Edges: Physical connections

Another layer of abstraction
 Vertices: Autonomous systems
 Edges: peering agreements
 Both a physical and business network
Other examples



US Power Grid
Interdependence and August 2003 blackout
Social Networks and More: Harambenet 2006
53
What does the Internet look like?
Social Networks and More: Harambenet 2006
54
Social Networks and More: Harambenet 2006
55
US Power Grid
Social Networks and More: Harambenet 2006
56
Business & Economic Networks




Example: eBay bidding
 vertices: eBay users
 links: represent bidder-seller or buyer-seller
 fraud detection: bidding rings
Example: corporate boards
 vertices: corporations
 links: between companies that share a board member
Example: corporate partnerships
 vertices: corporations
 links: represent formal joint ventures
Example: goods exchange networks
 vertices: buyers and sellers of commodities
 links: represent “permissible” transactions
Social Networks and More: Harambenet 2006
57
Content Networks


Example: Document similarity
 Vertices: documents on web
 Edges: Weights defined by similarity
 See TouchGraph GoogleBrowser
Conceptual network: thesaurus
 Vertices: words
 Edges: synonym relationships
Social Networks and More: Harambenet 2006
58
Enron
Social Networks and More: Harambenet 2006
59
Social networks

Example: Acquaintanceship networks
 vertices: people in the world
 links: have met in person and know last names
 hard to measure

Example: scientific collaboration
 vertices: math and computer science researchers
 links: between coauthors on a published paper
 Erdos numbers : distance to Paul Erdos
 Erdos was definitely a hub or connector; had 507 coauthors
How do we navigate in such networks?

Social Networks and More: Harambenet 2006
60
Social Networks and More: Harambenet 2006
61
Acquaintanceship & more
Social Networks and More: Harambenet 2006
62
Network Models (Barabasi)

Differences between Internet, Kazaa, Chord
 Building, modeling, predicting

Static networks, Dynamic networks
 Modeling and simulation

Random and Scale-free
 Implications?

Structure and Evolution
 Modeling via Touchgraph
Social Networks and More: Harambenet 2006
63
Web-based social networks
http://trust.mindswap.org






Myspace
Passion.com
Friendster
Black Planet
Facebook
73,000,000
23,000,000
21,000,000
17,000,000
8,000,000
Who’s using these, what are they doing, how often
are they doing it, why are they doing it?
Social Networks and More: Harambenet 2006
64
Golbeck’s Criteria

Accessible over the web via a browser

Users explicitly state relationships
 Not mined or inferred

Relationships visible and browsable by others
 Reasons?

Support for users to make connections
 Simple HTML pages don’t suffice
Social Networks and More: Harambenet 2006
65
CSE 112, Networked Life (UPenn)

Find the person in Facebook with the most friends
 Document your process

Find the person with the fewest friends
 What does this mean?

Search for profiles with some phrase that yields 30100 matches
 Graph degrees/friends, what is distribution?
Social Networks and More: Harambenet 2006
66
CompSci 1: Overview CS0

Audioscrobbler and last.fm
 Collaborative filtering
 What is a neighbor?
 What is the network?
Social Networks and More: Harambenet 2006
67
What can we do with real data?

How do we find a graph’s diameter?
 This is the maximal shortest path between any
pair of vertices
 Can we do this in big graphs?

What is the center of a graph?
 From rumor mills to terrorists
 How is this related to diameter?

Demo GUESS (as augmented at Duke)
 IM data, Audioscrobbler data
Social Networks and More: Harambenet 2006
68
Collaborative Filtering

Goal: predict the utility of an item to a particular user based on
a database of user profiles
 User profiles contain user preference information
 Preference may be explicit or implicit
• Explicit means that a user votes explicitly on some scale
• Implicit means that the system interprets user behavior or
selections to impute a vote

Problems
 Missing data: voting is neither complete nor uniform
 Preferences may change over time
 Interface issues
Social Networks and More: Harambenet 2006
69
My recommendations at Amazon
Social Networks and More: Harambenet 2006
70
And again…
Social Networks and More: Harambenet 2006
71
Finally, …
Social Networks and More: Harambenet 2006
72
Whose recommendations?
Social Networks and More: Harambenet 2006
73
And again…
Social Networks and More: Harambenet 2006
74
Alan Kay
"Simple things should
be simple. Complex
things should be
possible".
"The best way to
predict the future is to
invent it"
Social Networks and More: Harambenet 2006
75