Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,940

ANALYSIS OF SOCIAL GRAPHS WITH A METHOD OF ESTIMATING DEGREE OF FUZZY GRAPH ISOMORPHISM USING FUZZY CLIQUES

Bershteyn L.S. 1
1 Southern Federal University
This paper covers theoretical aspects of modeling social graphs using fuzzy graphs and hypergraphs. We consider notions of fuzzy homomorphism, monomorphism, epimorphism, and isomorphism from the point of view of fuzzy mappings and relations. We give an algorithm for building homomorphic images and determining the type of fuzzy homomorphism using basic graph-theoretical and algebraic operations. We introduce notions of a fuzzy clique, a maximal fuzzy clique and fuzzy sets of cliques in a fuzzy graph. We suggest a method of estimating degree of fuzzy graph isomorphism using fuzzy cliques. We provide an algorithm for finding maximal fuzzy cliques in a fuzzy graph. Obtained results can be used to solve a series of applied tasks that belong to a class of pattern recognition tasks and are closely related to an identification of social communities and social positions in a social network.
fuzzy clique
fuzzy graph
isomorphism
social graph

Введение

Под социальным графом принято понимать граф, моделирующий взаимоотношения между пользователями в Интернете. В отличие от компьютерных сетей, связывающих вычислительные машины, и Всемирной паутины, связывающей гипертекстовые документы, социальный граф связывает между собой людей. С позиции теории анализа социальных сетей [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 «Разработка и исследование методов нечетко-множественного анализа и моделирования социальных графов».

Рецензенты:

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

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