Сетевое издание
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

АНАЛИЗ СОЦИАЛЬНЫХ ГРАФОВ МЕТОДОМ ОЦЕНКИ СТЕПЕНИ ИЗОМОРФИЗМА НЕЧЕТКИХ ГРАФОВ НА ОСНОВЕ НЕЧЕТКИХ КЛИК

Берштейн Л.С. 1
1 ФГАОУ ВПО «Южный федеральный университет»
Работа посвящена теоретическим аспектам моделирования социальных графов на основе нечетких графов и гиперграфов. С позиции нечетких отображений и отношений рассматриваются понятия нечеткого гомоморфизма, мономорфизма, эпиморфизма и изоморфизма нечетких графов. Приводится алгоритм построения гомоморфных образов и определения типа гомоморфизма нечетких отношений по основным теоретико-множественным и алгебраическим операциям. Вводятся понятия нечеткой клики, максимальной нечеткой клики и нечеткого множества клик нечеткого графа. Предлагается метод оценки степени изоморфизма нечетких графов на основе нечетких клик. Приводится алгоритм для нахождения максимальных нечетких клик в нечетком графе. Полученные результаты можно применять для решения целого ряда прикладных задач, относящихся к классу задач сопоставления с образцом и связанных с идентификацией социальных сообществ и социальных позиций в социальной сети.
нечеткая клика
нечеткий граф
изоморфизм
социальный граф
1. Берштейн Л.С., Боженюк А.В. Нечеткие графы и гиперграфы. – М.: Научный мир, 2005. – 256 c.
2. Мелихов А.Н., Берштейн Л.С. Конечные четкие и расплывчатые множества. Часть 2. Расплывчатые множества: Учебное пособие. – Таганрог: Изд-во ТРТИ, 1981. – 90 с.
3. Мелихов А.Н., Карелин В.П. Методы распознавания изоморфизма и изоморфного вложения четких и нечетких графов. – Таганрог: ТРТУ, 1995. – 90 с.
4. Целых А.А. Метод распознавания изоморфного вложения нечетких графов на основе нечеткого множества клик // Известия ЮФУ. Технические науки. – 2008. – № 4 (81). – С. 129-132.
5. Целых А.Н. Моделирование процессов принятия решений в нечетких условиях. – Ростов-на-Дону: Изд-во Северо-Кавказского научного центра высшей школы, 1999. – 104 с.
6. Целых А.Н., Целых А.А. Позиционный анализ в социальных сетях на основе отношения эквивалентности // Известия вузов. Северо-Кавказский регион. Естественные науки. – 2011. – Спецвыпуск. – C. 73-76.
7. Fan W. Graph Pattern Matching Revised for Social Network Analysis. In the Proceedings of ICDT 2012, March 26-30, 2012, Berlin, Germany. – P. 8–21.
8. Wasserman, S. and Faust, K. Social Network Analysis: Methods and Applications. – Cambridge University Press, 1994. – P. 3-66.

Введение

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

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

В этой связи все большее число исследователей обращается к математическому аппарату теории нечетких множеств, а также теории нечетких графов и гиперграфов [1] с целью моделирования полного спектра взаимоотношений между социальными акторами. На практике возникает целый ряд прикладных задач, связанных с идентификацией социальных сообществ и социальных позиций [6, 7] в социальной сети и относящихся к классу задач сопоставления с образцом, проверки изоморфизма и распознавания изоморфного вложения графов [3, 4].

Рассмотрим подходы к оценке степени изоморфизма нечетких графов, имеющих социальную природу.

Изоморфизм нечетких графов

Рассмотрим нечеткое отображение Г=(X,Y,F) при условии, что на множестве X задано нечеткое отношение R=(X,P), а на множестве Y – нечеткое отношение S=(Y,Q).

Отображение Г: R→S будем называть гомоморфным отображением или гомоморфизмом между нечеткими отношениями R и S, если для всех xi∈X, i∈I={1,2,...,l} выполняется

