Программа дисциплины Поиск информации в Интернет

Правительство Российской Федерации

Нижегородский филиал

Федерального государственного автономного образовательного учреждения высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"

Факультет

Бизнес-информатики и прикладной математики

Программа дисциплины

Поиск информации в Интернет

для направления  010400.68 Прикладная математика и информатика

подготовки магистра

Автор программы:

, кандидат психол. наук, *****@***ru

Одобрена на заседании кафедры

прикладной математики и информатики «___»____________ 2013 г

Зав. кафедрой

Рекомендована секцией УМС «Прикладная математика» «___»____________ 2013 г

Председатель

Утверждена УМС НИУ ВШЭ – Нижний Новгород «___»_____________2013 г.

Председатель

Нижний Новгород, 2013

Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы.

Область применения и нормативные ссылки

Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности.

Программа предназначена для преподавателей, ведущих дисциплину «Поиск информации в Интернет», учебных ассистентов и студентов направления подготовки 010400.68 Прикладная математика и информатика уровень подготовки магистр.

Программа разработана в соответствии с:

Образовательным стандартом ФГАУ ВПО НИУ-ВШЭ по направлению подготовки "Прикладная математика и информатика " (уровень подготовки: "МАГИСТР").

Рабочим учебным планом университета по направлению подготовки 010400.68 Прикладная математика и информатика, утвержденным в 2012г.

Цели освоения дисциплины

Курс посвящен рассмотрению различных подходов к поиску и обработке информации находящейся в Интернет, основной акцент делается на методы и алгоритмы теории графов.

Целью освоения дисциплины «Поиск информации в Интернет» является изучение современных подходов к анализу и обработки информации Интернета.

Компетенции обучающегося, формируемые в результате освоения дисциплины

В результате освоения дисциплины студент должен:

·  знать основные модели случайных графов и случайных блужданий на них

·  знать свойства этих моделей и адекватность моделей при моделировании различных свойств сети Интернет

·  знать различные способы оценки «качества» Интернет-страниц (PageRank) и уметь использовать эти знания при построении алгоритмов поиска в Интернете

В результате освоения дисциплины студент осваивает следующие компетенции:

