Designing Classes and Programs - Duke University

Designing Classes and Programs - Duke University

Social Networks as a Foundation for Computer Science Jeffrey Forbes Social Networks, CAARMS 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, nontechnical What can we do to ensure the ongoing success of our academic discipline? Look inward, look to others Social Networks, CAARMS 2006 2 Acknowledgements

Social Networks/Broadening Participation group: Owen Astrachan developed most of 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, CAARMS 2006 3

Social Networks, CAARMS 2006 4 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, CAARMS 2006 5 WWDD? Social Networks, CAARMS 2006 6 Questions and Answers

Judge a man by his questions rather than by his answers Voltaire Social Networks, CAARMS 2006 7 History and Computer Science Those who cannot remember the past are condemned to repeat it.

Dont know much about history, dont know much about biology, dont know much about a science book Social Networks, CAARMS 2006 8 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 John, McCarthy, Information, Chapter available for the asking. 1, 1966 Social Networks, CAARMS 2006 9 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, CAARMS 2006 10 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, CAARMS 2006 11 What has changed in 20 years? Machines Characteristics and Availability

Internet Availability, IM, web, Google, Students Comfort with technology, Expectations Social Networks, CAARMS 2006 12 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, CAARMS 2006 13 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, Head of Physics Instruction Social Networks, CAARMS 2006 14 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 timetraveler. " Greg Wray, Director of Undergraduate Studies, Biology Social Networks, CAARMS 2006 15 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, CAARMS 2006 16 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, CAARMS 2006

17 Changes in Computer Science? Social Networks, CAARMS 2006 18 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 havent changed, is it because of a solid bedrock of principles that endures? Or because were lazy, goodfor-nothing, Social Networks, CAARMS 2006 19 What is CS? Who wants to study it? Why do they want to? Social Networks, CAARMS

2006 20 Social Networks, CAARMS 2006 21 NY Times in 1984 Social Networks, CAARMS 2006 22 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, CAARMS 2006

23 Social Networks, CAARMS 2006 24 Occupational Distribution of Projected S&E Job Openings 2002-2012 Engineers Information Technology Life Scientists Physical Scientists Natural

Science Managers John Sargent, US Department of Commerce, 2004 2006 25 Social Networks, CAARMS 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 Engineering Physical Sciences Computer Sciences Biological / Agricultural Sciences John Sargent, US Department of Commerce, 2004 Social Networks, CAARMS 2006

26 Demographics: 18 - 24 year olds White Asian/ Pacific Islande r Hispani c African American Native American 2000

66% 4% 15% 14% 1% 2010 63% 5% 17% 14%

1% 2025 55% 7% 22% 15% 1% Social Networks, CAARMS 2006 US Census Bureau

27 Bachelors Degrees from Doctoral Institutions Social Networks, CAARMS 2006 28 How are Black students doing? Bachelor's Degrees Earned 5,000 Math 4,000

CS 3,000 Math - Male 2,000 CS - Male Math - Female 1,000 Degrees Award 0 CS - Female 1992 1994 1996 1998 2001 Year

Social Networks, CAARMS 2006 29 How are Black students doing? (2) Master's Degrees Earned 600 Math 500 CS 400 Math - Male

300 CS - Male 200 Degrees 100 Math - Female CS - Female 0 1992 1993 1994 1995 1996 1997 1998 2000

2001 Year Social Networks, CAARMS 2006 30 How are black students doing? (3) PhD Degrees Earned 20 Math 15 CS Math - Male

10 CS - Male Degrees 5 Math - Female CS - Female 0 1992 1993 1994 1995 1996 1997 1998 2000 2001

Year Social Networks, CAARMS 2006 31 Awarded Degrees in CS B.A./ B.S. M.S. Ph.D. Female 28%

34% 23% White 57% 53% 76% African American 10% 8% 3%

5% 5% 2% .6% .7% .2% Hispanic Native American / Alaskan Native Persons with Disabilities 1%

Women, Minorities, and with Disabilities in S&E, 2004 (200132data) SocialPersons Networks, CAARMS 2006 Tough stats Between 1970 and 2001, CS/CE doctorates 8,913 to whites 154 to blacks 8,915 tenure-track faculty at 177 departments 497 Women

63 Hispanic* 32 African American* 6 Native Americans* 2003 Taulbee Data Social Networks, CAARMS 2006 33 More local

Social Networks, CAARMS 2006 34 Social Networks, CAARMS 2006 35 Social Networks, CAARMS 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, CAARMS 2006 37

Social Networks, CAARMS 2006 38 If you dont take a course in CS, you wont major in it. Social Networks, CAARMS 2006 39 Who's going to College? Social Networks, CAARMS

2006 40 Who's going to College? Social Networks, CAARMS 2006 41 Who's going to College? Social Networks, CAARMS 2006 42

How do we get Students into the CompSci Tent? Social Networks, CAARMS 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, CAARMS 2006 44 A Future for Computer Science? Social Networks, CAARMS 2006

45 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, CAARMS 2006 46 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, CAARMS 2006 47

