Учитывая большой безмасштабный график (график социальной сети), каков наилучший способ его отбора, чтобы образец сохранил приемлемую абстракцию свойств оригинала?
У меня большой график(Набор данных Твиттера Мунмун, если вы это знаете).Но мне нужен подключенный образец этого графика с достаточно большим диаметром (tl; dr ... причины, почему по запросу ... диаметр 10 будет хорошим).
Проблема заключается в том, что любой поиск в ширину всегда может встретить некоторые массивно связанные узлы.Поэтому я начинаю такой поиск, заводя друзей всех узлов, с которыми сталкиваюсь.Я неизбежно сталкиваюсь с некоторыми узлами, связанными с массой, и должен найти всех своих друзей.Это проблема, потому что я получаю большое количество узлов, которые находятся близко друг к другу в графе.Чтобы сделать программный анализ осуществимым, я должен ограничить количество узлов (и ребер).Весь смысл этого упражнения в том, чтобы найти кратчайшие пути между узлами, поэтому меня, как правило, интересуют ВСЕ соседние узлы.И это проблема.
Один из способов - ограничить макс.количество узлов, подключенных к интересующему меня пользователю. Например, если я сталкиваюсь с @barackobama в ходе поиска в ширину, я гарантирую, что я принимаю лишь небольшую часть его друзей и игнорирую остальные.Но стоило ли этот взломанный граф, или я теряю слишком много информации с точки зрения поиска кратчайших путей ??
Надеюсь, что имеет смысл ...