Компетенция	Код НИУ	Дескрипторы – основные признаки освоения (показатели достижения результата)	Формы и методы обучения, способствующие формированию и развитию компетенции
Способен совершенствовать и развивать свой интеллектуальный и общекультурный уровень	СК - М4	Владеет и применяет аппарат теории графов и моделей к широкому спектру задач реального мира	Семинарские занятия: обсуждение статей и проблемных задач, участие в дискуссиях, подготовка презентаций.
Способен к самостоятельному освоению новых методов исследования, изменению научного и научно-производственного профиля своей профессиональной деятельности	СК-М3	Демонстрирует умение овладеть новыми алгоритмами и новыми областями применения веб-графов и случайных графов	Подготовка презентаций, анализ статей, обсуждение результатов практикума
Способен порождать принципиально новые идеи и продукты, обладает креативностью, инициативностью	СЛК-М8	Демонстрирует творческий подход при решении различных задач реального мира (анализа социальных сетей, сетей цитирования и т. д.), в том числе при обсуждении возможностей по применению методов графов для решения практических задач.	Работа с творческими задачами, самостоятельное создание творческих задач
Способен рефлексировать (оценивать и перерабатывать) освоенные научные методы и способы деятельности.	СК-М1	Может оценить область своей компетенции, степень овладения алгоритмами и математическим аппаратом области	Презентации и обсуждения на семинарских занятиях
Способен организовать научно-исследовательскую деятельность.	ИК-М1.2н	Способен организовать свою научно-исследовательскую деятельность (ведение дневника, журнала исследователя)	Дневник исследователя
Способен анализировать и воспроизводить смысл междисциплинарных тек- стов с использованием языка и аппарата прикладной математики.	ИК-М2.1пми	Умеет прочитать статью на английском языке, в которой применяется аппарат веб-графов и случайных графов для решения задач из области социологии, психологии, библиометрики, лингвистики ит. д. и рассказать о ней в собственном выступлении	Презентации и обсуждения на семинарских занятиях
Способен создавать междисциплинарные тексты с использованием языка и аппарата прикладной математики.	ИК-М2.2пми	Способен написать небольшой текст 300-500 слов, в котором изложить решение одной из проблем курса на английском языке (используя материалы курса и статьи на английском языке)	Написание статей по проблемам курса
Способен публично представлять результаты профессиональной деятельности (в том числе с использованием информационных технологий	ИК-М2.5	Способен сделать презентацию о теме курса, в том числе с использованием Power Point или Prezi	Выступление с презентациями на семинарах
Способен использовать в профессиональной деятельности знания в области естественных наук, математики и информатики, понимание основных фак-тов, концепций, принципов теорий, связанных с прикладной математикой и информатикой. Способен строить и решать математические модели в соответствии с направлением подготовки и специализацией. Способен понимать и применять в исследовательской и прикладной деятельности современный математический аппарат.	ИК-М7.1пми ИК-М7.2пми ИК-М7.3пми	Демонстрируем умение применять модели курса к различным задачам социологии, лингвистики, психологии и т. д.	Решение задач на семинарах

Место дисциплины в структуре образовательной программы

Настоящая дисциплина относится к вариативной части цикла дисциплин программы.

Изучение данной дисциплины базируется на знаниях по комбинаторике и теории вероятностей, теории графов и дискретной математике.

В результате освоения учебной дисциплины студенты должны продемонстрировать не только понимание методов и алгоритмов поиска информации в Интернет, но способности перенести изученные методы на широкий спектр задач связанных с изучением характеристик различных случайных процессов: развития языка, социальных сетей, распространения слухов и т. д.

Тематический план учебной дисциплины

№	Название раздела	Всего часов	Аудиторные часы	Самостоя­тельная работа
Лекции	Семинары	Практические занятия
1	Тема 1.Случайные Веб-графы и их модели	32	6	6		20
2	Тема 2. Поиск информации	38	7	7		24
3	Тема 3. Графы и сети в обработке естественных языков	38	7	7		24
	Итого	108	20	20		68

Формы контроля знаний студентов

Тип контроля	Форма контроля	1 год	Параметры
			4
Текущий (неделя)	Контрольная работа Домашнее задание				4 неделя 3 неделя	В виде теста из 10 вопросов по теме курса Презентация на 30-40 минут (около 20 слайдов)
Итоговый	Зачет				*	Устный зачет, 30 мин.

1.2  Критерии оценки знаний, навыков

Текущая оценка рассчитывается как среднее из оценок: выступление с презентацией, участие в дискуссиях на семинаре, оценки за домашнюю и контрольную работу.

Выступление с презентацией оценивается двумя оценками (А и Б):

А. Подготовка презентации. Владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения, способен логически верно, аргументированно и ясно строить устную и письменную речь, способен к саморазвитию, повышению своей квалификации и мастерства, способен, используя отечественные и зарубежные источники информации, собрать необходимые данные проанализировать их и подготовить информационный обзор и/или аналитический отчет, способен использовать для решения коммуникативных задач современные технические средства и информационные технологии.

Оценивается качество материала презентации: использование информационных источников (3 балла), нацеленность на аудиторию (3 балла), насколько презентация в Power Point (OpenOffice) проработана (3 балла), бонусный балл за блестяще подготовленную презентацию (1 балл), итого максимум 10 баллов.

Б. Проведение презентации. Способен логически верно, аргументированно и ясно строить устную и письменную речь, способен использовать для решения коммуникативных задач современные технические средства и информационные технологии.

Оценивается качество процесса презентации: умение заинтересовать аудиторию (3 балла), устная речь оратора (3 балла), взаимодействие с аудиторией (3 балла), бонусный балл за блестяще подготовленную презентацию (1 балл), итого максимум 10 баллов.

Участие в дискуссии на семинаре

Владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения, способен логически верно, аргументировано и ясно строить устную и письменную речь, готов к кооперации с коллегами, работе в коллективе, способен к саморазвитию, повышению своей квалификации и мастерства

Способен критически оценивать свои достоинства и недостатки, наметить пути и выбрать средства развития достоинств и устранения недостатков.

Оценка за семинар: активность на семинаре (3 балла), способность критически обработать информацию (3 балла); умение привлечь необходимые знания для участия в дискуссии (3 балла), бонусный балл за блестящий ответ на семинаре (1 балл), итого максимум 10 баллов.

Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.

Содержание дисциплины

Тема 1. Случайные Веб-графы и их модели

Социальные сети, распространения вирусов, группы языков и другие области для моделирования с помощью графов. Характеристики графов созданных на основе данных из различных областей, свойства эмпирических графов: «мир тесен», степенной закон, закон Зипфа, коэффициенты кластеризации и т. д.. Модель Ердеша-Реньи, Модель предпочтительного присоединения Барабаши – Альберт. Сравнение существующих моделей случайного веб-графа.

Основные понятия: случайный граф, степень вершины, распределение степей вершин, связность, ассортативность, меры центральности.

Основная литература.

1.  Райгородский случайных графов МЦНМО, ISBN -840-6; 2011 г

Дополнительная литература.

2.  Mihalcea R., Radev D., Graph-Based Natural Language Processing and Information Retrieval CAMBRIDGE UNIVERSITY PRESS, ISBN 9613-9, 2011

3.  R. Durrett, «Random graph dynamics», Cambridge, 2007.

4.  L.-A. Barabasi, R. Albert, H. Jeong, «Scale-free characteristics of random networks: the topology of the world-wide web», Physica, A, 69-77.

5.  R. Kumar et al., «Stochastic models for the web graph», 41st Annual Symposium on Foundations of Computer Science, 2000.

6.  B. Bollobas, O. Riordan, J. Spencer, G. Tusnady, «The degree sequence of a scale-free random graph process», Random Structures Algorithms,, N3, 279-290.

7.  B. Bollobas, O. Riordan, «Robustness and vulnerability of scale-free random graphs», Internet Math., 1 (2003), N1, 1-35.

Тема 2. Поиск информации

Архитектура и методы работы поисковых систем. Методы ранжирования узлов графа. Алгоритм PageRank. Поиск с учетом темы (Topic-Sensitive Link Analysis) и поиск с учетом запроса (Query-Dependent Link Analysis). Сильно связанные компоненты Web-графа.. Диаметр графа. HITS алгоритм. Качество поиска. Вычисление точности и полноты алгоритма.

Основные понятия: гигантская компонента, интеграторы или хабы (Hubs), авторитеты ( Authorities), диаметр графа, точность, полнота.

Основная литература.

1.  Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual Web search puter networks and ISDN systems, 30(1), 107–117.

2.  Geng, G.-G., Wang, L.-M., Wang, W., Hu, A.-L., & Shen, S. (2012). Statistical cross-language Web content quality assessment. Knowledge-Based Systems, 35, 312–319. doi:10.1016/j. knosys.2012.05.018

3.  Kandiah, V., & Shepelyansky, D. L. (2012). PageRank model of opinion formation on social networks. Physica A: Statistical Mechanics and its Applications, 391(22), 5779–5793. doi:10.1016/j. physa.2012.06.047

4.  Yan, E., & Ding, Y. (2011). Discovering author impact: A PageRank perspective. Information Processing & Management, 47(1), 125–134. doi:10.1016/j. ipm.2010.05.002

Дополнительная литература.

1.  Schall, D. (2012). Expertise ranking using activity and contextual link measures. Data & Knowledge Engineering, 71(1), 92–113. doi:10.1016/j. datak.2011.08.001

2.  Wei, W., Barnaghi, P., & Bargiela, A. (2011). Rational Research model for ranking semantic entities. Information Sciences, 181(13), 2823–2840. doi:10.1016/j. ins.2011.02.028

3.  Mihalcea R., Radev D., Graph-Based Natural Language Processing and Information Retrieval Cambridge University Press, ISBN 9613-9, 2011

4.  S. Dill, R. Kumar, K. McCurley, S. Rajagopalan, D. Sivakumar, A. Tomkins. Self-similarity in the Web.27th International Conference on Very Large Data Bases, 2001.

5.  Gary Flake, K. Tsioutsiouliklis, R. E. Tarjan. Graph Clustering Techniques based on Minimum Cut Trees. Internet Mathematics, 2002.

6.  Lawrence Page, Sergey Brin, Rajeev Motwani and Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. — 1998. (англ.)

7.  SergeyBrin, LawrencePage. TheAnatomyofaLarge-ScaleHypertextualWebSearchEngine. — 1998. (англ.)

Тема 3. Графы и сети в обработке естественных языков

Сети в языке и семантические сети, параметры словарного графа. Кластеризация текстов: спектральные методы, метод Фидлера. Семантические классы и семантическое расстояние. Поиск синонимов. Сходство: реферирование и машинный перевод.

Основные понятия: «мир тесен», семантические сети, сегментация, определение темы.

Основная литература.

1.  Zhao, Y., and G. Karypis. 2001. Criterion functions for document clustering: Experiments and analysis. Technical Report TR 01-40, Department of Computer Science, University of Minnesota, Twin Cities, MN, USA.

2.  Girvan, M., and M. Newman. munity structure in social and biological networks. In Proceedings of the National Academy of Sciences, pp. 7821–7826.

3.  Dunning, T. E. 1993. Accurate methods for the statistics of surprise and coincidence. Сomputational Linguistics 19:61–74.

Дополнительная литература.

4.  Mihalcea R., Radev D., Graph-Based Natural Language Processing and Information Retrieval CAMBRIDGE UNIVERSITY PRESS, ISBN 9613-9, 2011

Образовательные технологии

На семинарах проводятся дискуссии на основе обсуждения статей или глав из книг, написанных на русском и английском языках.

Оценочные средства для текущего контроля и аттестации студента

Вопросы для оценки качества освоения дисциплины

Задание 1. Пусть G(n, p) – случайный граф, соответствующий модели Ердеша-Реньи (n - количество вершин, p – вероятность наличия ребра между двумя вершинами). Пожалуйста, напишите формулу распределения количества вершин в этом пространстве случайного графа. Найдите чему равно математическое ожидание и дисперсия данного распределения.

Задание 2. Для графов А и Б рассчитайте следующие коэффициенты:

Диаметр графа

Коэффициент кластеризации (clustering coefficient)

Распределение степеней (degree distribution)

Коэффициент ассортативности (assortativity coefficient)

Задание 3. Используя библиотеку nltk или любую другую программу определите частоту слов в поэму «Евгений Онегин». Рассчитайте коэффициент Зипфа для первых 50 слов.

Задание 4. Определите Page Rank двух наиболее авторитетных страниц

Задание 5. Какой из вариантов показывает результат работы алгоритма PageRank для представленного графа

А) B) C)