What does the Internet look like? Social Networks, CAARMS 2006 48 Social Networks, CAARMS 2006 49 US Power Grid Social Networks, CAARMS 2006

50 Business & Economic Networks Example: eBay bidding vertices: eBay users links: represent bidder-seller or buyerseller 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, CAARMS 2006 51 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, CAARMS 2006 52 Enron Social Networks, CAARMS 2006 53 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, CAARMS

2006 54 Social Networks, CAARMS 2006 55 Acquaintanceship & more Social Networks, CAARMS 2006 56 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, CAARMS

2006 57 Web-based social networks Myspace Friendster Black Planet Facebook

73,000,000 23,000,000 21,000,000 17,000,000 8,000,000 Whos using these, what are they doing, how often are they doing it, why are they doing it? Social Networks, CAARMS 2006 58 Golbecks 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 dont suffice Social Networks, CAARMS 2006

59 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 30-100 matches Graph degrees/friends, what is

distribution? Social Networks, CAARMS 2006 60 CompSci 1: Overview CS0 Audioscrobbler and Collaborative filtering What is a neighbor? What is the network? Social Networks, CAARMS 2006 61

What can we do with real data? How do we find a graphs 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, CAARMS

2006 62 My recommendations at Amazon Social Networks, CAARMS 2006 63 And again Social Networks, CAARMS 2006 64

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, CAARMS 2006 65 Memory-based methods Store all user votes and generalize from them to predict vote for new item Predicted vote of active user a for item j: where there are n users with non-zero

weights, vi,j is the vote of user i and item j, is a normalizing factor, w() is a weighting function between users Distance metric Correlation or similarity Social Networks, CAARMS 2006 66 Computing weights - Cosine Correlation In information retrieval, documents are

represented as vectors of word frequencies For CF, we treat preferences as vector Documents -> users Word frequencies -> votes Similarity is then the cosine between two vectors Dot product of the vectors divided by the product of their magnitudes Social Networks, CAARMS 2006 67

Computing weights - Pearson & Spearman correlation Pearson Correlation First used for CF in GroupLens project [Resnick et al., 1994] Relatively efficient to calculate incrementally Spearman Correlation same as Pearson but calculations are done on rank of va,j and vi,j Social Networks, CAARMS 2006 68

Model-based methods Really what we want is the expected value of the users vote Cluster Models Users belong to certain classes in C with common tastes Naive Bayes Formulation Calculate Pr(vi|C=c) from training set Bayesian Network Models Social Networks, CAARMS

2006 69

Recently Viewed Presentations

  • Workplace Exposure Assessment and Field Monitoring Strategies

    Workplace Exposure Assessment and Field Monitoring Strategies

    Standard pitot tube consists of an impact tube with an opening facing axially into the flow and a concentric static pressure tube with eight holes spaced equally around in a plane that is eight diameters from opening. The difference between...
  • Mass Production & Consumption

    Mass Production & Consumption

    The next piece is by Damien Hirstis called Mother and Child Divided, ... Norman Rockwell's image of "Dick and Jane" and Tina Turner's lyrics from the Mad Max movie set in a post-nuclear war future. ... MASS PRODUCTION & CONSUMPTION....
  • Temperature Fundamentals - Daum

    Temperature Fundamentals - Daum

    Hysterisis is the difference in the mean values of the two direction dependent output ranges when arriving at a target temperature in repetitive cycles from both directions. ... It may use platinum, nickel or copper for its element. A PRT...
  • Unit 2: Cells

    Unit 2: Cells

    Their theory accepted the first two tenets of modern cell theory. In 1855, Rudolf Virchow concluded that all cells come from pre-existing cells. Since 1855 when Virchow introduced the ideas, the cell theory has been supported by thousands of experiments...
  • PowerPoint-presentatie


    Ontwikkelingspsychologie. Ontwikkelingspsychologie = de psychologie van de ontwikkeling van de persoonlijkheid. Author: L. Buter Created Date: 11/15/2015 05:29:35 Title: PowerPoint-presentatie
  • The British Empire in India

    The British Empire in India

    Muslims don't eat pork & Hindus believe cow is sacred had to break cartridges w/ teeth Soldiers believed they were forced to violate their religion SEPOY MUTINY (or REBELLION) Sepoy Rebellion The Sepoy Rebellion was put down & India became...
  • Music: An Appreciation by Roger Kamien - Novella

    Music: An Appreciation by Roger Kamien - Novella

    Music: An Appreciation 10th Edition by Roger Kamien Part IX Music for Stage and Screen Ch. 1 - Musical Theater Musical, or musical comedy fuses script, acting, speech, music, singing, dancing, costumes, scenery, & spectacle Ch. 2 - Leonard Bernstein...
  • Physics and Chemistry of Solids

    Physics and Chemistry of Solids

    Arial Balloon Arial Black Times New Roman Symbol Comic Sans MS Standarddesign Microsoft Photo Editor 3.0-Photo Microsoft Equation 3.0 Microsoft Photo Editor 3.0 Photo Bitmap Image Thermal Physics Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7...