CS 43118/ 53118: Graph and Social Network Analysis
Fall 2020
Instructor: Niranjan Rai
Office Location: Mathematics and Computer Science (MSB) Building, Room 253
Office Phone Number: +1 (330)-672-9123
Web: http://www.cs.kent.edu/~nrai/index.html
Email: nrai@kent.edu
Course: CS ST: Graph and Social Network Analysis
Term: Fall 2020
CRN: 23009, 23040
Prerequisites: CS II: Data Structures and Abstraction, Introduction to Database System Design
Time: 12:30pm - 1:45pm, MW
Classroom Location: Remote Course [Blackboard & Blackboard Collaborate Ultra]
Instructor's Virtual Office Hours: 11:30am - 12:30pm, MW; or by appointment
Course Webpage: : http://www.cs.kent.edu/~nrai/fall_2020.html
Section: CS 43118-001, Course Number (CRN)
CS 53118-001, Course Number (CRN)
Enrollment/Official Registration of this class
The official registration
deadline for this course is 09/02/2020.
University policy requires all students to be
officially registered in each class they are attending. Students who are not
officially registered for a course by published deadlines should not be
attending classes and will not receive credit or a grade for the course. Each
student must confirm enrollment by checking his/her class schedule (using
Student Tools in FlashLine)
prior to the deadline indicated. Registration errors must be corrected prior to
the deadline.
http://www.kent.edu/registrar/calendars-deadlines
For
registration deadlines, enter the requested information for a Detailed Class
Search from the Schedule of Classes Search found at:
https://keys.kent.edu:44220/ePROD/bwlkffcs.P_AdvUnsecureCrseSearch?term_in=201680
After locating your course/section, click on the Registration
Deadlines link on the far right side of the listing.
Last day to withdraw: 11/04/2020
Textbook and Reference Books (optional, not required)
1.
Social Network
Analysis: Methods and Applications - Stanley
Wasserman
2.
Social Network
Analysis - David Knoke,
Song Yang
Resources
1. Introduction
to Graph Theory - Robin J. Wilson, Fourth
Edition, https://www.maths.ed.ac.uk/~v1ranick/papers/wilsongraph.pdf
Catalog Description
This course covers a number of important and useful ideas in graph
databases, especially in social networks (e.g. the data model for
certain-uncertain graphs), indexing over graphs, and query processing
algorithms for graph databases (e.g., single-source path queries, path queries,
reachability queries, keyword search queries, subgraph matching, etc.). The
influence maximization problems over social networks in real applications are
also discussed as well as various queries over the distributed graph database.
Course Objectives
·
Give introduction to graph and graph
theory.
·
Get familiar with terminologies and types
of graphs.
·
Introduce the social network snalysis.
·
Teach how we can implement different
queries in social networks.
·
Get familiar with different algorithm in
social networks.
·
Learn about the data mining algorithms in
social network.
Learning Objectives
Students
will be able to get familiar with the different types of graphs and networks.
They will be able to learn about various algorithms and properties of social
networks. They will be able to learn how to implement different queries and
algorithms in social network and analyze them. They will also learn about some
of the data mining algorithms in social networks.
Course Content
1. Chapter 1: Introduction to Graphs and Networks
2. Chapter 2: Graph Terminologies
a. 2.1: Graph Models
b. 2.2: Graph Representation
c. 2.3: Graph Properties
d. 2.4: Graph Visualization
e. 2.5: Graph Problems
f. 2.6: Graph matching
g. 2.7: Graph isomorphism
h. 2.8: Graph Algorithms
i. Single source shortest path query
ii. All-pair shortest path queries
3. Chapter 3: Types of Networks and its Applications
a. 3.1: Road Networks
b. 3.2: Biological Networks
c. 3.3: Social Networks
d. 3.4: Bibliography Networks
e. 3.5: Geo-social networks
4. Chapter 4: Introduction to Social Network Analysis
5. Chapter 5: Applications of Social Network Analysis
6. Chapter 6: Properties of Social Networks
7. Chapter 7: Algorithms in Social Networks
a. 7.1: Community Detection
b. 7.2: Community Search
c. 7.3: Influence Maximization
8. Chapter 8: Data mining in Social Networks
a. 8.1: Graph Clustering
b.
8.2: Graph Pattern Matching
Tentative Schedule
Week |
Topic |
Notes |
Week 1 (Aug. 31) |
Introduction to graphs (1) |
|
Week 1 (Sept. 2) |
Introduction to graphs (2) |
|
Week 2 (Sept. 7) |
-- |
Labor Day; No classes |
Week 2 (Sept. 9) |
Graph Models and Graph Representation |
*Deadline for group formation |
Week 3 (Sept. 14) |
Graph Properties, Graph Visualization, and Graph
Problems |
Homework 1, Due on Sept 28. |
Week 3 (Sept. 16) |
Graph Isomorphism and Graph Algorithms |
|
Week 4 (Sept. 21) |
Road Networks and Biological Networks |
|
Week 4 (Sept. 23) |
Social Networks |
|
Week 5 (Sept. 28) |
Bibliography Networks, and Geo-Social Networks |
Homework 2, Due on Oct 19. |
Week 5 (Sept. 30) |
Introduction to Social Network Analysis (1) |
*Deadline for Project Title and
Proposal submission. |
Week 6 (Oct. 5) |
Introduction to Social Network Analysis (2) |
|
Week 6 (Oct. 7) |
Applications of Social Network Analysis (1) |
|
Week 7 (Oct. 12) |
Applications of Social Network Analysis (2) |
|
Week 7 (Oct. 14) |
Properties of Social Network Analysis (1) |
|
Week 8 (Oct. 19) |
Properties of Social Network Analysis (2) |
Homework 3,
Due on Nov 2 *Deadline for Individual Presentation
Topic Selection |
Week 8 (Oct. 21) |
Community detection algorithms (1) |
|
Week 9 (Oct. 26) |
Individual Presentation (Day 1) |
|
Week 9 (Oct. 28) |
Individual Presentation (Day 2) |
|
Week 10 (Nov. 2) |
Individual Presentation (Day 3) |
Homework 4, Due on Dec 9 |
Week 10 (Nov. 4) |
Community search algorithms (1) |
|
Week 11 (Nov. 9) |
Community search algorithms (2) |
|
Week 11 (Nov. 11) |
Influence maximization algorithms (1) |
*Deadline for Midterm Project Report |
Week 12 (Nov. 16) |
Influence maximization algorithms (2) |
|
Week 12 (Nov. 18) |
Graph clustering algorithms(1) |
|
Week 13 (Nov. 23) |
-- |
Thanksgiving Break; No classes |
Week 13 (Nov. 25) |
||
Week 14 (Nov. 30) |
Graph clustering algorithms (2) |
|
Week 14 (Dec. 2) |
Graph clustering algorithms (3) |
|
Week 15 (Dec. 7) |
Graph pattern matching (1) |
Homework 5, Due on Dec 12 |
Week 15 (Dec. 9) |
Graph pattern matching (2) |
Deadline for final report submission (Dec 12) |
Week 16 (Dec. 14 ~ Dec. 20) |
Project Presentations |
|
Academic calendar: https://www.kent.edu/academic-calender
Final exam schedule: https://www.kent.edu/registrar/spring -final-exam-schedule
NOTE: Exam dates and deadlines are tentative. Exact dates will be announced in class.
Scoring and Grading
Homework will be given at the end of each chapter and should be done and submitted individually. One project is to be submitted by each group at the end of the semester. For undergraduates, group of 4 (max) students is recommended. Each students should give a presentation on the topic of their choice. Attendance or participation of students during the class is also reflected on the final grades.
40%
- Homework (Individual)
30%
- Project (Group)
20%
- Presentation (Individual)
10%
- Attendance / Participation
Scale |
0% |
60% |
67% |
70% |
73% |
77% |
80% |
83% |
87% |
90% |
93% |
Grade: |
F |
D |
D+ |
C- |
C |
C+ |
B- |
B |
B+ |
A- |
A |
GPA: |
0.00 |
1.00 |
1.30 |
1.70 |
2.00 |
2.30 |
2.70 |
3.00 |
3.30 |
3.70 |
4.00 |
Projects
It is a group project. Each student
should have a group (max 4 person).
Late Submission Policy
1 day: 5% deduction
2 to 4 days: 10 % deduction
5 to 7 days: 15% deduction
Online courses are conducted on the premise that
regular attendance requires students to log into the Bb Learn learning management
system (LMS). Attendance is measured both by virtual presence in the online
course and student interaction with course learning materials and assignments.
Students are expected to check their Kent State e-mail and to log into the
system multiple times (at least every other day) during the week.
All actions by students in the Bb Learn LMS can be
tracked. At any time during the course, an instructor may generate a report
that indicates when and how long individual students have been logged into the
LMS, or engaged with course materials or course tools.
Students who anticipate an absence from the online
course due to technical or medical reasons should consult with the instructor
individually. An absence due to illness or injury requires verification from a
medical professional and should be presented to the instructor.
Communicating appropriately in the online classroom
can be challenging. In order to minimize this challenge, it is important to
remember several points of internet etiquette that will smooth communication
for both students and instructors:
NOTE: The instructor reserves the right
to remove posts that are not collegial in nature and/or do not meet the Online
Student Conduct and Etiquette guidelines listed above.
No make-up exams, in-class assignments or quizzes will be given
except for university sanctioned excused absences. If you miss an
exam/assignment/quiz (for a good reason), it is your responsibility to contact
me before that date, or soon after the exam/assignment/quiz as possible.
Students are required to be aware of and follow all
general and academic policies established by Kent State University. A list of
the general academic policies is listed on the online version of the Kent State University Catalog. Specific
policies related to the successful completion of this online course can be
located and reviewed in your Blackboard Learn course.
University policies are located in the Online Student Support Services &
University Policies folder contained within the START HERE folder in your
Blackboard Learn course. [Include this only if you are using the Kent State
Online template, or include this information in your online course].
A university-assigned student e-mail account is the
official university means of communication with all students at Kent State
University. Students are responsible for all information sent to them via their
university-assigned e-mail account. If a student chooses to forward information
in their university e-mail account, he or she is responsible for all
information, including attachments, sent to any other e-mail account. To stay
current with university information, students are expected to check their
official university e-mail account and other electronic communications on a
frequent and consistent basis. Recognizing that some communications may be
time-critical, the university recommends that electronic communications be
checked minimally twice a week.
Students with Disabilities
(Revised 6/01/07) University policy 3342-3-01.3
requires that students with disabilities be provided reasonable accommodations
to ensure their equal access to course content. If you have a documented
disability and require accommodations, please contact the instructor at the
beginning of the semester to make arrangements for necessary classroom
adjustments. Please note, you must first verify your eligibility for these
through Student Accessibility Services (contact 330-672-3391 or visit www.kent.edu/sas for more information
on registration procedures).
Blackboard Learn
accessibility statement: http://blackboard.com/Platforms/Learn/Resources/Accessibility/WebCT-Accessibility.aspx
Course Enrollment and Withdrawal
University policy requires all students to be
officially registered in each class they are attending. Students who are not
officially registered for a course by published deadlines should not be
attending classes and will not receive credit or a grade for the course. Each
student must confirm enrollment by checking his/her class schedule (using
Student Tools in FlashLine) prior to the deadline
indicated.
If registration errors are not corrected by this date
and you continue to attend and participate in classes for which you are not
officially enrolled, you are advised now that you will not receive a grade at
the conclusion of the semester for any class in which you are not properly
registered. Also, it is your responsibility to check the withdrawal dates for
each semester.
Plagiarism and Academic Integrity
Students enrolled in the university, at all its
campuses, are to perform their academic work according to standards set by
faculty members, departments, schools and colleges of the university; and
cheating and plagiarism constitute fraudulent misrepresentation for which no
credit can be given and for which appropriate sanctions are warranted and will
be applied.
For more information: http://www.kent.edu/academics/resources/plagiarism/
The
University expects a student to maintain a high standard of individual honor in
his/her scholastic work. Unless otherwise required, each student is expected to
complete his or her assignment individually and independently (even in the
team, workload should be distributed to team members to accomplish
individually). Although it is encouraged to study together, the work handed in
for grading by each student is expected to be his or her own. Any form of
academic dishonesty will be strictly forbidden and will be punished to the
maximum extent. Copying an assignment from another student (team) in this class
or obtaining a solution from some other source will lead to an automatic
failure for this course and to a disciplinary action. Allowing another student
to copy one's work will be treated as an act of academic dishonesty, leading to
the same penalty as copying.
University
policy 3-01.8 deals with the problem of academic dishonesty, cheating, and
plagiarism. None of these will be tolerated in this class. The sanctions
provided in this policy will be used to deal with any violations. If you have
any questions, please read the policy at http://www.kent.edu/policyreg/administrative-policy-regarding-student-cheating-and-plagiarism and/or
ask.
This course
may be used to satisfy the University Diversity requirement. Diversity courses
provide opportunities for students to learn about such matters as the history, culture,
values and notable achievements of people other than those of their own
national origin, ethnicity, religion, sexual orientation, age, gender, physical
and mental ability, and social class. Diversity courses also provide
opportunities to examine problems and issues that may arise from differences,
and opportunities to learn how to deal constructively with them.
This course
may be used to satisfy the Writing Intensive Course (WIC) requirement. The
purpose of a writing-intensive course is to assist students in becoming
effective writers within their major discipline. A WIC requires a substantial
amount of writing, provides opportunities for guided revision, and focuses on
writing forms and standards used in the professional life of the discipline.
This course
may be used to fulfill the university's Experiential Learning Requirement (ELR)
which provides students with the opportunity to initiate lifelong learning
through the development and application of academic knowledge and skills in new
or different settings. Experiential learning can occur through civic
engagement, creative and artistic activities, practical experiences, research,
and study abroad/away.
The instructor reserves the right to alter this syllabus as necessary.