Задание 6. Рассчитайте коэффициент концентрации и авторитетности узлов (Hubs и Autorities)

Порядок формирования оценок по дисциплине

1. При получении результирующей оценки учитываются: среднее арифметическое оценки за участие в семинарах Осем, оценка за презентацию, включает в себя оценку за домашнюю работу) Опр, оценка за контрольную работу – Ок. р.

2. Вес оценок:

Wк. р. = 0.2, Wпр=0.4, Wсем=0.4

3. Накопленная оценка за текущий контроль выставляется по следующей формуле

Онакопленная = Wсем * Осем +Wк. р. * Ок. р. +Wпр. * Опр.

Например, если у студента по 10-балльной шкале набраны следующие оценки:

Осем = 6, Ок. р. = 6, Опр=4 то Отекущий = + Wсем * Осем +Wк. р. * Ок. р.+ Wпр. * Опр. = 5

4. Если студент согласен с накопленной оценкой Оитоговый = Онакопленная

5. Если студент не согласен с накопленной оценкой, то он может сдавать зачет (письменно).

6. Вес оценок:

Wнакопленная= 0.6, Wзачет = 0.4

7. Результирующая оценка за итоговый контроль выставляется по следующей формуле, где Озачет – оценка за работу непосредственно на зачете

Оитоговый = Wзачет·Озачет + Wнакопленная Онакопленная

