To the Bottom
of the Page
Instructor: Dr. Shieu-Hong Lin
Email:
Class: MW 12:00-1:15 pm at BUSN 210 PC Lab
(ii)
Monday, Wednesday, Thursday: 3:00~5:00pm: email Dr. Lin in advance to set up an
appointment
Important notes:
¡P Overview of the course: syllabus
¡P 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
¡P
Chapter
1. Overview in Networks,
Crowds, and Markets: Reasoning About a Highly Connected World.
¡P
Preface, prelude, Appendix A and C in Mining the Social Web, 2nd
Ed.
¡P
Explore
the articles about Facebook news feed and more: 1, 2,
3
¡P
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
¡P
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.
¡P
Ask questions
and get feedback in the class if you have problems to make IPython Notebook work,
¡P
Chapter
2. Introduction
to Graphs in Networks, Crowds, and Markets: Reasoning
About a Highly Connected World.
¡P
Roughly browse Chapter 1 (Twitter) of Mining the Social Web, 2nd
Ed.
Lab experiments on graphs and data structures in C++:
¡P 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
¡P
Chapter
3. Strong and
Weak Ties in Networks, Crowds, and Markets: Reasoning
About a Highly Connected World.
¡P
Review Chapter 1 (Twitter) of Mining the Social Web, 2nd
Ed.
¡P
Browse the Wikipedia article on Twitter
Lab experiments with Twitter:
¡P Create a Twitter account (if you don¡¦t have one yet) and sign in to play with it.
¡P Play with the sample programs in Chapter 1 (Twitter) of Mining the Social Web.
Lab experiments on graphs and data structures in C++:
¡P 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.
Discussion #2 on graphs and data structures in C++: due: Wednesday, Sept. 20
¡P Report what you have done and observed in the lab experiments on graphs and Euler circuits above.
¡P
Apply your understanding of C++
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
¡P
Review
Chapter 3. Strong and
Weak Ties in Networks, Crowds, and Markets: Reasoning
About a Highly Connected World.
¡P
Review Chapter 1 (Twitter) of Mining the Social Web, 2nd
Ed.
¡P
Browse about research on the strength of weak
ties: 1, 2, 3
Lab experiments on local bridges in graphs using data structures in C++:
¡P 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.
¡P 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
¡P
Browse
Chapter 4 Networks
in Their Surrounding Contexts
in Networks, Crowds, and Markets:
Reasoning About a Highly Connected World.
¡P
Browse Chapter 2 (Facebook) of Mining the Social Web, 2nd
Ed.
Lab experiments on local bridges in graphs using data structures in C++:
¡P 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.
¡P 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
¡P
Read
Chapter 4 Networks
in Their Surrounding Contexts
in Networks, Crowds, and Markets:
Reasoning About a Highly Connected World.
¡P
Read Chapter 2 (Facebook) of Mining the Social Web, 2nd
Ed.
¡P
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.
¡P
Submit your discussion on Canvas.
Quiz #1 Finding neighborhood
overlapping using data
structures in C++: due: Wednesday, Oct. 11. Open till Wednesday Oct. 18.
¡P 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.
¡P 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
¡P
Review
Chapter 4 Networks
in Their Surrounding Contexts
in Networks, Crowds, and Markets:
Reasoning About a Highly Connected World.
¡P
Read
Chapter 5 Positive and Negative Relationships in Networks,
Crowds, and Markets: Reasoning About a Highly Connected World.
¡P
Read Chapter 3 (LinkedIn) of Mining the Social Web, 2nd
Ed.
Lab experiments on social-affiliation networks using data structures in C++:
¡P 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.
¡P 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.
¡P 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.
¡P 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.
¡P 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
¡P
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++:
¡P 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.
¡P 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.
¡P 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.
Quiz #2: due:
Wednesday, Nov. 22.
¡P 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.
¡P 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.
¡P 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 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
¡P
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++:
¡P 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.
¡P 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.
¡P 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.
¡P Report your approach for finding strongly connected components.
¡P More TBA.
*************************************************************************************************
External resources:
¡P
List all example
programs in Mining the Social Web, 2nd Edition.
¡P
On the installation of IPython
Notebook for Mining the Social Web, 2nd
Edition: 1
*************************************************************************************************
To the Top of the Document of the Page
.