Applied graph theory (“Social Networks Analysis”)

Concepts

Graph theory:

• nodes and edges
• degree = number of edges for a given node
• isolated nodes
• connected nodes
• hub = well connected node
• Scale-free networks = average number of nodes stays constant
• preferential attachment:
• the fraction of nodes with k edges:
• a long tail distribution
• Degree of distribution

SNAs on YouTube

• A documentary on networks, social and otherwise_Part 1 – http://www.youtube.com/watch?v=RcCpEf6_Ofg
• A documentary on networks, social and otherwise_Part 2 – http://www.youtube.com/watch?v=n1-nfySqf9M
• A documentary on networks, social and otherwise_Part 3 – http://www.youtube.com/watch?v=61a_uTmVk0c
• A documentary on networks, social and otherwise_Part 4 – http://www.youtube.com/watch?v=nIQfuaymmdY
• Networks Understanding Networks, Pt. 1: Welcome by Nicholas Negroponte, Joi Ito, and César Hidalgo – http://www.youtube.com/watch?v=mwIjcv7OWMo
• Networks Understanding Networks, Pt. 2: Ed Boyden – http://www.youtube.com/watch?v=24eWSvqy7nU
• Networks Understanding Networks, Pt. 3: Sandy Pentland – http://www.youtube.com/watch?v=9S5LW4xfAw4
• Networks Understanding Networks, Pt. 4: Ricardo Hausmann – http://www.youtube.com/watch?v=496ujSBhVpM
• Networks Understanding Networks: Pt. 5, Joi Ito on Meeting Mechanics – http://www.youtube.com/watch?v=95EaNrLVm-U
• Networks Understanding Networks, Pt. 6: Albert-László Barabási – http://www.youtube.com/watch?v=ni_A2bAkUww
• Networks Understanding Networks, Pt. 7: Kent Larson – http://www.youtube.com/watch?v=OVPbaj6yny0
• Networks Understanding Networks, Pt. 8: Wrap-Up, Day One – http://www.youtube.com/watch?v=rw9MVvdVMJg
• Networks Understanding Networks, Pt. 9: Day 2 Welcome, Joi Ito and César Hidalgo – http://www.youtube.com/watch?v=tH8FqyhPWZQ
• Networks Understanding Networks, Pt. 10: Nicholas Christakis – http://www.youtube.com/watch?v=udQn3R1zrW8
• Networks Understanding Networks, Pt. 11: John Moore – http://www.youtube.com/watch?v=0cxvivwUtvQ
• Networks Understanding Networks, Pt. 12: Neri Oxman – http://www.youtube.com/watch?v=x4F0bdr9It0
• Networks Understanding Networks, Pt. 13: Panel on Open Innovation and Creativity – http://www.youtube.com/watch?v=SEMTG-tCU58
• Networks Understanding Networks, Pt. 14: Sep Kamvar – http://www.youtube.com/watch?v=SaONPh4C4j0
• Networks Understanding Networks, Pt. 15: Ethan Zuckerman – http://www.youtube.com/watch?v=G28FLepdeWY
• Networks Understanding Networks, Pt. 16: Wadah Khanfar and Closing Remarks – http://www.youtube.com/watch?v=c65jOne_Ksk

Six degrees of separation, Small Worlds, Kevin Bacon metric, Erdos metric, etc

• Six Degrees: from Kevin Bacon to Network Theory – http://www.youtube.com/watch?v=5BdQxvHtMIQ
• Six Degrees of Kevin Bacon: Inside the Game – http://www.youtube.com/watch?v=vOUdy2J0lfU
• Six degrees of Separation – http://www.youtube.com/watch?v=9nAIdxuAESU
• Small world experiment – http://www.youtube.com/watch?v=V2biPHBGm3c
• Small-World Networks: “Six-degrees of separation” – John D Barrow Gresham College maths lecture – http://www.youtube.com/watch?v=EVhx96Oml3U
• It’s a small world! (Stories from a connected world) – http://www.youtube.com/watch?v=NRWSF1c0Ez0 | http://www.youtube.com/watch?v=61a_uTmVk0c

Books

• “Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life” by Albert-László Barabási: home page – http://barabasilab.com/LinkedBook/ | at Amazon – http://www.amazon.com/Linked-Everything-Connected-Business-Everyday/dp/0452284392 | at Google books – http://books.google.com/books/about/Linked.html?id=6PVN2-ihczYC | at WikiPedia – http://en.wikipedia.org/wiki/Linked:_The_New_Science_of_Networks
• “Connected – The Surprising Power of Our Social Networks and How They Shape Our Lives” by Nicholas A. Christakis and James H. Fowler: http://connectedthebook.com/| excerpt –http://connectedthebook.com/pdf/excerpt.pdf
• “Networks, Crowds , and Markets – Reasoning about a Highly Connected World” – by David Easey and Jon Kleinberg – http://www.cs.cornell.edu/home/kleinber/networks-book/

Authors and Sites