Г(R (xi)) ≈ S(Г(xi)), (1)

где Г(xi)∈Y={<(yk), yk>}, k∈K={1,2,...,m} – множество нечетких образов элементов xi∈X при отображении Г, а знак ≈ является нечетким равенством отношений.

Нечеткое отношение S будем называть отношением, индуцированным гомоморфизмом Г или гомоморфным образом отношения R при отображении Г.

Нечеткий образ Г(<xi, xj>) ребра <xi, xj> отношения R при отображении Г определяется из выражения

Г(<xi, xj>)= {<<yk, yl>, <yk, yl>>}, (2)

где <yk, yl>=(mP<xi, xj>&mF<xi, yk>&mF<xj, yl>).

Нечеткий образ петли можно определить как

Г(<xi, xi>)= {<<yk, yk>, <yk, yk>>}, (3)

где <yk, yk>=(mP<xi, xi>&mF<xi, yk >).

Выражение для нахождения нечеткого образа Г (R) отношения R представляет собой объединение нечетких образов всех ребер и петель графика P нечеткого отношения R, которое можно представить, как

Г(R)= Г(<xi, xj>). (4)

Рассмотрим нечеткое отображение Г=(X,Y,F) при условии, что на области отправления X заданы два или более нечетких бинарных (нечеткий граф) или многоарных (нечеткий гиперграф) отношений, над которыми, в свою очередь, выполняются некоторые теоретико-множественные или алгебраические операции.

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

Пусть R1 и R2 – произвольные нечеткие отношения, заданные на области отправления X нечеткого отображения Г, а Г(R1) и Г(R2) – их нечеткие образы, определенные на области прибытия Y .

Если для отображения Г выполняется соотношение

Г (R1 ◊ R2) ≈ Г (R1) ◊ Г (R2), (5)

где R1 ◊ R2 – нечеткое отношение на множестве X, представляющее собой результат применения операции ◊ над отношениями R1 и R2, то Г является нечетким гомоморфным отображением или нечетким гомоморфизмом нечетких отношений R1 и R2 по операции ◊.

Отношение Г(R1 ◊ R2) будет являться нечетким гомоморфным образом отношения R1 ◊ R2 на множестве Y при отображении Г.

Если Г – нечеткое инъективное отображение множества X на множество Y и выполняется соотношение (5), то Г является нечетким мономорфизмом отношений R1 и R2 по операции ◊, а Г(R1 ◊ R2) – нечетким мономорфным образом отношения R1 ◊ R2 на множестве Y.

Если Г – нечеткое сюръективное отображение множества X на множество Y и выполняется соотношение (5), то Г является нечетким эпиморфизмом отношений R1 и R2 по операции ◊, а Г(R1 ◊ R2) – нечетким эпиморфным образом отношения R1 ◊ R2 на множестве Y.

Наконец, если Г – нечеткое инъективное и сюръективное отображение множества X на множество Y и выполняется соотношение (5), то Г является нечетким изоморфизмом отношений R1 и R2 по операции ◊, а Г(R1◊R2) – нечетким изоморфным образом отношения R1 ◊ R2 на множестве Y.

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

Алгоритм 1

1º. Для каждого из отношений R1 и R2 найти нечеткие образы на отображении Г для всех ребер и петель соответствующих им графов, используя выражения (2), (3), а также нечеткие образы отношений R1 и R2 с помощью выражения (4).

2º. Определить отношения, являющиеся результатом выполнения заданных операций ◊ над исходными отношениями R1 и R2 и над их нечеткими образами Г(R1) и Г(R2).

3º. Пользуясь выражением (5), вычислить значения степеней нечеткого равенства для каждой из заданных операций. Если степень нечеткого равенства отношений, полученных в (1), больше или равна 0,5, то считать факт существования гомоморфизма нечетких отношений R1 и R2 по операции ◊ установленным.

4º. Определить тип нечеткого гомоморфизма, пользуясь формулами инъективности и сюръективности отображения Г:

b(Г)inj =1- (((y)& (y))),