Например, если у студента по 10-балльной шкале набраны следующие оценки:

Озачет = 9 Онакопленная=6, Оитоговый = 7

На пересдаче студенту предоставляется возможность получить дополнительный балл для компенсации оценки за текущий контроль. На зачете студент может получить дополнительный вопрос (дополнительную практическую задачу, решить к пересдаче домашнее задание), ответ на который оценивается в 1 балл. Таким образом, результирующая оценка за итоговый контроль в форме зачета, получаемая на пересдаче, выставляется по формуле

Оитоговый = Wзачет·Озачет + Wнакопленная Онакопленная+Oдоп. вопрос

В ведомость выставляется две оценки: например, "зачет" (7).

Учебно-методическое и информационное обеспечение дисциплины

Основная литература

1.  Райгородский случайных графов МЦНМО, ISBN -840-6; 2011 г

Дополнительная литература

1.  B. Bollobas, O. Riordan, «Robustness and vulnerability of scale-free random graphs», Internet Math., 1 (2003), N1, 1-35.

2.  Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual Web search puter networks and ISDN systems, 30(1), 107–117.

3.  B. Bollobas, O. Riordan, J. Spencer, G. Tusnady, «The degree sequence of a scale-free random graph process», Random Structures Algorithms,, N3, 279-290.

