Новые или менее известные структуры данных для сетевых (графовых) данных?

Question

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

Примечание: я нетак сильно интересуются базами данных, как проекты для решения проблем с внешней памятью.

Answer 1

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

Answer 2

Я слышал о Skip Graphs (http://www.google.com/search?ie=UTF-8&oe=UTF-8&sourceid=navclient&gfns=1&q=skip+graphs), вероятностной структуре графов, которая, насколько я знаю, уже используется в некоторых одноранговых приложениях.

Эти графики являются своего рода самоорганизующимися, и их целью является достижение хорошей связности и небольшого диаметра. Существует распределенный алгоритм, который пытается получить такие графики: http://www14.informatik.tu -muenchen.de / personen / jacob / Publications / podc09.pdf