Archive for Март, 2014

Современные методы викификации (25.03.14)

Лексическая многозначность — неотъемлемое свойство естественного языка, заключающееся в том, что слова и словосочетания могут иметь различную смысловую нагрузку в зависимости от окружающего их контекста. В компьютерной лингвистике задача автоматического определения корректных значений слов называется задачей разрешения лексической многозначности (РЛМ). Данная задача является одной из важнейших проблем обработки текстов.
Центральной частью любого современного метода РЛМ является база знаний — источник терминов, их возможных значений (концептов) и связей между ними. В последнее время наибольшее развитие получили методы РЛМ, база знаний которых основана на Википедии — огромном быстрорастущий ресурсе, покрывающем множество предметных областей. В роли концептов в таких базах знаний обычно выступают статьи Википедии, а в роли терминов — текстовые ссылки на них.
Задача поиска терминов в заданном тексте и связывание их с соответствующими статьями Википедии называется задачей викификации. Данная задача имеет такие важные приложения, как семантический поиск, классификация текстов и др.

Докладчик: Денис Федоренко

Презентация (pdf)

Литература

* Milne D., Witten I. H. Learning to link with wikipedia //Proceedings of the 17th ACM conference on Information and knowledge management. – ACM, 2008. – С. 509-518.
* Ratinov L. et al. Local and global algorithms for disambiguation to wikipedia //Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1. – Association for Computational Linguistics, 2011. – С. 1375-1384.
* Cheng X., Roth D. Relational Inference for Wikification //Urbana. – 2013. – Т. 51. – С. 61801.
* Cai Z. et al. Wikification via link co-occurrence //Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. – ACM, 2013. – С. 1087-1096.

Методы получения репрезентативной выборки пользователей социальной сети (18.03.14)

Для обучения и оценки качества методов анализа социальных сетей требуются данные: информация о пользователях реальных социальных сетей. Данный доклад посвящен одному из аспектов сбора таких данных — сэмплингу.
В рамках доклада будут рассмотрены различные способы получения репрезентативной выборки пользователей социальных сетей, так называемые, методы сэмплинга (англ. sampling). При этом будут освещены как классические подходы (поиск в ширину, случайные блуждания и др.), так и современные методы, которые «налету» используют извлекаемую в процессе скачивания информацию (например, сообщества пользователей) для повышения качества дальнейшего сбора.
От качества получаемой выборки сильно зависит качество алгоритмов, использующих эти данные. Поэтому будут рассмотрены различные критерии, по которым оценивается репрезентативность получаемой выборки пользователей. В конце доклада будет кратко рассказано о фреймворке MODIS Crawler, который предназначен для автоматического сбора данных из Интернета, в частности, из социальных сетей.

Докладчик: Андрей Гомзин

Презентация (pdf)

Список литературы:

1. Leskovec J., Faloutsos C. Sampling from large graphs //Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery
and data mining. — ACM, 2006. — С. 631-636.
http://www.stat.cmu.edu/~fienberg/Stat36-835/Leskovec-sampling-kdd06.pdf

2. PAKDD 2013 Tutorial: Sampling and Summarization for Social Networks
http://mslab.csie.ntu.edu.tw/tut-pakdd13/

3. Leskovec J., Kleinberg J., Faloutsos C. Graphs over time: densification laws, shrinking diameters and possible explanations
//Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. — ACM, 2005. — С. 177-187.
http://eprints.pascal-network.org/archive/00001220/01/powergrowth-kdd05.pdf

4. Blenn N. et al. Crawling and detecting community structure in online social networks using local information //NETWORKING 2012. —
Springer Berlin Heidelberg, 2012. — С. 56-67.
http://repository.tudelft.nl/assets/uuid:61624ff0-d637-497a-9bf1-355638b63c7e/Crawling.pdf

Применение тематического моделирования для поиска агентов влияния в социальных сетях (11.03.14)

В рамках доклада планируется познакомить слушателей с тематическим моделированием (модели PLSA и RobustPLSA), с semi-supervised подходами к тематическому моделированию, с иерархическим тематическим моделированием (MASHA).

Будет описано применение этих подходов для решения задачи распределенного поиска агентов влияния в социальном графе.

Докладчик: Валерий Аванесов

Презентация (pdf)

Distributed Generation of Billion-node Social Graphs with Overlapping Community Structure (04.03.14)

In the field of social community detection, it is commonly accepted to utilize graphs with reference community structure for accuracy evaluation. The resulting accuracy value is obtained by directly comparing the ground-truth set of communities with the one produced by the algorithm. Therefore, a generic tool capable of generating random social graphs with realistic community structure and diverse properties is required. As soon as populations of modern social networks reach billion users in size, the tool must be scalable enough to produce synthetic networks of similar scale.

The method for generating large random social graphs with realistic community structure is introduced in the paper. The resulting graphs have several of recently discovered properties of social community structure which run counter to conventional wisdom: dense community overlaps, superlinear growth of number of edges inside a community with its size, and power law distribution of user-community memberships. Further, the method is by-design distributable and showed near-linear scalability in Amazon EC2 cloud using Apache Spark implementation.

Speaker: Kyrylo Chykhradze

presentation (pdf)