b(Г)sur=(((x))).

Понятие нечеткой клики

Рассмотрим ориентированный или неориентированный нечеткий граф .

Определение 1. Подмножество вершин назовем нечеткой кликой со степенью

Величина δ(X') отражает степень близости подграфа к полному подграфу с X' вершинами.

Определение 2. Подмножество вершин назовем максимальной кликой со степенью , если справедливо:

Иначе говоря, любое подмножество , включающее в себя подмножество , является кликой со степенью меньшей величины .

Рассмотрим семейство всех максимальных нечетких клик , содержащих ровно k вершин со степенями соответственно.

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

Определение 3. Множество назовем нечетким множеством клик нечеткого графа .

Свойство 1. Из определения 3 непосредственно вытекает неравенство: .

Заметим, что величина равна 0, если любой k-вершинный подграф имеет хотя бы одну пару вершин, например , между которыми нет никакого ребра, то есть .

Рассмотрим метод нахождения всех максимальных нечетких клик и нечеткое множество клик нечеткого графа , в котором:

.

Свойство 2. Семейство максимальных нечетких клик исходного графа совпадает с семейством максимальных нечетких внутренне устойчивых множеств дополнительного графа .

Данное свойство непосредственно вытекает из определения максимальной нечеткой клики и максимального нечеткого внутренне устойчивого множества.
Из свойства 2 непосредственно вытекает такое следствие.

Следствие 1. Нечеткое множество клик нечеткого графа совпадает с нечетким множеством внутренней устойчивости дополнительного графа .
На основании свойства 2 и следствия 1 предложим следующий метод нахождения максимальных нечетких клик и максимального нечеткого внутренне устойчивого множества нечеткого графа:

  • по заданному нечеткому графу строим дополнительный граф ;
  • для графа находим семейство максимальных нечетких внутренне устойчивых множеств с соответствующей степенью внутренней устойчивости;
  • полученное семейство одновременно является и семейством максимальных нечетких клик исходного графа;
  • по вычисленному семейству максимальных нечетких клик определяем нечеткое множество клик нечеткого графа [1].

Оценка степени изоморфизма на основе нечетких клик нечетких графов

Пусть и – нечеткие графы, изоморфные со степенью f.
Обозначим через

нечеткие множества клик графов и соответственно. Тогда справедливы следующие свойства.

Свойство 3. Справедливо неравенство

.

Данное свойство непосредственно вытекает из определения ядер нечеткого графа.

Свойство 4. Справедливо неравенство

.

Учитывая взаимосвязь между нечетким множеством клик рассматриваемого графа и нечетким множеством внутренней устойчивости дополнительного графа, свойство 4 доказывается аналогично.

Пример 1. Рассмотрим пример оценки степени изоморфизма нечетких графов и , для которых определены нечеткие множества клик

Степень изоморфизма рассматриваемых графов можно оценить с помощью выражения

.

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

Заключение

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

Работа выполнена в рамках гранта Южного федерального университета № 213.01-24/2013-79 «Разработка и исследование методов нечетко-множественного анализа и моделирования социальных графов».

Рецензенты:

Карелин В.П., д.т.н., профессор, заведующий кафедрой прикладной математики и информационных технологий НОУ ВПО «Таганрогский институт управления и экономики», г. Таганрог.

Финаев В.И., д.т.н., профессор, заведующий кафедрой систем автоматизированного управления ФГАОУ ВПО «Южный федеральный университет», г. Ростов-на-Дону.


Библиографическая ссылка

Берштейн Л.С. АНАЛИЗ СОЦИАЛЬНЫХ ГРАФОВ МЕТОДОМ ОЦЕНКИ СТЕПЕНИ ИЗОМОРФИЗМА НЕЧЕТКИХ ГРАФОВ НА ОСНОВЕ НЕЧЕТКИХ КЛИК // Современные проблемы науки и образования. – 2013. – № 6. ;
URL: https://science-education.ru/ru/article/view?id=11188 (дата обращения: 29.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674