Mining the Social Web

Networks, Crowds, and Game Theory

CSCI 480, Fall 2017

To the Bottom of the Page

Instructor: Dr. Shieu-Hong Lin

Email:

Class: MW 12:00-1:15 pm at BUSN 210 PC Lab

Dr. Lin Office Hours: Math & CS department at Grove 8.

(i) Tuesday: 1:00-3:30pm, just drop by, no appointment needed

(ii) Monday, Wednesday, Thursday: 3:00~5:00pm: email Dr. Lin in advance to set up an appointment

Important notes:

· Overview of the course: syllabus

· About the weekly progress reports on reading, lab experiments, and coding

*************************************************************************************************

Week 1: Graph Theory and Social Networks: An Overview

Progress report #1on reading, lab experiments, coding: due: Wednesday, Sept. 6

Submit your progress report on Canvas

Reading

· Chapter 1. Overview in Networks, Crowds, and Markets: Reasoning About a Highly Connected World.

· Preface, prelude, Appendix A and C in Mining the Social Web, 2^nd Ed.

· Explore the articles about Facebook news feed and more: 1, 2, 3

Lab experiments

· Install IPython Notebook for Mining the Social Web, 2nd Edition.

Discussion #1 on IPython Notebook: due: Wednesday, Sept. 6

Submit your discussion on Canvas

*************************************************************************************************

Week 2: Basics of Graphs | Twitter and Its API

Progress report #2 on reading, lab experiments, coding: due: Wednesday, Sept. 13

Submit your progress report on Canvas

In-class collaboration on the installation of IPython Notebook Monday, Sept. 11

· William, Matthew, and others who were able to make it work to some extent will (i) demonstrate what they can now do with IPython Notebook and (ii) describe the technical glitches they got over to make something happen.

· Ask questions and get feedback in the class if you have problems to make IPython Notebook work,

Reading

· Chapter 2. Introduction to Graphs in Networks, Crowds, and Markets: Reasoning About a Highly Connected World.

· Roughly browse Chapter 1 (Twitter) of Mining the Social Web, 2^nd Ed.

Lab experiments on graphs and data structures in C++:

· On graphs and Euler circuits

1. Read this Wikipedia article to learn about Euler circuits in graphs. Download this zip file to examine a power point slide set on Euler circuits, a basic code framework folder, a sample executable EulerCircuit.exe, and sample graphs such as graph1.txt and biolaGraph.txt in it.

2. Write down a graph of your choice and encode the adjacency relation between the vertices as a text file myGraph.txt following the format used in graph1.txt and biolaGraph.txt.

3. Run EulerCircuit.exe and use it to find Euler circuits for graphs encoded in graph1.txt, biolaGraph.txt and myGraph.txt.

*************************************************************************************************

Week 3: Strong and Weak Ties | Twitter and Its API

Progress report #3 on reading, lab experiments, coding: due: Wednesday, Sept. 20

Submit your progress report on Canvas

Reading

· Chapter 3. Strong and Weak Ties in Networks, Crowds, and Markets: Reasoning About a Highly Connected World.

· Review Chapter 1 (Twitter) of Mining the Social Web, 2^nd Ed.

· Browse the Wikipedia article on Twitter

Lab experiments with Twitter:

· Create a Twitter account (if you don’t have one yet) and sign in to play with it.

· Play with the sample programs in Chapter 1 (Twitter) of Mining the Social Web.

Lab experiments on graphs and data structures in C++:

· On graphs and Euler circuits

2. Write down a graph of your choice and encode the adjacency relation between the vertices as a text file myGraph.txt following the format used in graph1.txt and biolaGraph.txt.

3. Run EulerCircuit.exe and use it to find Euler circuits for graphs encoded in graph1.txt, biolaGraph.txt and myGraph.txt.

Discussion #2 on graphs and data structures in C++: due: Wednesday, Sept. 20

· Report what you have done and observed in the lab experiments on graphs and Euler circuits above.

· Apply your understanding of C++ STL maps to study the code framework and describe conceptually how you may finish the implementation of the GetOneEulerCircuit method and the StitchNewCycleIntoPartialEulerCircuit method of the Euler solver class in EulerSolver.cpp to make it fully functional.

Submit your discussion on Canvas

*************************************************************************************************

Week 4: More on Strong and Weak Ties | Twitter and Its API

Progress report #4 on reading, lab experiments, coding: due: Wednesday, Sept. 27

Submit your progress report on Canvas

Reading

· Review Chapter 3. Strong and Weak Ties in Networks, Crowds, and Markets: Reasoning About a Highly Connected World.

