DAOC: Stable Clustering of Large Networks
https://arxiv.org/abs/1909.08786
https://github.com/eXascaleInfolab/daoc
Apache 2.0 License, C++ (морда на Java)
Возможно , просто только дошли руки прочитать. По поиску выходит, что обзора тут еще не было.
TL;DR авторы утверждают, что разработали новый алгоритм community detection, который хорошо масштабируемый.
Сравнивают с Louvain (версия из igraph) и другими, менее известными алгоритмами (в их реализации https://github.com/eXascaleInfolab/clubmark - я раньше про нее не слышал). Есть Java-морда (https://github.com/eXascaleInfolab/StaTIX) и еще их же работа про эмбеддинги Bridging the Gap between Community and Node Representations: Graph Embedding via Community Detection https://arxiv.org/abs/1912.08808 (которую я может попозже тоже тут расскажу). По их же бенчмаркам не самый быстрый (Louvain выходит быстрее), но зато самый "универсальный" алгоритм: поддерживается все - и overlapping community, и веса, и направленность, и плюс он еще детерминирован в отличии от Louvain.
Как обычно оптимизируется модулярность (хотя это не обязательно, они пишут, что подходят и другие метрики, удовлетворяющие: парная (т.е. от ij), коммутативная, ограниченная в положительной области). Процесс похож на Louvain в том смысле, что на каждом шаге отбираются кандидаты в кластеры, а потом строится новая сеть их кластеров. Отличия в процессе отбора.
А). На шаге, где выбираются кандидаты на кластеры (вершины, которые хорошо бы объединить исходя из модулярности), они для каждой вершины находят кандидатов-соседей, дающих максимальный вклад в модулярность. Далее они выбирают из списков такие вершины, для которых найденные максимумы gain-а модулярности одинаковы при объединении как i c j, так и j c i. Они назвали это Mutual Maximal Gain (MMG). Так они добиваются:
а). детерменированности
б). выделяют overlapping community: все вершины, имеющие MMG с i "перекрываются" в i.
Б). Те вершины, для которых MMG дает строго один вариант объединения, они сразу формируют кластеры. Далее формируются уже перекрывающиеся кластеры: те вершины, которые имеют несколько кандидатов-кластеров после MMG разбиваются на "виртуальные" вершины, которые сохраняют все веса и связи. При этом для определения веса связей между фрагментами используется степень вершины, которую мы "разбиваем". Далее у нас два варианта: оставить разбиение (т.е, как я понял, вершина шарит кластеры), если весь gain от разбиения положительный; объединить всех кандидатов на кластеры вместе с самой вершиной, если это выгодно. В статье есть формулы для расчета всех весов и более строгие правила, но вроде суть примерно как я написал. Часть про DBSCAN-эвристику, про которую они там пишут (для случая разбиения, когда кандидатов больше, чем степень вершины) я пока не очень понял  .
Выглядит на самом деле очень прикольно. Для меня наиболее ценным видятся:
• детерминированность
• Louvain-style масштабируемость
• возможность получения overlapping community
• работа с directed weighted networks.
https://arxiv.org/abs/1909.08786
https://github.com/eXascaleInfolab/daoc
Apache 2.0 License, C++ (морда на Java)
Возможно , просто только дошли руки прочитать. По поиску выходит, что обзора тут еще не было.
TL;DR авторы утверждают, что разработали новый алгоритм community detection, который хорошо масштабируемый.
Сравнивают с Louvain (версия из igraph) и другими, менее известными алгоритмами (в их реализации https://github.com/eXascaleInfolab/clubmark - я раньше про нее не слышал). Есть Java-морда (https://github.com/eXascaleInfolab/StaTIX) и еще их же работа про эмбеддинги Bridging the Gap between Community and Node Representations: Graph Embedding via Community Detection https://arxiv.org/abs/1912.08808 (которую я может попозже тоже тут расскажу). По их же бенчмаркам не самый быстрый (Louvain выходит быстрее), но зато самый "универсальный" алгоритм: поддерживается все - и overlapping community, и веса, и направленность, и плюс он еще детерминирован в отличии от Louvain.
Как обычно оптимизируется модулярность (хотя это не обязательно, они пишут, что подходят и другие метрики, удовлетворяющие: парная (т.е. от ij), коммутативная, ограниченная в положительной области). Процесс похож на Louvain в том смысле, что на каждом шаге отбираются кандидаты в кластеры, а потом строится новая сеть их кластеров. Отличия в процессе отбора.
А). На шаге, где выбираются кандидаты на кластеры (вершины, которые хорошо бы объединить исходя из модулярности), они для каждой вершины находят кандидатов-соседей, дающих максимальный вклад в модулярность. Далее они выбирают из списков такие вершины, для которых найденные максимумы gain-а модулярности одинаковы при объединении как i c j, так и j c i. Они назвали это Mutual Maximal Gain (MMG). Так они добиваются:
а). детерменированности
б). выделяют overlapping community: все вершины, имеющие MMG с i "перекрываются" в i.
Б). Те вершины, для которых MMG дает строго один вариант объединения, они сразу формируют кластеры. Далее формируются уже перекрывающиеся кластеры: те вершины, которые имеют несколько кандидатов-кластеров после MMG разбиваются на "виртуальные" вершины, которые сохраняют все веса и связи. При этом для определения веса связей между фрагментами используется степень вершины, которую мы "разбиваем". Далее у нас два варианта: оставить разбиение (т.е, как я понял, вершина шарит кластеры), если весь gain от разбиения положительный; объединить всех кандидатов на кластеры вместе с самой вершиной, если это выгодно. В статье есть формулы для расчета всех весов и более строгие правила, но вроде суть примерно как я написал. Часть про DBSCAN-эвристику, про которую они там пишут (для случая разбиения, когда кандидатов больше, чем степень вершины) я пока не очень понял  .
Выглядит на самом деле очень прикольно. Для меня наиболее ценным видятся:
• детерминированность
• Louvain-style масштабируемость
• возможность получения overlapping community
• работа с directed weighted networks.
GitHub
GitHub - eXascaleInfolab/daoc: DAOC (Deterministic and Agglomerative Overlapping Clustering algorithm): Stable Clustering of Large…
DAOC (Deterministic and Agglomerative Overlapping Clustering algorithm): Stable Clustering of Large Networks - GitHub - eXascaleInfolab/daoc: DAOC (Deterministic and Agglomerative Overlapping Clust...
Bridging the Gap between Community and Node Representations: Graph Embedding via Community Detection
https://arxiv.org/abs/1912.08808
https://github.com/eXascaleInfolab/daor
AGPL-3.0 License, C++ (в качестве бэка для CommunityDetection их же разработка из статьи выше)
Продолжение статьи выше.
TL;DR авторы предлагают использовать алгоритмы CommunityDetection для построения графовых эмбеддингов. Сравнивают с Node2Vec/DeepWalk, LINE и VERSE (от участника ODS @xgfs). На задачах классификации вершин их разработка (по их бенчмаркам) обходит как DeepWalk-like, так и LIME с VERSE. На задачах предсказания связей Node2Vec и VERSE выглядят лучше, но разработка авторов в топ-3.
По сути идея на поверхности и очень красивая. Мы знаем очень много классных алгоритмов CommunityDetection, которые выдают иерархию сообществ. Это все Louvain-стайл алгоритмы, а также "старые" агломеративные алгоритмы, типа Girvan-Newman и прочих. И эта иерархия и является их скрытым представлением для вершин.
Авторы идут от самых больших кластеров к самым маленьким. Чтобы не плодить кучу одинаковых эмбеддингов (в Louvain некоторые кластеры могут вообще не меняться от шага к шагу), они накладывают условие, что новый эмбеддинг добавляется лишь при условии, что плотность весов в кластере больше, чем в любом его супер-кластере (т.е. они ищут "ядро" каждого кластера верхнего уровня иерархии).
Выглядит на самом деле очень-очень круто по следующим причинам:
можно использовать множество разных алгоритмов CommunityDetection, включая Louvain, для которого есть реализации в большинстве пакетов
фичи получаются очень хорошо интерпретируемые - по сути это сообщества
работает мега быстро (я не уверен, что они именно там с чем сравнивают, но если верить их табличкам, то примерно в 1000-и раз быстрее, чем VERSE, LINE, Node2Vec)
можно переиспользовать уже полученные результаты кластеризаци
можно использовать как supervised-определитель того, какой уровень иерархии сообществ на какую задачу влияет (это особенно круто, т.к. тот же Louvain выдает сообщества от десятков тысяч сообществ в начале, до десятков в конце и понять какой уровень лучше изучать бывает трудно)
parameter free подход (как и все Louvain-style алгоритмы он не требует настройки), хотя руками обрезать пространство эмбеддингов все же можно
они там пишут про робастность, но с этим я не очень понял
https://arxiv.org/abs/1912.08808
https://github.com/eXascaleInfolab/daor
AGPL-3.0 License, C++ (в качестве бэка для CommunityDetection их же разработка из статьи выше)
Продолжение статьи выше.
TL;DR авторы предлагают использовать алгоритмы CommunityDetection для построения графовых эмбеддингов. Сравнивают с Node2Vec/DeepWalk, LINE и VERSE (от участника ODS @xgfs). На задачах классификации вершин их разработка (по их бенчмаркам) обходит как DeepWalk-like, так и LIME с VERSE. На задачах предсказания связей Node2Vec и VERSE выглядят лучше, но разработка авторов в топ-3.
По сути идея на поверхности и очень красивая. Мы знаем очень много классных алгоритмов CommunityDetection, которые выдают иерархию сообществ. Это все Louvain-стайл алгоритмы, а также "старые" агломеративные алгоритмы, типа Girvan-Newman и прочих. И эта иерархия и является их скрытым представлением для вершин.
Авторы идут от самых больших кластеров к самым маленьким. Чтобы не плодить кучу одинаковых эмбеддингов (в Louvain некоторые кластеры могут вообще не меняться от шага к шагу), они накладывают условие, что новый эмбеддинг добавляется лишь при условии, что плотность весов в кластере больше, чем в любом его супер-кластере (т.е. они ищут "ядро" каждого кластера верхнего уровня иерархии).
Выглядит на самом деле очень-очень круто по следующим причинам:
можно использовать множество разных алгоритмов CommunityDetection, включая Louvain, для которого есть реализации в большинстве пакетов
фичи получаются очень хорошо интерпретируемые - по сути это сообщества
работает мега быстро (я не уверен, что они именно там с чем сравнивают, но если верить их табличкам, то примерно в 1000-и раз быстрее, чем VERSE, LINE, Node2Vec)
можно переиспользовать уже полученные результаты кластеризаци
можно использовать как supervised-определитель того, какой уровень иерархии сообществ на какую задачу влияет (это особенно круто, т.к. тот же Louvain выдает сообщества от десятков тысяч сообществ в начале, до десятков в конце и понять какой уровень лучше изучать бывает трудно)
parameter free подход (как и все Louvain-style алгоритмы он не требует настройки), хотя руками обрезать пространство эмбеддингов все же можно
они там пишут про робастность, но с этим я не очень понял
GitHub
eXascaleInfolab/daor
DAOR Parameter-free Embedding Framework for Large Graphs (Networks) - eXascaleInfolab/daor
open_data_sources_2020.pdf
2.3 MB
Источники открытых данных и аналитические материалы
для работы над проектами комплексного развития территорий
https://urban.hse.ru/for_students_open_data_sources
для работы над проектами комплексного развития территорий
https://urban.hse.ru/for_students_open_data_sources
Из ODS.AI
Всем привет!
Есть желание сделать AI-консультанта, который делает философскую консультацию (для начала стартовый вопрос только один - «в чем смысл моей жизни»).
Команда Оскара Бренифье (https://www.labirint.ru/authors/91412/) в прошлом году описала алгоритм и провела 50 консультаций, которые показывают желаемую логику работы алгоритма.
Во вложении - схематичное изображение процесса и пример диалога с пояснениями логики вопросов.
Для понимания: философская консультация ставит целью сделать мышление более ясным для клиента, а не просто побудить выговориться.
Буду очень благодарен, если кто-нибудь сможет подсказать:
что почитать / с кем пообщаться (может, кто-то что-то подобное делает)
какие самые существенные подводные камни в этой задаче
что на данный момент реалистично реализовать (из более продвинутого, нежели психологические проекты, задающие вопросы и стимулирующие выговориться, типа https://www.x2ai.com, https://www.wysa.io)
Продуктовая дизайн команда The New York Times провела ресерч как люди в США потребляют контент и что для них важно
https://open.nytimes.com/looking-forward-to-2020-here-are-10-themes-for-news-166d84125172
Кратко:
1) Люди не хотят получать рекомендации основанные только на их прошлых действиях, они хотят узнавать что то новое, близкое их окружению. Рекомендации друзей и знакомых до сих пор наиболее ценные.
2) Когда люди потребляют контент, выход которого строго запланирован по времени, это превращается в ритуал, событие, что увеличивает вовлеченность.
3) Люди хотят историй с четким началом и концом. Хотят осознавать что история/статья закончены и они ее поняли. Как пример, приводятся очень популярные в США ток-шоу про расследования, и люди их любят за то, что они точно знают, что загадочное происшествие будет обязательно раскрыто и изложено в доступном виде к концу шоу.
4) Люди предпочитают употреблять наиболее сложные с точки зрения восприятия материалы утром, а вечером хотят видеть легкий контент
5) Люди хотят понимать контекст создания статьи/истории, почему им это важно знать сейчас. Хотят знать, что вопрос был очень тщательно изучен и проверен в нескольких источниках. Так как сейчас очень много “fake news”, люди доверяют больше тем материалам, процесс создания и публикации которого им понятен и обоснован
6) Для многих людей социальные платформы ценны в первую очередь не из-за того, что там можно выразить свое мнение, а ввиду того, что там есть возможность общаться с узким кругом людей, которым они доверяют
7) В США практически все покрыто политическим подтекстом и люди не хотят высказывать свое мнение открыто, боясь негативной реакции. Предпочитают это делать в приватных чатах среди людей, которым доверяют
https://open.nytimes.com/looking-forward-to-2020-here-are-10-themes-for-news-166d84125172
Кратко:
1) Люди не хотят получать рекомендации основанные только на их прошлых действиях, они хотят узнавать что то новое, близкое их окружению. Рекомендации друзей и знакомых до сих пор наиболее ценные.
2) Когда люди потребляют контент, выход которого строго запланирован по времени, это превращается в ритуал, событие, что увеличивает вовлеченность.
3) Люди хотят историй с четким началом и концом. Хотят осознавать что история/статья закончены и они ее поняли. Как пример, приводятся очень популярные в США ток-шоу про расследования, и люди их любят за то, что они точно знают, что загадочное происшествие будет обязательно раскрыто и изложено в доступном виде к концу шоу.
4) Люди предпочитают употреблять наиболее сложные с точки зрения восприятия материалы утром, а вечером хотят видеть легкий контент
5) Люди хотят понимать контекст создания статьи/истории, почему им это важно знать сейчас. Хотят знать, что вопрос был очень тщательно изучен и проверен в нескольких источниках. Так как сейчас очень много “fake news”, люди доверяют больше тем материалам, процесс создания и публикации которого им понятен и обоснован
6) Для многих людей социальные платформы ценны в первую очередь не из-за того, что там можно выразить свое мнение, а ввиду того, что там есть возможность общаться с узким кругом людей, которым они доверяют
7) В США практически все покрыто политическим подтекстом и люди не хотят высказывать свое мнение открыто, боясь негативной реакции. Предпочитают это делать в приватных чатах среди людей, которым доверяют
NY Times
Looking Forward to 2020, Here are 10 Themes for News
A human-centered design research process to understand how people use technology and what that might mean for news.