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

Версия 11:46, 3 февраля 2017

?

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

• 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

• net <- graph.edgelist(as.matrix(df))
• V(net)$type <- bipartite.mapping(net)$type

Посчитать отдельно участников и страницы (например)

• V(term.network)[V(term.network)$type == 0] - авторы
• V(term.network)[V(term.network)$type == 1] - страницы

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

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

Например для термитника:

• Узлов - 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