CS 432/532 Web Science
Spring 2018
http://anwala.github.io/lectures/cs532-s18/
Assignment #5
Due: 11:59pm March 7
(10 points)
1. We know the result of the Karate Club (Zachary, 1977) split.
Prove or disprove that the result of split could have been predicted
by the weighted graph of social interactions. How well does the
mathematical model represent reality?
Generously document your answer with all supporting equations, code,
graphs, arguments, etc.
Clues:
1. Draw original Karate club graph (two connected components) after split (Week 6 lecture, slide 98).
2. Run multiple iterations of graph partioning algorithm (e.g., Girvan-Newman Algorithm) on experimental Karate club graph until the graph splits into two connected components.
3. Compare the connected components of the experimental graph (in 2.) with the original connected components of the split Karate club graph (in 1.). Are they similar?
Useful sources include:
* Original paper
http://aris.ss.uci.edu/~lin/76.pdf
* Week 6 Slides:
https://docs.google.com/presentation/d/1ihf6N8bHgzM5VLAyHkmF_i5JGUBVpCSdsvYpk8XgHwo/edit?usp=sharing
* Slides
http://www-personal.umich.edu/~ladamic/courses/networks/si614w06/ppt/lecture18.ppt
http://clair.si.umich.edu/si767/papers/Week03/Community/CommunityDetection.pptx
* Code and data
https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.generators.social.karate_club_graph.html
https://networkx.github.io/documentation/networkx-1.9/examples/graph/karate_club.html
http://nbviewer.ipython.org/url/courses.cit.cornell.edu/info6010/resources/11notes.ipynb
http://stackoverflow.com/questions/9471906/what-are-the-differences-between-community-detection-algorithms-in-igraph/9478989#9478989
http://stackoverflow.com/questions/5822265/are-there-implementations-of-algorithms-for-community-detection-in-graphs
http://konect.uni-koblenz.de/networks/ucidata-zachary
http://vlado.fmf.uni-lj.si/pub/networks/data/ucinet/ucidata.htm#zachary
https://snap.stanford.edu/snappy/doc/reference/CommunityGirvanNewman.html
http://igraph.org/python/doc/igraph-pysrc.html#Graph.community_edge_betweenness
(extra credit, 10 points)
2. Use D3.js's force-directed graph layout to draw the Karate Club Graph before split. Color the nodes according to the factions they belong to (John A or Mr. Hi). After a button is clicked, split the graph based on the original graph split. Include a link to the HTML/JavaScript files in your report and all necessary screenshots.
See: https://bl.ocks.org/mbostock/4062045
https://d3js.org/
(extra credit, 3 points)
3. We know the group split in two different groups. Suppose the
disagreements in the group were more nuanced -- what would the clubs
look like if they split into groups of 3, 4, and 5?