Двудольный граф
(не показаны 17 промежуточных версий 1 участника) | |||
Строка 1: | Строка 1: | ||
{{w|http://ru.wikipedia.org/wiki/Двудольный_граф|Двудольный_граф}} | {{w|http://ru.wikipedia.org/wiki/Двудольный_граф|Двудольный_граф}} | ||
+ | |||
+ | === Основные понятия === | ||
* http://barabasi.com/networksciencebook/chapter/2#bipartite-networks | * http://barabasi.com/networksciencebook/chapter/2#bipartite-networks | ||
− | |||
'''Двудо́льный граф''' или '''бигра́ф''' — это математический термин [[Теория графов|теории графов]], обозначающий [[граф]], множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. | '''Двудо́льный граф''' или '''бигра́ф''' — это математический термин [[Теория графов|теории графов]], обозначающий [[граф]], множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. | ||
Строка 16: | Строка 17: | ||
+ | Подробное описание - выбора и обмена - почему и когда одномодальный или многомодальный граф - 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. | ||
Строка 21: | Строка 24: | ||
* 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, | * 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. | * 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]] | ||
Строка 32: | Строка 36: | ||
Т.е. мы преобразуем в матрицу, где количественная характеристика связи показывает количество документов, которые они редактировали вместе. | Т.е. мы преобразуем в матрицу, где количественная характеристика связи показывает количество документов, которые они редактировали вместе. | ||
+ | |||
+ | Многодольный граф | ||
+ | |||
+ | http://barabasi.com/networksciencebook/images/ch-02/figure-2-10.jpg | ||
+ | |||
+ | == Как мы работаем с двудольными графами в [[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) | ||
+ | # IGRAPH DN-- 8709 32308 -- направленная, 8709 узлов, 32308 связей | ||
+ | |||
+ | === Указали, что это [[биграф]] === | ||
+ | |||
+ | # V(term.network)$type <- V(term.network)$name %in% lterm[,1] # - первый вариант | ||
+ | # 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] # круги или квадратики | ||
+ | |||
+ | # is.connected(term.network) # TRUE - связанная сеть | ||
+ | # no.clusters(term.network) # How many components? 1 | ||
+ | # table(clusters(term.network)$csize) # How big are these? | ||
+ | |||
+ | === Распределение авторов по числу исходящих связей (кто самые активные участники) === | ||
+ | |||
+ | Может даже для ненаправленного графа подсчитать, поскольку у нас уже было на вершины разного типа: | ||
+ | |||
+ | # 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 | ||
+ | |||
+ | ==== Центральность по посредничеству ==== | ||
+ | |||
+ | # centralization.betweenness (term.network, directed = FALSE, nobigint = TRUE, normalized = TRUE) # 0.002904453 | ||
+ | |||
+ | == Перевод в одномодальный граф == | ||
+ | |||
+ | * https://pedroj.github.io/bipartite_plots/ | ||
+ | |||
[[Категория:Сеть]] | [[Категория:Сеть]] | ||
+ | [[Категория:R]] |
Текущая версия на 16:01, 25 мая 2019
Содержание |
[править] Основные понятия
Двудо́льный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.
Летописи - типичный пример двудольного графа, на котором представлены связи между участниками и страницами, которые они редактируют. Страницы вики являются социальными объектами.
Сходные примеры:
- фильмы, в которых принимают участия актеры
Совместив в одном пространстве двудольного графа объекты и участников, которые эти объекты создавали, редактировали или оценивали, мы можем увидеть группы людей, объединенных общими социальными объектами.
Подробное описание - выбора и обмена - почему и когда одномодальный или многомодальный граф - 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)
- IGRAPH DN-- 8709 32308 -- направленная, 8709 узлов, 32308 связей
[править] Указали, что это биграф
- V(term.network)$type <- V(term.network)$name %in% lterm[,1] # - первый вариант
- 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] # круги или квадратики
- is.connected(term.network) # TRUE - связанная сеть
- no.clusters(term.network) # How many components? 1
- table(clusters(term.network)$csize) # How big are these?
[править] Распределение авторов по числу исходящих связей (кто самые активные участники)
Может даже для ненаправленного графа подсчитать, поскольку у нас уже было на вершины разного типа:
- 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
[править] Центральность по посредничеству
- centralization.betweenness (term.network, directed = FALSE, nobigint = TRUE, normalized = TRUE) # 0.002904453