• Albert-László Barabási
  • Albert-László Barabási (@WikiPedia) – http://en.wikipedia.org/wiki/Albert-L%C3%A1szl%C3%B3_Barab%C3%A1si
  • Albert-László Barabási – at TEDMED 2012 – http://www.youtube.com/watch?v=10oQMHadGos
  • Albert-László Barabási – Q&A at TEDMED 2012 – http://www.youtube.com/watch?v=SkurtDHFnac
  • Authors@Google: Albert László Barabási – http://www.youtube.com/watch?v=7YFNf1ix_yY
  • “Network Science: from Structure to Control”: Albert-László Barabási at IMT – http://www.youtube.com/watch?v=EeldZm4vMw4
  • GEM 2012: Albert-Laszlo Barabasi on Laws of Networks – http://www.youtube.com/watch?v=MNLSMGvbAUc
  • Networks Understanding Networks, Pt. 6: Albert-László Barabási – http://www.youtube.com/watch?v=ni_A2bAkUww
  • IMA Public Lecture : Network Science: From the Web to Human Diseases, Albert-László Barabási – http://www.youtube.com/watch?v=KOfRITP9o5U
  • Albert-Laszlo Barabasi – Systems Biology Defined – http://www.youtube.com/watch?v=BGMuELnPJDw
  • Albert-Laszlo Barabasi – Web Science Meets Network Science Workshop – http://www.youtube.com/watch?v=qfoE2kWHmI4
  • Network Science by Albert Laszlo Barabasi (Part 4 of 13) – http://www.youtube.com/watch?v=NCq1kpuCUq4
• Nicholas A. Christakis:
  • Nicholas A. Christakis (@WikiPedia) – http://en.wikipedia.org/wiki/Nicholas_A._Christakis
  • Nicholas Christakis: The hidden influence of social networks – http://www.youtube.com/watch?v=2U-tOghblfE
  • Nicholas Christakis: The Sociological Science Behind Social Networks and Social Influence – http://www.youtube.com/watch?v=wadBvDPeE4E
  • Christakis, NA; Fowler, JH (26 July 2007). “The Spread of Obesity in a Large Social Network Over 32 Years” (PDF). New England Journal of Medicine 357 (4): 370–379. doi:10.1056/NEJMsa066082. PMID 17652652. – http://christakis.med.harvard.edu/pdfs/078.pdf
  • Christakis, NA; Fowler, JH (22 May 2008). “Quitting in Droves: Collective Dynamics of Smoking Behavior in a Large Social Network” (PDF). New England Journal of Medicine 358 (21): 2249–2258. doi:10.1056/NEJMsa0706154. PMC 2822344. PMID 18499567. – http://web.archive.org/web/20090219071240/http://christakis.med.harvard.edu/pdfs/083.pdf
  • Fowler, J. H; Christakis, N. A (3 January 2009). “The Dynamic Spread of Happiness in a Large Social Network” (PDF). British Medical Journal 337 (768): a2338. doi:10.1136/bmj.a2338. PMC 2600606. PMID 19056788. – http://web.archive.org/web/20090219071245/http://christakis.med.harvard.edu/pdfs/095.pdf
  • Fowler, JH; Dawes, CT; Christakis, NA (10 February 2009). “Model of genetic variation in human social networks” (PDF). Proceedings of the National Academy of Sciences 106 (6): 1720–1724. doi:10.1073/pnas.0806746106. PMC 2644104. PMID 19171900. – http://web.archive.org/web/20091229064853/http://christakis.med.harvard.edu/pdfs/096.pdf
• James Fowler – http://fowler.ucsd.edu/
• Jon Kleinberg – http://www.cs.cornell.edu/home/kleinber/
• An Introductory Course on Network Analysis – https://sites.google.com/site/networkanalysisacourse/schedule/an-introduction/scale-free-networks
• Scale Free Networks (at Facebook) – https://www.facebook.com/pages/Scale-free-network/110363432347522
• Scale Free Networks (at C2 Wiki) – http://c2.com/cgi/wiki?ScaleFreeNetworks
• Papers & Talks – http://web.archive.org/web/20041102121249/http://www.nd.edu/~networks/papers.htm
• Scale-free network (at WikiPedia) – https://en.wikipedia.org/wiki/Scale-free_network
• Barabási–Albert model (at WikiPedia) – http://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model
• “This Man Could Rule the World Data Age (How Albert-László Barabási went from mapping systems to controlling them)” by Gregory Mone (11.02.2011.11.02) – http://www.popsci.com/science/article/2011-10/man-could-rule-world
• Generalized scale-free model (at WikiPedia) – http://en.wikipedia.org/wiki/Generalized_scale-free_model
• Complex network (at WikiPedia) – http://en.wikipedia.org/wiki/Complex_network
• Panayiotis Tsaparas (University of Ioannina; Computer Science Department)
  • Course: “Online Social Networks and Media” – Fall 2013 – http://www.cs.uoi.gr/~tsap/teaching/cs-l14/. Previous versions of the same course:
    • Course: “Information Networks” – Spring 2005 – http://www.cs.uoi.gr/~tsap/teaching/InformationNetworks/
  • “Information Networks – References” – http://www.cs.uoi.gr/~tsap/teaching/InformationNetworks/references.html
• Jon Kleinberg:
  • Course: “The Structure of Information Networks” – Computer Science 685 – Fall 2002 – http://www.cs.cornell.edu/Courses/cs685/2002fa/
  • Course: “Algorithms for Information Networks” (Carnegie Mellon, Spring 2005) – http://www.cs.cornell.edu/home/kleinber/sp05course.html

---

Papers

• “Power laws, Pareto distributions and Zipf’s law” by M.E.J. Newman (arXiv) – http://arxiv.org/abs/cond-mat/0412004
  • When the probability of measuring a particular value of some quantity varies inversely as a power of that value, the quantity is said to follow a power law, also known variously as Zipf’s law or the Pareto distribution. Power laws appear widely in physics, biology, earth and planetary sciences, economics and finance, computer science, demography and the social sciences. For instance, the distributions of the sizes of cities, earthquakes, solar flares, moon craters, wars and people’s personal fortunes all appear to follow power laws. The origin of power-law behaviour has been a topic of debate in the scientific community for more than a century. Here we review some of the empirical evidence for the existence of power-law forms and the theories proposed to explain them.
  • more papers by M.E.J. Newman at arXiv – arxiv.org/find/cond-mat/1/au:+Newman_M/0/1/0/all/0/1