Двудольный граф

?

В Википедии тоже есть статья по теме
«Двудольный_граф».

Основные понятия

• http://barabasi.com/networksciencebook/chapter/2#bipartite-networks

Двудо́льный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.

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

Сходные примеры:

• фильмы, в которых принимают участия актеры

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

Подробное описание - выбора и обмена - почему и когда одномодальный или многомодальный граф - http://www.scottbot.net/HIAL/index.html@p=41158.html

• More categories lead to a richer understanding of the diversity of human experience, but are incredibly unhelpful when you want to count things.

---

• Jesus R., Schwartz M., Lehmann S. (2009) Bipartite networks of Wikipedia's articles and authors: a meso-level approach. Proceedings of the 2009 International Symposium on Wikis, 2009, Orlando, Florida, USA, October 25-27, 2009. ACM 2009, ISBN 978-1-60558-730-1,
• Kumar R. et al. Trawling the web for emerging cyber-communities // Computer Networks. 1999. Vol. 31. P. 1481–1493.
• https://github.com/jaroslav-kuchar/Multimode-Networks - Мультимодальные графы в Gephi

Двудольный граф = Биграф = Двумодальная сеть vs Одномодальная сеть или АФФИЛИАТИВНЫЕ СЕТИ бимодальные сети социальные (гиперсети), построенные по критерию участия акторов в одних и тех же событиях или принадлежности к социальным группам. В отличие от традиционных сетей, А.С. включают два множества элементов - акторов и события. Отношения между элементами одного множества обусловлены их связями с элементами другого. Основное предположение, лежащее в основе анализа А.С., состоит в том, что совместное участие в событиях создает условия для возникновения социальных связей другого типа - знакомств, дружбы, конкуренции.

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

Т.е. мы преобразуем в матрицу, где количественная характеристика связи показывает количество документов, которые они редактировали вместе.

Многодольный граф

Как мы работаем с двудольными графами в R+ igraph

Исходные данные взяты из модели Reseach based on Special:Log/NetLogo - модель термитника

• termh <- read.csv(file.choose(),sep=",", as.is=T, header=T) ;
• lterm <- data.frame(Source = paste("U",termh[,1],sep=":" ) , Target = paste("P",termh[,2],sep=":") )
• term.network <- graph.data.frame(lterm,directed=T) ;

summary(term.network)

1. IGRAPH DN-- 8709 32308 -- направленная, 8709 узлов, 32308 связей

Указали, что это биграф

1. V(term.network)$type <- V(term.network)$name %in% lterm[,1] # - первый вариант
2. V(term.network)$type <- bipartite.mapping(term.network)$type # второй вариант - Используем

Посчитали данные для разных типов узлов

• Узлов - length(V(term.network)) 8709
• Связей - length(E(term.network)) 32308
• Авторов - length(V(term.network)[V(term.network)$type == 0]) - 1000
• Страниц - length(V(term.network)[V(term.network)$type == 1]) - 7709

А потом разные подмножества сети мы можем представлять по-разному:

• V(net)$color <- c( "red", "steel blue")[V(net)$type+1] # - красные или синие
• V(net)$shape <- c("circle", "square")[V(net)$type+1] # круги или квадратики

1. is.connected(term.network) # TRUE - связанная сеть
2. no.clusters(term.network) # How many components? 1
3. table(clusters(term.network)$csize) # How big are these?

Распределение авторов по числу исходящих связей (кто самые активные участники)

Может даже для ненаправленного графа подсчитать, поскольку у нас уже было на вершины разного типа:

1. V(pr01.network)$type <- bipartite.mapping(pr01.network)$type

Присваиваем переменной $degree значение для данной вершины

V(pr01.network)$degree=degree(pr01.network)

Получаем распределение узлов по степени

V(pr01.network)[V(pr01.network)$type==0]$degree

Распределение страниц по числу входящих связей (кто самые редактируемые страницы)

max(degree(term.network, mode="in" )[V(term.network)$type == 1]) # страница с максимальным числом входящих связей

Распределение по кластерам

> table(clusters(lt06.network)$csize)

  2    3    4    5    7    8   11   12 7324 
 95   24    5    4    1    4    1    1    1 

Центральность по посредничеству

1. centralization.betweenness (term.network, directed = FALSE, nobigint = TRUE, normalized = TRUE) # 0.002904453

Перевод в одномодальный граф

• https://pedroj.github.io/bipartite_plots/