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.


For registration deadlines, enter the requested information for a Detailed Class Search from the Schedule of Classes Search found at:



After locating your course/section, click on the Registration Deadlines link on the far right side of the listing.


Last day to withdraw11/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


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 1 (Aug. 31)

Introduction to graphs (1)


Week 1 (Sept. 2)

Introduction to graphs (2)

Chapter 1 slides

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

Chapter 2 slides

Week 4 (Sept. 21)

Road Networks and Biological Networks

 Chapter 3 slides

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)

Chapter 4 Slides

*Deadline for Project Title and Proposal submission.

Week 6 (Oct. 5)

Introduction to Social Network Analysis (2)

Individual Presentation Guidelines

Week 6 (Oct. 7)

Applications of Social Network Analysis (1)

Chapter 5 Slides

Week 7 (Oct. 12)

Applications of Social Network Analysis (2)


Week 7 (Oct. 14)

Properties of Social Network Analysis (1)

Chapter 6 Slides

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)

 Chapter 7

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)

 Chapter 8 Slides

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







































 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


Policies and Expectations

Online Attendance Policy

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.


Communication Policy

  1. Email course questions and personal concerns, including grading questions, to me privately using your @kent.edu email. Do NOT submit posts of a personal nature to the discussion board.
  2. Email will be checked at least twice per day Monday through Friday; Saturday and Sunday, email is checked once per day. During the week, I will respond to all emails within 24 hours; on weekends and holidays, allow up to 48 hours. If there are special circumstances that will delay my response, I will make an announcement to the class.
  3. Student Forum/Q&A discussion boards will be checked twice per day Monday through Friday; Saturday and Sunday, these discussion boards will be checked once per day.
  4. Virtual office hours will be held using the Blackboard IM tool. Instructions for downloading the tool and usage are located in the START HERE folder in Bb Learn LMS. I will hold Virtual Office Hours every [MW, 11:30am - 12:30pm], as well as special office hours for dedicated topics, such as a large, upcoming assignment. Special topic hours will be announced in advance through the Announcement tool. I am also happy to schedule one-on-one office hours in person, via phone, via Skype, or through instant messenger.
  5. For questions related to technology, please contact: 330-672-HELP for 24/7 support.

Online Student Conduct and (N) etiquette

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:


  1. Read first, Write later. Read the ENTIRE set of posts/comments on a discussion board before posting your reply, in order to prevent repeating commentary or asking questions that have already been answered.
  2. Avoid language that may come across as strong or offensive. Language can be easily misinterpreted in written electronic communication. Review email and discussion board posts BEFORE submitting. Humor and sarcasm may be easily misinterpreted by your reader(s). Try to be as matter-of-fact and professional as possible.
  3. Follow the language rules of the Internet. Do not write using all capital letters, because it will appear as shouting. Also, the use of emoticons can be helpful when used to convey nonverbal feelings. J
  4. Consider the privacy of others. Ask permission prior to giving out a classmate's email address or other information.
  5. Keep attachments small. If it is necessary to send pictures, change the size to an acceptable 250kb or less (one free, web-based tool to try is picresize.com).
  6. No inappropriate material. Do not forward virus warnings, chain letters, jokes, etc. to classmates or instructors. The sharing of pornographic material is forbidden.


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.

Make-up Policy

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.

University Policies


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].


University Use Of Electronic Email

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/


Academic Dishonesty Policy

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.

Statements for the Course

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.