SubjectsSubjects(version: 964)
Course, academic year 2024/2025
   Login via CAS
Social networks and their analysis - NAIL116
Title: Sociální sítě a jejich analýza
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: English, Czech
Teaching methods: full-time
Guarantor: doc. RNDr. Iveta Mrázová, CSc.
RNDr. František Mráz, CSc.
Teacher(s): RNDr. František Mráz, CSc.
doc. RNDr. Iveta Mrázová, CSc.
Class: Informatika Mgr. - Teoretická informatika
Classification: Informatics > Informatics, Software Applications, Computer Graphics and Geometry, Database Systems, Didactics of Informatics, Discrete Mathematics, External Subjects, General Subjects, Computer and Formal Linguistics, Optimalization, Programming, Software Engineering, Theoretical Computer Science
Is incompatible with: NAIX116
Is interchangeable with: NAIX116
Annotation -
The concept of social networks is widely used to model mutual relationships between people (but also between other objects like chemical compounds). Intriguing problems from this area range from finding important structural patterns that influence interaction among the considered actors across sentiment analysis that studies people´s opinions, emotions, and attitudes to the analysis and evolution of the network structure itself. Recently, the trends have shifted rather towards online social networks (e.g., Facebook, LinkedIn and MySpace) which allow for efficient data collection.
Last update: Hric Jan, RNDr. (07.05.2018)
Aim of the course -

The course reviews fundamental paradigms and algorithms used in the area of social networks. An important part of the lecture/seminar will represent the design and implementation of an own application in order to facilitate deeper understanding of both the social networks and the means applicable to their analysis. Knowledge at the extent of the bachelors´ course NDBI025 Database systems is expected as well as knowledge of the Python language at least on the level of the introductory course in programming for year 1 of the bachelor study program.

The course is given (only) in English.

Last update: Hric Jan, RNDr. (07.05.2018)
Course completion requirements -

A) The lab

Step by step, in an accompanying Moodle course, there will be published assignments and quizzes.

Assignments:

Each assignment has a deadline till which the assignment should be submitted for grading. You can edit a draft solution of an assignment at any time, but the time of submission is when you click the "Submit assignment" button. After clicking this button, you can no longer edit your submission, but you can ask your teacher (per e-mail) to return the assignment to the draft state. The teacher will grade each submitted assignment with 0–10 points. During the semester, you will solve 2 assignments.

A typical solution for an assignment will consist of a text – a description of the solution – and a Python code for solving the task. You can submit both the description and code as a Jupyter notebook. Alternatively, you can submit your texts as a PDF file and the source codes as plain ASCII files.

Warning: If N≥2 participants of the course will submit solutions that are very similar or identical, all these solutions will be considered as a single solution. A teacher will grade the solution by B points according to its quality, and all students who submitted the solution will obtain only the integer part of the value B/N points.

Quizzes:

Beside the assignments, you will solve several on-line quizzes for at most 20 points altogether. Each quiz will have a deadline set. In contrast to assignments, it will not be possible to solve any quiz after its deadline.

For obtaining credits from the lab, it is necessary:

  1. To solve all the assignments and to obtain at least 1 point for each solution. WARNING: late submission of a solution will be penalized with a 1-point decrease for each started week of the delay after the deadline.
  2. To prepare and to present a term project in the lab in the last week of the term or on a date (during the following exam period) that will be set up in the lab within the last week of the term. Subjects of the projects will be discussed in a lab in the middle of this term. Each project will be graded up to 15 points according to its quality.

The quizzes are not among the necessary conditions for obtaining credits for the lab. During labs, it is possible to obtain additional points

  • for demonstrating a solution to a problem assigned during a lab — 1 point,
  • for demonstrating a solution submitted as a solution for an assignment in Moodle (after its deadline) — the integer part of the half of the number of points awarded for the solution (after evaluating by the teacher)

Except for the additional points, obtaining up to 55 points is possible. All points obtained during labs will account for up to 40% of the final exam score. However, when a student obtains more than 55 points within labs (counting also additional points), these points will still account for only 40% of the final exam score.

Continuous work throughout the term is required to obtain the credits; therefore, there will be no additional possibilities to acquire them later.

B) The lecture

The lecture will be given once per week according to the schedule. As already mentioned above, points acquired within the labs will account for up to 40% of the final exam score. Further, there will be one written test, which will be written during a lab. The date for the written test will be set up within the first week of the semester and published in the accompanying Moodle course.

This test will be graded with 0–15% towards the final score. The exam at the end of this term will add up to the remaining 45% of the final score. The following table gives the final grade according to the achieved score:

grade 1 grade 2 grade 3 failure
100%–86% 85%–71% 71%–56% less than 56%

Last update: Mráz František, RNDr., CSc. (06.11.2024)
Literature -

  1. Charu C. Aggarwal (Ed.): Social Network Data Analytics, Springer, 2011
  2. Amy N. Langville, Carl D. Meyer: Google´s PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, 2006
  3. Bing Liu: Sentiment Analysis: Mining Opinions, Sentiments, and Emotions, Cambridge University Press, 2015
  4. Albert-László Barabási: Network science. Cambridge university press, 2016

Last update: Mrázová Iveta, doc. RNDr., CSc. (27.05.2020)
Requirements to the exam -

The exam consists of a written and oral part. The written part precedes the oral part. Failing the written part impacts failing the whole exam, i.e. the exam will be classified by the grade 4 (failed) and the exam will not continue with the oral part. When failing the oral part the next (reparative) attempt will consist again of both the written and oral parts. The final grade of the exam is set based on points awarded for the written and oral parts of the exam as well as on the points obtained for student’s work throughout the semester - see Course completion requirements.

The written part of the exam consists of three questions related to the syllabus of the lecture and/or material covered during the lab classes.

The requirements for the exam correspond to the syllabus of the lecture within the extent presented in the classes. In order to take part in the exam, it is necessary to obtain Final course credit.

Last update: Mrázová Iveta, doc. RNDr., CSc. (27.05.2020)
Syllabus -
  1. Introduction to the area:
    • Information retrieval, web search, social network analysis
    • Main areas of interest in social networks and future directions
  2. Fundamental paradigms of social network analysis:
    • Data and model description, text and web page pre-processing, graph data models, static and dynamic graph properties
    • Subgraph isomorphism, maximum common subgraph problem
    • Matching and distance computation in graphs
    • Topological descriptors for graph structures
    • Frequent substructure-based transformations and mining in graphs
    • Graph clustering and graph classification
  3. Techniques for web data mining:
    • Web crawling and resource discovery
    • Search engine indexing and query processing, web spamming
    • Ranking algorithms: PageRank and HITS
    • Recommender systems: content-based methods, collaborative filtering, graph-based methods, clustering methods, latent factor models
    • Web usage mining: data collection and pre-processing, discovery and analysis of web usage patterns
  4. Approaches to social network analysis:
    • Introduction and main properties, measures of centrality and prestige
    • Community detection: Kernighan-Lin algorithm and its analysis, clustering algorithms, overlapping communities
    • Node classification and label propagation, social influence analysis, detection of experts in social network
    • Evolution and link prediction in social networks
  5. Applications:
    • Sentiment analysis
    • Opinion mining - Feature-based opinion mining and summarization, opinion search and opinion spam
    • Data, text and multimedia information mining in social networks
    • Advertizing on the web
Last update: Hric Jan, RNDr. (07.05.2018)
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html