VII Международная студенческая научная конференция Студенческий научный форум - 2015

Теория графов, как и большинство точных наук, возникла из решения и, вернее будет сказать, из формулировки известных математических проблем. В данном случае это задачи о Кенигсбергских мостах, разрезании пиццы и раскраски карты. Все вышеуказанные проблемы связанные, в первую очередь, с некими объектами, имеющими характеристики, представляемые графически, и поэтому естественно применить графы для исследования таких объектов как социальные сети.

Не менее естественно применить для построения, анализа и визуализации по параметрам систему Mathematica 10, которая включает большой набор основных операций на графах, в том числе нахождение путей, циклов, кликов и многое другое. Написаны функции в данной системе для создания специальных семей-ств графов, генерирование случайных графов и интерактивное построение графов, а также импорт и экспорт в стандартные форматы.

Помимо стандартных фун-кций для работы с графами в системе Mathematica 10 появились функции построения графа по заданным условиям и его анализ.

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

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

Оговоримся далее считать «социальными сетями» сообщества реальных людей, а «виртуальные сети» - сообщество аккаунтов на сайте в сети. Вершиной графа сети является аккаунт, а ребром – «дружественная связь между аккаунтами».

Кстати, сам термин «социальная сеть» был введен в 1954 году социологом Джеймсом Барнсом [1] и поскольку при случайно-равномерном соединении вершин графа распределение P(k), (k – число входящих в вершины ребер) является биномиальным, а в пределе большого размера графа – пуассоновским, то такие сети также назвали пуассоновскими случайными сетями и долгое время они были интерпретацией социальных сетей. Тем не менее, в начале XXI века выяснилось, что модель Эрдоса-Реньи плохо коррелируется с реальными графами Интернет-сетей [2].

Значительные результаты последних лет в изучении сетевых Интернет-структур были получены в теоретической физике. В частности, в 1999 г. появилась теория безмасштабных сетей, сформулированная Альбертом-Лассо Барабаши [3]. Безмасштабные сети – это граф, где распределение числа связей вершин описывается степенным, а не экспоненциальным (как в пуассоновских сетях) законом, кроме того, объекты, распределенные по степенному закону, нередко устроены иерархически, а основные свойства сети не зависят от размера сети. Название не было придумано специально для этого типа сетей, а было взято из теории критических явлений.

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

Наиболее интересным объектом для изучения внутри сети является некоторые виды вершин, особенно те, которые регулируют потоки информации, назовем их «дружественными».

Термин «дружественная» – вольный перевод термина Betweenness centrality, который введен еще в 1977 г. социологом Линтон Фриман (American Sociological Association, Vol. 40, No. 1 (Mar., 1977), pp. 35-41).

Математически – это такая вершина, которая имеет самый высокий «индекс дружественности», который рассчитывается как отношение общего количества путей, проходящих через эту вершину к числу минимальных путей, говоря иначе – это вершина, через которую проходит максимальное количество кратчайших путей.

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

Библиография

1. Barnes J. A. Class and committees in a Norwegian Island Parish // Human Relations. – 1954. V. 7. – P. 39–58. URL: http://pierremerckle.fr/wp-content/uploads/2012/03/Barnes.pdf (дата обращения 17.07.2014).

2. Watts D. J., Strogatz S. H. Collective dynamics of «small-world» networks // Nature. – 1998, June. Vol. 393. – P. 440–442.

3. Barabasi A. L., Reka A. Emergence of scaling in random networks // Science. – 1999, October. Vol 286. – P. 509–512.