· Review Chapter 1 (Twitter) of Mining the Social Web, 2^nd Ed.

· Browse about research on the strength of weak ties: 1, 2, 3

Lab experiments on local bridges in graphs using data structures in C++:

· On local bridges as weak ties

1. Develop an algorithm for identifying all local bridges in a graph. Try to analyze the time complexity of your algorithm.

2. Based on the basic code framework folder in the zip file for Euler circuits, try to implement your algorithm for identifying all local bridges in a graph. Here is a sample demo executable about what you may accomplish through your implementation.

Discussion #3 on local bridges in graphs using data structures in C++: due: Wednesday, Sept. 27 open till Oct. 4.

· Report what you have done for finding all local bridges in a graph.

*************************************************************************************************

Week 5: Networks in Their Surrounding Contexts | Facebook and Its API

Progress report #5 on reading, lab experiments, coding: due: Wednesday, Oct. 4.

Submit your progress report on Canvas

Reading

· Browse Chapter 4 Networks in Their Surrounding Contexts in Networks, Crowds, and Markets: Reasoning About a Highly Connected World.

· Browse Chapter 2 (Facebook) of Mining the Social Web, 2^nd Ed.

Lab experiments on local bridges in graphs using data structures in C++:

· On local bridges as weak ties

1. Develop an algorithm for identifying all local bridges in a graph. Try to analyze the time complexity of your algorithm.

2. Based on the basic code framework folder in the zip file for Euler circuits, try to implement your algorithm for identifying all local bridges in a graph. Here is a local-bridge demo executable about what you may accomplish through your implementation.

Discussion #3 on local bridges in graphs using data structures in C++: due: Wednesday, Sept. 27 open till Oct. 4.

· Report what you have done for finding all local bridges in a graph.

Submit your discussion on Canvas

*************************************************************************************************

Weeks 6-7: More on Networks in Their Surrounding Contexts | Facebook and Its API | Torrey Conference

Progress report #6 on reading, lab experiments, coding: due: Wednesday, Oct. 11.

Submit your progress report on Canvas

Progress report #7 on reading, lab experiments, coding: due: Wednesday, Oct. 18.

Submit your progress report on Canvas

Reading

· Read Chapter 4 Networks in Their Surrounding Contexts in Networks, Crowds, and Markets: Reasoning About a Highly Connected World.

· Read Chapter 2 (Facebook) of Mining the Social Web, 2^nd Ed.

Discussion #4 Twitter: due: Wednesday, Oct. 11

· Share with the class about (i) your experiences/understanding of the Twitter API and sample programs in Chapter 1 of "Mining the Social Web" 2nd Ed., (ii) any ideas and experiments you are developing based on ideas from social networks and the Twitter API, and (iii) highlight any technical problems you encountered and describe how you resolved them in the process.

· Submit your discussion on Canvas.

Quiz #1 Finding neighborhood overlapping using data structures in C++: due: Wednesday, Oct. 11. Open till Wednesday Oct. 18.

· Based on the basic code framework folder in the zip file for Euler circuits, please implement an additional option (as shown in the local-bridge demo program here) such that the user can determine the neighborhood overlapping for each pair of vertices u and v where there is an edge (u, v) in a given graph.

· Submission: (i) Compress your entire program folder into a zip file and then upload it through Biola Canvas. (ii) Carefully fill out this self-evaluation report and upload it through Biola Canvas. No need for a peer review for the self-evaluation report.

*************************************************************************************************

Weeks 8-9: Networks: the Surrounding Contexts, Positive and Negative Relationships

Progress report #8-9 on reading, lab experiments, coding: due: Wednesday, Nov. 1. No Penalty till Nov. 8.

Submit your progress report on Canvas

Reading

· Review Chapter 4 Networks in Their Surrounding Contexts in Networks, Crowds, and Markets: Reasoning About a Highly Connected World.

· Read Chapter 5 Positive and Negative Relationships in Networks, Crowds, and Markets: Reasoning About a Highly Connected World.

· Read Chapter 3 (LinkedIn) of Mining the Social Web, 2^nd Ed.

Lab experiments on social-affiliation networks using data structures in C++:

· Download and examine the graph solver framework in C++ in a zip file here (updated 11/6), which implements solutions for both Quiz 1, Discussion #3, and more.

· Implement an option that will take two graphs as two snapshots of an evolving social network and then calculate T(k)’s as defined and described in Section 4.4.