4.  Geng, G.-G., Wang, L.-M., Wang, W., Hu, A.-L., & Shen, S. (2012). Statistical cross-language Web content quality assessment. Knowledge-Based Systems, 35, 312–319. doi:10.1016/j. knosys.2012.05.018

5.  Gary Flake, K. Tsioutsiouliklis, R. E. Tarjan. Graph Clustering Techniques based on Minimum Cut Trees. Internet Mathematics, 2002.

6.  Kandiah, V., & Shepelyansky, D. L. (2012). PageRank model of opinion formation on social networks. Physica A: Statistical Mechanics and its Applications, 391(22), 5779–5793. doi:10.1016/j. physa.2012.06.047

7.  L.-A. Barabasi, R. Albert, H. Jeong, «Scale-free characteristics of random networks: the topology of the world-wide web», Physica, A, 69-77.

8.  Yan, E., & Ding, Y. (2011). Discovering author impact: A PageRank perspective. Information Processing & Management, 47(1), 125–134. doi:10.1016/j. ipm.2010.05.002

9.  Lawrence Page, Sergey Brin, Rajeev Motwani and Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. — 1998. (англ.)

10.  Zhao, Y., and G. Karypis. 2001. Criterion functions for document clustering: Experiments and analysis. Technical Report TR 01-40, Department of Computer Science, University of Minnesota, Twin Cities, MN, USA.

11.  Mihalcea R., Radev D., Graph-Based Natural Language Processing and Information Retrieval CAMBRIDGE UNIVERSITY PRESS, ISBN 9613-9, 2011

12.  Girvan, M., and M. Newman. munity structure in social and biological networks. In Proceedings of the National Academy of Sciences, pp. 7821–7826.

13.  R. Durrett, «Random graph dynamics», Cambridge, 2007.

14.  Dunning, T. E. 1993. Accurate methods for the statistics of surprise and coincidence. Сomputational Linguistics 19:61–74.

15.  R. Kumar et al., «Stochastic models for the web graph», 41st Annual Symposium on Foundations of Computer Science, 2000.

16.  S. Dill, R. Kumar, K. McCurley, S. Rajagopalan, D. Sivakumar, A. Tomkins. Self-similarity in the Web.27th International Conference on Very Large Data Bases, 2001.

17.  Schall, D. (2012). Expertise ranking using activity and contextual link measures. Data & Knowledge Engineering, 71(1), 92–113. doi:10.1016/j. datak.2011.08.001

18.  Wei, W., Barnaghi, P., & Bargiela, A. (2011). Rational Research model for ranking semantic entities. Information Sciences, 181(13), 2823–2840. doi:10.1016/j. ins.2011.02.028

Интернет-ресурсы

Райгородского

http://www. *****/php/presentation. phtml? option_lang=rus&presentid=3755

Материально-техническое обеспечение дисциплины

Используется компьютер и стандартный проектор, карточки для экспериментов по распространению информации.

Автор