Расчет коэффициента кластеризации неполной сети с использованием параллельных вычислений
Разработка алгоритма расчета коэффициента кластеризации неполной сети и программы на основе полученного алгоритма. Использование параллельных вычислений для расчета коэффициента кластеризации. Принадлежность исследуемого узла к той или иной группе.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 02.02.2019 |
| Размер файла | 203,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Расчет коэффициента кластеризации неполной сети с использованием параллельных вычислений
Дёмина А.Р., Юдин Е.Б.
Омский государственный технический университет
Аннотация
Разрабатывается алгоритм расчета коэффициента кластеризации неполной сети и программа на основе полученного алгоритма. Приводится структура программы и дается краткая инструкция по работе с ней. Проводится анализ аккаунтов пользователей социальной сети «Вконтакте» с помощью разработанной программы.
Ключевые слова: графы, социальные сети, неполные сети, коэффициент кластеризации
Введение
Социальные сети - неотъемлемая часть современной жизни, которая используется не только для общения, но и для поиска услуг, организации событий и прочих социальных взаимодействий. Исследование социальных сетей может обеспечить сбор важных статистических данных, выявить круг потенциальных покупателей, определить лидеров некоторых групп и известных личностей.
Исследование социальной сети целиком требует огромных ресурсов и длительных вычислений, поэтому целесообразно прибегнуть к исследованию неполной сети - некоторой выборки узлов в рамках полной сети [1]. Для расчёта метрических характеристик и числа подграфов сетей в [2, 3] разработаны соответствующие алгоритмы, которые, тем не менее, не могут корректно применяться при исследовании неполных сетей, так как они не учитывают обработку связей с узлами, не входящими в выборку. В данной работе предлагается алгоритм расчета коэффициента кластеризации неполной сети с использованием параллельных вычислений, а также программа, реализующая этот алгоритм.
При анализе ближайшего окружения сеть разбивается на несколько слоев, представляющих собой подмножества вершин, в зависимости от связи исследуемого узла с остальными (рис. 1).
Рис.1. Граф, разбитый на слои
Так, узлы, образующие непосредственные связи с исследуемым узлом, представляют собой первый слой, узлы, образующие связь с исследуемым узлом только через связь с узлами первого слоя, составляют второй слой и так далее.
Расчет коэффициента кластеризации
Коэффициент кластеризации для полной сети рассчитывается по следующей формуле:
,
где С - коэффициент кластеризации, Д - число треугольников (полных графов на трех вершинах), ? - число вилок (путей длины 2).
Для социальной сети (в которой узлами являются аккаунты, а связи определяют отношения дружбы между аккаунтами) коэффициент кластеризации можно интерпретировать как вероятность того, что «друзья» случайно выбранного аккаунта являются друзьями между собой. Для неполной сети использование такой формулы непригодно, поскольку часть узлов сети не учитывается при сборе данных для неполной сети, искажая статистику. В данной работе предлагается алгоритм и программа, в которой коэффициент кластеризации рассчитывается для подмножеств вершин неполной сети.
Для каждого из слоев подсчитывается коэффициент кластеризации, по формулам:
,
где i - номер исследуемого слоя.
На основе полученного коэффициента кластеризации можно судить о принадлежности исследуемого узла к той или иной группе, а также возможно судить о степени известности.
Структура программы
Исходный код программы находится в свободном доступе в репозитории GitHub [4].
Для работы с программой понадобится среда разработки Eclipse с установленными плагинами Eclipse Git Team Provider и m2e.
Клонировав проект на свой компьютер, пользователь не сможет им воспользоваться, т.к. сборка проекта не осуществлена. Сборка совершается специальным инструментом Apache Maven, в обязанности которого входит компиляция, создание jar-файлов, генерация документации.
Для удобства разбора командной строки используется библиотека Apache Commons CLI, которая включает в себя набор опций и их аргументов. Общая структура программы представлена на рис. 2.
Запуск осуществляется через командную строку. Пользователь может запустить уже приложенный к программе файл run.bat, в котором представлены основные возможности программы, либо может ввести собственные команды. Для просмотра полного списка команд необходимо вызвать справку. На рис. 3 представлен скриншот окна консоли с запущенной программой, в которой сначала был произведен вызов справки, а затем посчитаны коэффициенты кластеризации для каждого из трех слоев.
Рис. 2. Структура программы
Рис. 3. Скриншот результатов работы программы
коэффициент кластеризация параллельное вычисление
Введенная команда запускает файл по адресу target/GraphStats-1.2.jar, использует граф graphs/1.txt, вызывает опцию применения операций (-op) с единственным параметром cl3, который сообщает программе, что необходимо посчитать коэффициент кластеризации на трех слоях. После этого программе сообщается, что расчет необходимо выполнить в два потока (-t 2), а главному узлу исследуемого графа присвоить идентификационный номер 3252819.
В результате программа загружает граф, выдает соответствующее уведомление и его характеристики: Число вершин (Vertices), число связей (Edges) и идентификационный номер. После этого начинается обработка каждого из слоев. Пользователь может видеть число вилок (Number of forks), число треугольников (Number of triangles) и коэффициент кластеризации для текущего слоя (Clustering coefficient).
Библиографический список
1. Ниткин Д.А., Юдин Е.Б. Исследование социальной сети «ВКонтакте» // Информационные технологии и автоматизация управления. Материалы VI Всероссийской научно-практической конференции студентов, аспирантов, работников образования и промышленности (Омск, 27-30 апреля 2015 г.). - Омск, - 2015. -С. 144-150.
2. Курчанов А.А., Юдин Е.Б Программа расчета метрических характеристик больших графов // Омский научный вестник. - 2014. - № 3 (133). -С. 217-221.
3. Юдин Е.Б., Задорожный В.Н. Расчет числа сетевых мотивов методом случайной выборки каркасов// Омский научный вестник. - 2015. -№ 140. -С. 208-2113)
4. Сайт проекта NeighbourhoodAnalysis [Электронный ресурс]: - Режим доступа: https://github.com/Slyance/NeighbourhoodAnalysis
Размещено на Allbest.ru
...Подобные документы
Сущность и понятие кластеризации, ее цель, задачи, алгоритмы; использование искусственных нейронных сетей для кластеризации данных. Сеть Кохонена, самоорганизующиеся нейронные сети: структура, архитектура; моделирование кластеризации данных в MATLAB NNT.
дипломная работа [3,1 M], добавлен 21.03.2011Микропроцессорные системы обработки данных. Специальные алгоритмы-планировщики для распределения операторов параллельных алгоритмов по процессорам вычислительной сети. Алгоритм построения и уплотнения нитей. Интерфейс программы, результаты работы.
курсовая работа [1,8 M], добавлен 22.02.2011Создание программы, автоматизирующей расчет коэффициента ритмичности продукции с использованием электронных таблиц средствами языка программирования Си. Консолидация данных в MSExcel. Программная реализация алгоритма. Тестирование разработанного ПО.
курсовая работа [3,0 M], добавлен 07.06.2014Автоматизация вычислений, необходимых для расчета коэффициента ритмичности, используя пакеты прикладных программ в Excel. Проведение необходимых расчетов с применением формул в электронных таблицах. Тестирование разработанного программного обеспечения.
курсовая работа [1,6 M], добавлен 28.08.2014Показатели эффективности параллельного алгоритма: ускорение, эффективность использования процессоров, стоимость вычислений. Оценка максимально достижимого параллелизма. Закон Амдала, Закон Густафсона. Анализ масштабируемости параллельного алгоритма.
презентация [493,0 K], добавлен 11.10.2014Вычисление физических параметров реальной электрической цепи посредством преобразования её к эквивалентной. Схема алгоритма программы и ее разработка на языках программирования СИ и С++, результаты расчета зависимостей эквивалентных сопротивлений.
курсовая работа [19,9 K], добавлен 15.10.2010Математическая основа параллельных вычислений. Свойства Parallel Computing Toolbox. Разработка параллельных приложений в Matlab. Примеры программирования параллельных задач. Вычисление определенного интеграла. Последовательное и параллельное перемножение.
курсовая работа [1,1 M], добавлен 15.12.2010Описание структурной схемы искусственного нейрона. Характеристика искусственной нейронной сети как математической модели и устройств параллельных вычислений на основе микропроцессоров. Применение нейронной сети для распознавания образов и сжатия данных.
презентация [387,5 K], добавлен 11.12.2015Основные модели вычислений. Оценки эффективности параллельных алгоритмов, их коммуникационная трудоемкость. Последовательный алгоритм, каскадная схема и способы ее улучшения. Модифицированная каскадная схема. Передача данных, классификация операций.
презентация [1,3 M], добавлен 10.02.2014Характеристика методов нечеткого моделирования и изучение системы кластеризации в пакетах прикладных программ. Разработка и реализация алгоритма для оптимизации базы правил нечеткого классификатора с помощью генетического алгоритма аппроксимации функции.
дипломная работа [1,9 M], добавлен 21.06.2014Понятие вычислительных систем, их классификация по различным признакам. Модели параллельных вычислений PGAS и APGAS. Разработка программного продукта для анализа информационных обменов в параллельных программах на языке IBM X10. Расчёт его себестоимости.
дипломная работа [1,6 M], добавлен 10.06.2013Особенности кластеризации социальных сетей, методы распознавания сообществ. Особенности локального прореживания графа. Разработка рекомендаций по выбору метода кластеризации для выделенных классов задач. Оптимизация процесса дальнейшей обработки данных.
курсовая работа [1,8 M], добавлен 30.06.2017Понятие двумерного массива целых чисел. Создание динамического массива из элементов, расположенных в четырех столбах данного массива и имеющих нечетное значение. Сохранение результатов в файл и выведение их на экран. Использование ввода с файла.
курсовая работа [44,0 K], добавлен 09.11.2014Классификация алгоритмов маршрутизации. Методы передачи данных. Характеристики коммуникационной составляющей длительности выполнения параллельного алгоритма. Преимущества и недостатки CTR. Оценки трудоемкости для различных топологий и кластеров.
презентация [875,8 K], добавлен 10.02.2014Знакомство с историей развития многопроцессорных комплексов и параллельных вычислений. Персональные компьютеры как распространенные однопроцессорные системы на платформе Intel или AMD, работающие под управлением однопользовательских операционных систем.
презентация [1,1 M], добавлен 22.02.2016Сравнение центрального и графического процессора компьютера в параллельных расчётах. Пример применения технологии CUDA для неграфических вычислений. Вычисление интеграла и сложение векторов. Технические характеристики ПК, применяемого для вычислений.
курсовая работа [735,9 K], добавлен 12.07.2015Алгоритм логарифмического сдваивания. Средняя степень параллелизма. Характеристики векторных компьютеров. Модель ускорения для параллельной вычислительной системы. Суммирование методом рекурсивного удвоения. Условия выполнения несогласованного алгоритма.
лекция [183,2 K], добавлен 22.10.2014Рассмотрение теоретических аспектов решения задач средствами пакетов прикладных программ. Разработка алгоритма проведения вычислений, необходимых для расчета израсходованной электроэнергии. Основы организации удобного интерфейса созданной программы.
курсовая работа [1,2 M], добавлен 09.07.2015Основы для проведения кластеризации. Использование Data Mining как способа "обнаружения знаний в базах данных". Выбор алгоритмов кластеризации. Получение данных из хранилища базы данных дистанционного практикума. Кластеризация студентов и задач.
курсовая работа [728,4 K], добавлен 10.07.2017Принципы организации и функционирования биологических нейронных сетей. Система соединенных и взаимодействующих между собой простых процессоров. Нейронные сети Маккалока и Питтса. Оценка качества кластеризации. Обучение многослойного персептрона.
курсовая работа [1,1 M], добавлен 06.12.2010
