Лингвистические сети. Linguistic Networks

Осень 2013 / Fall 2013.

Тематический План Курса / Course Outline

1. Введение в теорию комплексных сетей / Introduction to complex networks
2. Анализ узлов и связей/ Node and link analysis
3. Сетевые сообщества / Network communities
4. Сетевая структура / Network structure
5. Визуализация сетей / Network visualization
6. Модели формирования сетей / Network models

Лекции / Lectures

1. [4.09.2013] Комплексные сети / Complex networks. [Lecture 1]
   Введение в теорию комплексных систем. Основные понятия в теории сетей. Свойства и метрики анализа сетей. Степенное распределение. Масштабно-инвариантные сети (scale-free networks). Случайные графы. Распределение Парето, нормализация, моменты,Закон Ципфа.Граф ранк-частота Диаметр и кластерный коэффициенть
2. [11.09.2012] Анализ узлов и связей / Nodes metrics and link analysis . [Lecture 2]
   Метрики центральности узлов / Centrality metrics. Понятия центральности и престижа. Модельные графы. Degree centrality, closeness centrality, betweenness centrality, статус/rank prestige (eigenvector centrality). Центральность сети (сentralization). Анализ связей. Алгоритм PageRank. Стохастические матрицы. Hubs и Authorities. Алгоритм HITS.
3. [26.10.2013]Презентация проектов
4. [13.11.2013] Сетевые сообщества / Network communitites [Lecture 3 ]
   Понятие сетевых сообществ (network communities). Плотность связей. Метрики. Разделение графа на части (graph partitioning). Разрезы (cuts) в графе. Min-cut, quotent and normalized cuts метрики. Divisive and agglomerative algorithms. Repeated bisection. Корреляционная матрица. Clustering. Классификация алгоритмов нахождения сообществ. Алгоритмы нахождения сетевых сообществ Edge Betweenness. Newman-Girvin algorithm. Spectral methods. Modularity maximization algorithm
5. [27.11.2012] Структурная эквивалентность / Structural equivalence. [Lecture 4 ]
   
Метрики структурной эквивалентности узлов. Эвклидово расстояние. Расстояни Хэмминга. (Eucleadean and Hamming distance). Корреляционный коэффициент. Сходство по косинусу (cosine similarity). Ассортативнoe смешивание (homophily). Модулярность (modularity). Ассортативный коэффициент (Assortativity coefficient). Смешивание по степеням узлов (Mixing by degree).
6. [11.12.2012] Визуализация сетей / Network visualization [Lecture 5]
   Методы и инструменты для визуализации сетей.
7. [21.12.2013] Модели формирования сетей / Network models [Lecture 6]
   Random graphs. Модель "малого мира". Модель предпочтительного присоединения. Стратегические модели формирования сетей.
   
8. [27.12.2013] Зачет: презентация проектов
   

Курсовой проекты / Course Projects

• Задание / Assignment .

1. Дарья Рыжова, "Исследование сочетаемости русских имён прилагательных методами анализа комплексных сетей". [slides] [report]
2. Елена Клячко, "Поиск частотных синтаксических паттернов для русского языка методами анализа комплексных сетей". [slides] [report]
3. Анастасия Темченко, "Исследование характеристик лингвистической сети на примере сети, построенной по произведениям Терри Пратчетта". [slides] [report]
4. Андрей Кутузов, "Использование графа совместной встречаемости слов в русскоязычной Википедии для нахождения значений полисемичных лексем". [slides] [report]
5. Даниил Скоркин, "Исследование лингвистической сети, построенной на основе коллекции новостных текстов, методами теории социальных сетей". [slides] [report]
6. Марина Фадеева, "Анализ лингвистической сети, основанной на повести Туве Янссон «Муми-тролль и комета»". [slides] [report]
7. Дмитрий Исаев, "Лингвистическая сеть по повести Дж.Р.Р.Толкиена "Хоббит" [slides] [report]
8. Мария Кюсева, "Использование графа совместной встречаемости слов для исследования семантики русского прилагательного острый". [slides] [report]

Литература по курсу / References

• "Social Network Analysis. Methods and Applications". Stanley Wasserman and Katherine Faust, Cambridge University Press, 1994
• "Networks: An Introduction". Mark Newman. Oxford University Press, 2010.
• "Networks, Crowds, and Markets: Reasoning About a Highly Connected World". David Easley and John Kleinberg, Cambridge University Press 2010.

• Scale Free Networks, Scientific American, A.L Barabasi
• The physics of networks, Physics Today, Mark Newman

• Statistical mechanics of complex networks, R. Albert and A-L. Barabasi
• The Structure and Function of Complex Networks, M. E. J. Newman
• Complex networks: Structure and dynamics, S. Boccaletti et al.
• Evolution of Networks, S. N. Dorogovtsev and J. F. F. Mendes

• Power laws, Pareto distributions and Zipf’s law, M. E. J. Newman
• On random graphs I, P. Erdos and A. Renyi
• On the evolution of random graphs, P. Erdos and A. Renyi
• Collective dynamics of ‘small-world’ networks. Duncan J. Watts and Steven H. Strogatz
• Emergence of Scaling in Random Networks, AL Barabasi and R. Albert
• Centrality in Social Networks. Conceptual Clarification, Linton C. Freeman
• Power and Centrality: A Family of Measures, Phillip Bonacich
• The PageRank Citation Ranknig: Bringing Order to the Web, S. Brin, L. Page
• Authoritative Sources in a Hyperlinked Environment, John M. Kleinberg
• Finding and evaluating community structure in networks, M.E.J. Newman, M. Girvan
• Modularity and community strcuture in networks, M.E.J. Newman
• Community detection in graphs , S. Fortunato

• Language Networks: Their Structure, Function and Evolution Ricard V. Sole, Bernat Corominas Murtra, Sergi Valverde, Luc Steels
• Semantic Networks: Structure and Dynamics Javier Borge-Holthoefer and Alex Arenas
• Quantifying Semantics Using Complex Network Analysis Chris Biemann, Stefanie Roos, Karsten Weihe.
• The Large-Scale Structure of Semantic Networks: Statistical Analyses and a Model of Semantic Growth Mark Steyversa, Joshua B. Tenenbaumb
• The small world of human language. Ramon Ferrer i Cancho and Ricard V. Sole
• Complex network analysis of literary and scientific texts. Iwona Grabska-Gradzinska, Andrzej Kulig, Jaroslaw Kwapien, Stanislaw Drozdz

Програмное обеспечение / Software

• Computations: Matlab, Octave, R, Python
• Graph Visualization: Gephi, yEd
• Matlab libraries:
  • Graph algorithms: MatlabBGL
  • Graph layout: GraphViz. Matlab interface for GraphViz gvraphviz4matlab or graphviz
• Python libraries:
  • Linear algebra algorithms: Numpy, SciPy
  • Graph algorithms and visualizaton: NetworkX, iGraph
  • Language tooklit: NTLK
• R libraries:
  • Graph algorithms: igraph, statnet