Поиск сообщества - Community search

Обнаружение сообществ в сети, известное как обнаружение / обнаружение сообществ, является фундаментальной проблемой в сетевая наука, которая привлекала большое внимание в последние несколько десятилетий. В последние годы благодаря огромным исследованиям большое количество данных, другая связанная, но другая проблема, называется поиск сообщества, цель которого - найти наиболее вероятное сообщество, содержащее узел запроса, привлекла большое внимание как в академических, так и в промышленных кругах. Это зависящий от запроса вариант проблемы обнаружения сообщества. Подробный обзор поиска сообщества можно найти по ссылке. [1], в котором рассматриваются все недавние исследования[2][3][4][5][6][7][8][9][10][11]

Основные преимущества

Как указывает первая работа по поиску сообщества[2] опубликовано в SIGKDD'2010, многие существующие методы обнаружения / обнаружения сообщества учитывают статический проблема обнаружения сообщества, когда граф должен быть разбит априори без ссылки на узлы запроса. В то время как поиск сообщества часто фокусируется на наиболее вероятном сообществе, содержащем вершину запроса. Основные преимущества поиска по сообществу перед обнаружением / обнаружением сообществ перечислены ниже:

(1) Высокая персонализация.[3][9][10] Обнаружение / обнаружение сообщества часто использует один и тот же глобальный критерий для определения того, может ли подграф квалифицироваться как сообщество. Другими словами, критерий фиксирован и предопределен. Но на самом деле сообщества для разных вершин могут иметь очень разные характеристики. Более того, поиск по сообществу позволяет запрашивающим пользователям указывать более персонализированные условия запроса. Кроме того, персонализированные условия запроса позволяют легко интерпретировать сообщества.

Например, недавняя работа,[9] который фокусируется на атрибутированных графах, где узлы часто связаны с некоторыми атрибутами, такими как ключевое слово, и пытается найти сообщества, называемые атрибутированными сообществами, которые демонстрируют как сильную структуру, так и связность ключевых слов. Пользователи запроса могут указывать узел запроса и некоторые другие условия запроса: (1) значение k, минимальная степень для ожидаемых сообществ; и (2) набор ключевых слов, которые контролируют семантику ожидаемых сообществ. Возвращенные сообщества можно легко интерпретировать по ключевым словам, общим для всех членов сообщества. Более подробную информацию можно найти здесь.[11]

(2) Высокая эффективность. В связи с поразительным ростом социальных сетей в последние годы появилось много действительно больших графиков. Например, количество пользователей Facebook и Twitter часто исчисляется миллиардами. Поскольку обнаружение / обнаружение сообществ часто находит все сообщества из всей социальной сети, это может быть очень дорогостоящим, а также требовать много времени. Напротив, поиск сообщества часто работает на подграфе, что очень эффективно. Более того, обнаружение всех сообществ из всей социальной сети часто не требуется. Для реальных приложений, таких как рекомендации и социальные медиа На рынках люди часто сосредотачиваются на некоторых сообществах, которые им действительно интересны, а не на всех сообществах.

Некоторые недавние исследования[4][9] показали, что для графиков в миллионном масштабе поиск сообщества часто занимает менее 1 секунды, чтобы найти четко определенное сообщество, что обычно намного быстрее, чем многие существующие методы обнаружения / обнаружения сообществ. Это также означает, что поиск сообществ больше подходит для поиска сообществ из больших графов.

(3) Поддержка динамически развивающихся графов.[3] Почти все графики в реальной жизни часто развиваются со временем. Поскольку при обнаружении сообществ часто используется один и тот же глобальный критерий для поиска сообществ, они не чувствительны к обновлениям узлов и ребер в графах. Другими словами, обнаруженные сообщества могут потерять свежесть через короткий промежуток времени. Напротив, поиск по сообществам может с этим легко справиться, поскольку он может выполнять поиск в сообществах в режиме онлайн на основе запроса запроса.

Метрики для поиска по сообществу

Поиск по сообществу часто использует некоторые четко определенные фундаментальные графовые метрики, чтобы сформулировать сплоченность сообществ. Обычно используемые метрики arek-core (минимальная степень),[2][4][6][7][9] к-ферма,[5][8] k-реберная связность,[12][13] и т. д. Среди этих мер наиболее популярной является метрика k-core, которая использовалась во многих недавних исследованиях.[1]

