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.
Positive Algorithmic Bias Cannot Stop Fragmentation in Homophilic Social Networks
https://arxiv.org/abs/2001.02878v1

TL;DR; Авторы пишут о процессе фрагментации в социальных сетях. Любая социальная сеть, в которой есть малейший preferential attchment процесс, рано или поздно скатится к полной фрагментации. Авторы приводят доказательства этого для одной из моделей. Далее авторы ставят вопрос, могут ли администраторы сети избежать процесса фрагментации. И доказывают, что сохранение равномерного разнообразия и полного отсутствия сегментации не возможно.
Сразу оговорюсь, что я не социолог, просто увидел интересный заголовок в рассылке  и решил посмотреть. Авторы опираются на довольно простую модель: мы начинаем с бесконечно большой сети, где у каждой вершины есть одна случайна связь. Все вершины двух разных цветов. На каждом шаге для каждой вершины выбирается новая связь с некоторым предпочтением (в реальности предпочтение обеспечивается как склонностями людей, так и рекомендательными системами) в пользу "своего" цвета. Чем больше разнообразие имеющихся связей, тем больше предпочтение. С некоторой вероятностью "забывается" одна из старых связей, причем вероятность забыть "долгоживущую" связь меньше. Авторы доказывают, что такая система в пределе приходит к полной сегментации, даже если учитывать слабые связи (aka друзья друзей). Дальше авторы предлагают механизм, имитирующий возможности администраторов сети влиять на цвет (типа мы можем показывать модифицированные рекомендации связей), после чего доказывают, что такой механизм в пределе не способен удержать разнообразие связей на уровне 0.5.
Плюсы:
• Прикольная тема, я, например, раньше об этом не думал в таком ключе
• Интересна сама постановка вопроса
• Строгие доказательства
Минусы:
• Все в пределах бесконечного времени и бесконечного размера сети
• То, что нельзя удержать разнообразие связей на уровне 0.5 мало о чем говорит: это как в анекдоте про физика-теоретика, которого попросили оценить устойчивость стула с тремя ножками (легко оценить устойчивость стула с нулем и бесконечным числом ножек, но с произвольном числом ножек возникают трудности)
Вспомнилась статья (не помню где) о том, что люди голосовавшие за Хиллари в США писали, что не понимают, кто голосует за Трампа, так как все, кого они знают тоже голосовали за Хиллари: кажется фрагментация это наша реальность. Не ясно, в чем опасность фрагментации, может в ограниченности информации? Или быстром достижении пределов роста? В целом постановка вопроса именно про возможности влиять на процесс фрагментации довольно любопытная и кажется, эта тема довольно актуальна.
https://arxiv.org/abs/2001.02878v1

TL;DR; Авторы пишут о процессе фрагментации в социальных сетях. Любая социальная сеть, в которой есть малейший preferential attchment процесс, рано или поздно скатится к полной фрагментации. Авторы приводят доказательства этого для одной из моделей. Далее авторы ставят вопрос, могут ли администраторы сети избежать процесса фрагментации. И доказывают, что сохранение равномерного разнообразия и полного отсутствия сегментации не возможно.
Сразу оговорюсь, что я не социолог, просто увидел интересный заголовок в рассылке  и решил посмотреть. Авторы опираются на довольно простую модель: мы начинаем с бесконечно большой сети, где у каждой вершины есть одна случайна связь. Все вершины двух разных цветов. На каждом шаге для каждой вершины выбирается новая связь с некоторым предпочтением (в реальности предпочтение обеспечивается как склонностями людей, так и рекомендательными системами) в пользу "своего" цвета. Чем больше разнообразие имеющихся связей, тем больше предпочтение. С некоторой вероятностью "забывается" одна из старых связей, причем вероятность забыть "долгоживущую" связь меньше. Авторы доказывают, что такая система в пределе приходит к полной сегментации, даже если учитывать слабые связи (aka друзья друзей). Дальше авторы предлагают механизм, имитирующий возможности администраторов сети влиять на цвет (типа мы можем показывать модифицированные рекомендации связей), после чего доказывают, что такой механизм в пределе не способен удержать разнообразие связей на уровне 0.5.
Плюсы:
• Прикольная тема, я, например, раньше об этом не думал в таком ключе
• Интересна сама постановка вопроса
• Строгие доказательства
Минусы:
• Все в пределах бесконечного времени и бесконечного размера сети
• То, что нельзя удержать разнообразие связей на уровне 0.5 мало о чем говорит: это как в анекдоте про физика-теоретика, которого попросили оценить устойчивость стула с тремя ножками (легко оценить устойчивость стула с нулем и бесконечным числом ножек, но с произвольном числом ножек возникают трудности)
Вспомнилась статья (не помню где) о том, что люди голосовавшие за Хиллари в США писали, что не понимают, кто голосует за Трампа, так как все, кого они знают тоже голосовали за Хиллари: кажется фрагментация это наша реальность. Не ясно, в чем опасность фрагментации, может в ограниченности информации? Или быстром достижении пределов роста? В целом постановка вопроса именно про возможности влиять на процесс фрагментации довольно любопытная и кажется, эта тема довольно актуальна.