Мне интересно, может ли кто-нибудь предложить хорошие отправные точки, когда дело доходит до обнаружения сообщества / разбиения / кластеризации графа на графе, который имеет взвешенные , ненаправленные ребра. У рассматриваемого графа приблизительно 3 миллиона ребер, и каждое ребро выражает степень сходства между двумя вершинами, которые он соединяет. В частности, в этом наборе данных ребра являются индивидуумами, а вершины являются мерой сходства их наблюдаемого поведения.
В прошлом я следовал предложению, которое я получил здесь на stats.stackexchange.com, и использовал реализацию igraph модульной кластеризации Ньюмана, и был удовлетворен результатами, но это было на невзвешенном наборе данных.
Есть ли какие-то конкретные алгоритмы, на которые я должен обратить внимание?
источник
Я знаю, что Gephi может обрабатывать неориентированный взвешенный график, но я помню, что он должен храниться в GDF , который очень близок к CSV или Ucinet DL . Имейте в виду, что это все еще альфа-версия. Теперь, что касается кластеризации вашего графика, у Gephi, похоже, нет кластеризованных конвейеров, за исключением алгоритма MCL, который теперь доступен в последней версии. В 2009 году был проект Google Code Project , Gephi Network Statistics (включающий, например, показатель модульности Ньюмана), но я не знаю, было ли что-то выпущено в этом направлении. Как бы то ни было, кажется, что он допускает какие-то модульные / кластерные вычисления, но см. Также Анализ социальных сетей с использованием R и Gephi иПодготовка данных для анализа социальных сетей с использованием R и Gephi (Большое спасибо @Tal).
Если вы привыкли к Python, стоит попробовать NetworkX (вот пример взвешенного графа с соответствующим кодом). Тогда у вас есть много способов провести анализ.
Вам также следует взглянуть на INSNA - программное обеспечение для анализа социальных сетей или веб-страницу Тима Эванса о сложных сетях и сложности .
источник
Gephi реализует метод модульности Лувена: http://wiki.gephi.org/index.php/Modularity
ура
источник
Алгоритм модульности Лувена доступен на C ++: https://sites.google.com/site/findcommunities/
Он имеет дело с взвешенными сетями миллионов узлов и ребер, и было продемонстрировано, что он работает намного быстрее, чем алгоритм Ньюмена.
источник
Если вы используете python и создали взвешенный граф с использованием NetworkX , то вы можете использовать python-louvain для кластеризации. Где G - взвешенный график:
источник
Я только что наткнулся на пакет tnet для R. Похоже, что создатель исследует обнаружение сообщества на взвешенных и двудольных (двухрежимных) графиках.
http://opsahl.co.uk/tnet/content/view/15/27/
Я еще не использовал это.
источник
SLPA (теперь называется GANXiS) - это быстрый алгоритм, способный обнаруживать как несвязанные, так и перекрывающиеся сообщества в социальных сетях (ненаправленные / направленные и невзвешенные / взвешенные). Показано, что алгоритм дает значимые результаты в реальных социальных и генных сетях. Это один из самых современных. Это доступно в
https://sites.google.com/site/communitydetectionslpa/
Смотрите хороший обзор arxiv.org/abs/1110.5813 для получения дополнительной информации
источник
У меня есть реализация Java для неперекрывающейся, взвешенной / невзвешенной сети, которая могла бы обрабатывать 3 миллиона узлов (я проверил ее на наборе данных миллиона узлов). Однако он работает как k-means и требует, чтобы в качестве входных данных было обнаружено количество разделов (k в kmeans). Вы можете найти больше информации здесь , и вот код , в github
Ура,
источник