Рекомендации

  1. ^ а б Исян Фан, Синь Хуан, Лу Цинь, Ин Чжан, Вэньцзе Чжан, Рейнольд Ченг, Сюэминь Линь. 2019. Обзор поиска сообщества по большим графам. ссылка arXiv: https://arxiv.org/abs/1904.12539.
  2. ^ а б c Мауро Социо и Аристидес Гионис. 2010. Проблема поиска сообщества и как спланировать успешный коктейль. В материалах 16-й международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных (KDD '10). ACM, Нью-Йорк, Нью-Йорк, США, 939-948. DOI =https://dx.doi.org/10.1145/1835804.1835923
  3. ^ а б c Ваньюнь Цуй, Янхуа Сяо, Хайсюнь Ван, Ики Лу и Вэй Ван. 2013. Онлайн-поиск пересекающихся сообществ. В материалах Международной конференции ACM SIGMOD 2013 по управлению данными (SIGMOD '13). ACM, Нью-Йорк, Нью-Йорк, США, 277-288. DOI =https://dx.doi.org/10.1145/2463676.2463722
  4. ^ а б c Ваньюнь Цуй, Янхуа Сяо, Хайсунь Ван и Вэй Ван. 2014. Локальный поиск сообществ в больших графах. В материалах Международной конференции ACM SIGMOD 2014 по управлению данными (SIGMOD '14). ACM, Нью-Йорк, Нью-Йорк, США, 991-1002. DOI =https://dx.doi.org/10.1145/2588555.2612179
  5. ^ а б Синь Хуан, Хун Чэн, Лу Цинь, Вентао Тянь и Джеффри Сюй Юй. 2014. Запросы сообщества k-truss в больших и динамических графах. В материалах Международной конференции по управлению данными ACM SIGMOD 2014 г. (SIGMOD '14). ACM, Нью-Йорк, Нью-Йорк, США, 1311-1322. DOI =https://dx.doi.org/10.1145/2588555.2610495
  6. ^ а б Жун-Хуа Ли, Лу Цинь, Джеффри Сюй Ю и Руй Мао. 2015. Поиск влиятельного сообщества в больших сетях. Proc. VLDB Endow. 8, 5 (январь 2015), 509-520. DOI =https://dx.doi.org/10.14778/2735479.2735484
  7. ^ а б Никола Барбьери, Франческо Бонки, Эдоардо Галимберти и Франческо Гулло. 2015. Действенный и действенный поиск сообщества. Данные Мин. Знай. Discov. 29, 5 (сентябрь 2015 г.), 1406-1433. DOI =https://dx.doi.org/10.1007/s10618-015-0422-1
  8. ^ а б Синь Хуан, Лакс В. С. Лакшманан, Джеффри Сюй Ю и Хун Ченг. 2015. Примерный поиск ближайшего сообщества в сети. Proc. VLDB Endow. 9, 4 (декабрь 2015 г.), 276-287. DOI =https://dx.doi.org/10.14778/2856318.2856323
  9. ^ а б c d е Исян Фанг, Рейнольд Ченг, Сыцян Ло, Цзяфэн Ху. 2016. Эффективный поиск сообществом больших графов с атрибутами. Proc. VLDB Endow. 9, 12, 1233-1244.
  10. ^ а б Исян Фанг, Рейнольд Ченг, Сяодун Ли, Сицян Ло, Цзяфэн Ху. 2017. Эффективный поиск сообщества по большим пространственным графам. Proc. VLDB Endow. 10, 6, 709-720.
  11. ^ а б http://i.cs.hku.hk/~yxfang/acq.html
  12. ^ Лицзюнь Чан, Сюэминь Линь, Лу Цинь, Джеффри Сюй Ю и Вэньцзе Чжан. «Оптимальные алгоритмы на основе индексов для вычисления компонентов Steiner с максимальной связью». В материалах Международной конференции по управлению данными ACM SIGMOD 2015 г., стр. 459-474. ACM, 2015.
  13. ^ Цзяфэн Ху, Сяовей Ву, Рейнольд Ченг, Сыцян Ло и Исян Фанг. О минимальных запросах Штейнера по максимально связным подграфам. IEEE Transactions по разработке знаний и данных 29, вып. 11 (2017): 2455-2469.