Просмотр исходного текста страницы Кластеризация сети

'''Кластеризация сети''' – разбиение социальной сети на непересекающиеся подмножества - кластеры, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались.

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

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

Существует несколько подходов к выделению подструктур в социальной сети:

•	определение клик в социальной сети. Клики — это подгруппы, в которых агенты связаны между собой сильнее, чем с членами других клик; 

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

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

•	выделение группировок (factions) — групп эквивалентных агентов сети, которые имеют максимально похожие профили связей. 


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

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

1. Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками. Признаки могут быть числовыми или нечисловыми.

2. Матрица расстояний между объектами. Каждый объект описывается расстояниями до всех остальных объектов обучающей выборки. 

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

Литература: 

1.	Wasserman S., and Faust К. Social Network Analysis: Methods and Applications. -Cambridge University Press,1994. 

2.	Nair P.S. and Sarasamma S.T. Data Mining Through Fuzzy Social Network Analysis//North American Fuzzy Information Processing Society, 2007

3.	Интерактивная видео-лекция Google [Cluster Computing and MapReduce Lecture 4]http://www.youtube.com/watch?v=1ZDybXl212Q 

4.	Мандель И. Д. Кластерный анализ. — М.: Финансы и статистика, 1988. ISBN 5-279-00050-7.

5.	Х.Хайянь, К.Хильдрун, Л. Дзеюйань Структура сетей научного сотрудничества // Международный форум по информации Т.32. №1 ,2007.С. 8-14

6.	Сивоголовко Е.В Методы обобщающей кластеризации при анализе социальных сетей /  Программные продукты и системы. № 4. 2011. С.24