Построение социальной сети и кластеризация узлов

Главная » Рефераттар » Построение социальной сети и кластеризация узлов

Понятие «Социальная сеть» появилось в 30-е годы, в Америке. Тогда проводились  исследования взаимосвязи между людьми с помощью социограмм, то есть визуальных диаграмм, в которых отдельные лица представлены в виде точек, а связи между ними – в виде линий. «Социальная сеть» (англ. socialnetwork) –  социальная структура (математически –  граф), состоящая из группы узлов, которыми являются социальные объекты (люди или организации), и связей между ними (социальных взаимоотношений)[1].

В предлагаемой работе описывается проект создания программы для построения социальной сети и последующей кластеризации узлов данной сети на заранее неизвестное число таксонов. Для реализации проекта выбрана интегрированная среда разработки MicrosoftVisualStudio 2010, и язык VisualBasic.NET.

Перед непосредственном использовании программы нужно произвести анкетирование  среди интересующей выборки людей. Анкетирование происходит следующим образом: каждому члену группы дается список всех участников группы, напротив фамилии каждого требуется поставить число в пределах 0 ÷ 10, где «0» — полное отсутствие связи, «1» – слабая связь, и «10» – сильная связь с данным индивидом (самому себе ставится «11»). Под «связью» может пониматься широкий спектр значений, в зависимости от контекста исследования. Это могут быть дружеские отношения, профессиональные, рабочие, и т.д.

.

Далее формируется текстовый файл, в который заносятся результаты данного анкетирования. На этом «ручная работа» заканчивается, всеми остальными вычислениями занимается программа. На первом этапе программа читает файл, определяет всех участников анкетирования, присваивает каждому участнику имя, присваивает ему его матрицу расстояний. Затем вычисляется общая матрица расстояний следующим образом: очевидно, нельзя считать близкой связь между двумя объектами, если один оценил степень связи с другим в 10 баллов, а второй в 1 или даже 0 баллов, для этой цели, и для приведения матрицы в метрическую систему число, которое есть расстояние между этими двумя объектами – это сумма расстояний которые они поставили друг другу.Например узел «А» оценил связь с «Б» в 9 баллов, а узел «Б»  оценил связь  «А» в 5, значит  расстояние м\у ними равно 14. Но 14 – ещё не есть то число, которое будет стоять в общей матрице расстояний. Автор данной работы посчитал, что психологически легче поставить выше оценку тому, с кем связь больше, и наоборот – поставить меньшее число, с кем связь меньше. Максимальное число, которое может получиться на данном этапе – 20 (оба оценили связь на максимум в 10 баллов), и минимальное – 0. Чтобы «облегчить» построение и дальнейшую кластеризацию, будем производить как бы «инверсию», то есть от 20 отнимать сумму расстояний м\у двумя объектами. Таким образом 0 – будет соответствовать близкой связи, 20 – отсутствующей (в примере выше соответственно связь АБ = БА = 20 – 14 = 6).

Далее отобразим сеть. Отображение заключается в рисовании узлов сети с их названиями на форме. Есть 2 варианта отображения: произвольное отображение точек в заранее заданном участке формы, либо рисование, отталкиваясь от какого либо одного узла сети (по умолчанию – первого). Следует отметить, что такое отображение узлов сети – преследует только иллюстративную цель, даже отталкиваясь от какого либо одного элемента, нельзя претендовать на полную адекватность. Например,  если узел «А» хорошо дружит с «Б» и «В», а «Б» и «В» друг друга не переносят, то как это отобразить на сети? Как выбрать расположение?

После вышеописанных действий переходим к кластеризации узлов сети. После перебора различных методов кластеризации, было решено в программе реализовать алгоритм таксономии класса FOREL.

В алгоритмах таксономии класса FORELиспользуется критерий «похожести на центр», который заключается в следующем: Если координаты центра j-го таксона обозначить символом  , то сумма расстояний   между центром и всеми   точками   этого таксона   , где ,а сумма таких внутренних расстояний для всех   таксонов , . Смысл критерия похожести на центр состоит в том, что нужно найти такое разбиение m объектов на k таксонов, чтобы приведенная выше величина F была минимальной. Выполнение этого условия можно достичь с помощью алгоритма FOREL.

Алгоритм:

  1. Случайно выбираем текущий объект из выборки
  2. Помечаем объекты выборки, находящиеся на расстоянии менее, чем R от текущего
  3. Вычисляем их центр тяжести, помечаем этот центр как новый текущий объект
  4. Повторяем шаги 2-3, пока новый текущий объект не совпадет с прежним
  5. Помечаем объекты внутри сферы радиуса R вокруг текущего объекта как кластеризованные, выкидываем их из выборки
  6. Повторяем шаги 1-5, пока не будет кластеризована вся выборка

Доказана сходимость алгоритма за конечное число шагов, однако легко видеть, что решение может быть не единственным. Так, на рисунке 1 видно, что результат таксономии зависит от того, с какой первой точки был начат процесс.

Рисунок 1. Различные варианты кластеризации

.
.

Если начальную точку менять случайным образом, то может получиться несколько разных вариантов таксономии, и тогда нужно останавливаться на таком варианте, который соответствует минимальному значению величины F[2].

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

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

ОСТАВИТЬ КОММЕНТАРИЙ

Лимит времени истёк. Пожалуйста, перезагрузите CAPTCHA.