Метрики для подключения иерархических графов

Question

это мой первый вопрос о переполнении стека.Это на самом деле не вопрос программирования, но, поскольку в какой-то момент большинству из нас приходится иметь дело с теоретическими проблемами, а вокруг могут быть специалисты по теории графов, я подумал, что могу попробовать.

Я сейчас занимаюсьнекоторые исследования на многоязычных сайтах, и я обнаружил некоторые интересные закономерности в структуре сайта.Графики ниже представляют собой графики двух разных многоязычных сайтов.Извините, у меня недостаточно точек ответов для публикации изображений, поэтому я оставляю их как ссылки.Я использовал алгоритм Force Atlas для макета.Вершины окрашены в соответствии с языком страницы.Затененные области соответствуют подграфам определенного языка.

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

http://www.ai.soc.i.kyoto -u.ac.jp / ~ julien / phd / images /ight.png

ВНа втором графике у нас есть веб-сайт, где языковые версии веб-сайта практически независимы, поэтому мы почти не перекрываем друг друга.

http://www.ai.soc.i.kyoto -u.ac.jp / ~ julien / phd / images/loose.png

Итак, вот мой вопрос:

Существует ли конкретная метрика для количественного определения этого перекрытия?Если так, как он называется?

Поскольку я использовал силовую компоновку, число ребер между языковыми подграфами.Так что я думаю, что что-то вроде принятия отношения количества ребер в подграфе к числу ребер, выходящих наружу / входящих в конкретный подграф, могло бы сработать.Я уверен, что я не первый, кто получил эту идею, поэтому мне было интересно, есть ли у этой метрики имя.Я мог бы тогда оттуда это гуглить :) 1025

Спасибо заранее!

Answer 1

Звучит так, как будто вы ищете Модульность сети .Для данного графа и разбиения (разбиение графа на непересекающиеся подграфы) модульность определяется как:

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

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

Answer 2

И теперь есть другие подходы, кроме модульности, предназначенные для преодоления ограничений, упомянутых в работе, такие как сюрприз ; или B- и C-баллы (рассчитаны как индексы значимости).