· Devise an approach to extend and enhance the framework above so that we can incorporate additional information about the vertices (nodes). We should be able to label each vertex (node) as either a person or a social focus, which will allow us to use the framework to handle social-affiliation networks described in Chapter 4 Networks in Their Surrounding Contexts. You may add additional data members into the class to make this happens. You also need to devise a file format such that you can record the information of a social-affiliation network in a file.

· Revise the member functions of the graph solver class such that (i) you can properly read the information of a social-affiliation network from a file and (ii) you can take 2 graphs as two snapshots of an evolving social-affiliation network and automatically derive information regarding triadic closure, focal closure, and membership closure as shown in Figures 4.9, 4.10, and 4.11 as described in Section 4.4 in Chapter 4 Networks in Their Surrounding Contexts.

Discussion #5 on social-affiliation networks in graphs using data structures in C++: due: Wednesday, Nov. 8.

· Report your approach and what you are able to accomplish in the lab experiments above.

Submit your discussion on Canvas

*************************************************************************************************

Weeks 10-11: The Structure of the Web

Progress report #10-11 on reading, lab experiments, coding: due: Wednesday, Nov. 22.

Submit your progress report on Canvas

Reading

· Read Chapter 13 The Structure of the Web in Networks, Crowds, and Markets: Reasoning About a Highly Connected World.

Lab experiments on social-affiliation networks using data structures in C++:

· Try to devise an approach to extend and enhance the framework above so that we can incorporate additional information about the vertices (nodes). We should be able to label each vertex (node) as either a person or a social focus, which will allow us to use the framework to handle social-affiliation networks described in Chapter 4 Networks in Their Surrounding Contexts. You may add additional data members into the class to make this happens. You also need to devise a file format such that you can record the information of a social-affiliation network in a file.

Quiz #2: due: Wednesday, Nov. 22.

· Based on the enhanced graph solver framework in C++ in a zip file here (updated 11/13), please complete the implementation of an option that will take two graphs as two snapshots of an evolving social network and then calculate T(k)’s as defined and described in Section 4.4.

· Demo executable and test cases here: Download and play with the executable and two snapshot graphs (graph1.txt as the first snapshot and graph2.txt the second on) in the zip file to see how your option z should determine and report all the T(k) where there is at least one pair of vertices who have k common friends.

*************************************************************************************************

Weeks 12-13: The Structure of the Web | Link Analysis

Progress report #12-13 on reading, lab experiments, coding: due: Wednesday, Dec. 6.

Submit your progress report on Canvas

Reading

· Read Chapter 14 Link Analysis and Web Search in Networks, Crowds, and Markets: Reasoning About a Highly Connected World.

Lab experiments on social-affiliation networks using data structures in C++:

· See the social-affiliation network framework in C++ in a zip file here (updated 11/20), which now allows you to read tin he information of a social-to affiliation network from a file. Try to devise additional member functions such they can take 2 graphs as two snapshots of an evolving social-affiliation network and automatically derive information regarding triadic closure, focal closure, and membership closure as shown in Figures 4.9, 4.10, and 4.11 as described in Section 4.4 in Chapter 4 Networks in Their Surrounding Contexts.

· See the enhanced graph solver framework in C++ in a zip file here (updated 11/13), which implements solutions for both Quiz 1, Discussion #3, clustering coefficients, embeddedness coefficients, and some basics of triadic closure last week. Please devise an approach to extend and enhance the framework above so that we can handle directed graphs and automatically find strongly connected components discussed in Chapter Chapter 13 The Structure of the Web.

Discussion #6 on social-affiliation networks in graphs using data structures in C++: due: Wednesday, Nov. 29.

· Report your approach and what you are able to accomplish in the lab experiments above.

Submit your discussion on Canvas

*************************************************************************************************

Weeks 14-15: Project and Final Report

Final project report due: Friday, Dec. 15.

Format of the contents of your report
1. General description of the project and its goal.
2. Detailed descriptions of findings and conclusions you have in the end.
3. Detailed list of books/manuals/references you have studied for this project and
the amount of time you spent in the study this semester.
4. Detailed list of experiments and writing/programming tasks you have done for this project and
the amount of time you spent in such work this semester.
5. Descriptions of additional attachment of programs, work journals, or any other relevant documents you have uploaded in the context of this project.
6. A proposed grade and descriptions of why you think you deserve the grade.

Discussion #7 on strongly connected components in graphs using data structures in C++: due: Friday, Dec. 15.

· Report your approach for finding strongly connected components.

· More TBA.

*************************************************************************************************

External resources:

· List all example programs in Mining the Social Web, 2nd Edition.

· On the installation of IPython Notebook for Mining the Social Web, 2nd Edition: 1

*************************************************************************************************

To the Top of the Document of the Page