Поиск по сообществу
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
Обнаружение сообществ в сети, известное как обнаружение/обнаружение сообществ, является фундаментальной проблемой сетевой науки , которая привлекла большое внимание в последние несколько десятилетий. В последние годы, благодаря огромным исследованиям больших данных , еще одна связанная, но другая проблема, называемая поиском по сообществу , целью которой является поиск наиболее вероятного сообщества, содержащего узел запроса, привлекла большое внимание как в академических, так и в отраслевых областях. Это зависящий от запроса вариант проблемы обнаружения сообщества. Подробный обзор поиска по сообществам можно найти по ссылке. [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] Почти все графики в реальной жизни часто меняются со временем. Поскольку при обнаружении сообществ часто используется один и тот же глобальный критерий для поиска сообществ, они не чувствительны к обновлениям узлов и ребер в графах. Другими словами, обнаруженные сообщества могут потерять свежесть через небольшой промежуток времени. Напротив, поиск по сообществам может легко справиться с этой задачей, поскольку он может осуществлять поиск по сообществам в режиме онлайн на основе запроса.
Метрики для поиска по сообществу
[ редактировать ]Поиск по сообществам часто использует некоторые четко определенные, фундаментальные графические показатели для определения сплоченности сообществ. Обычно используемые метрики: k-core (минимальная степень), [2] [4] [6] [7] [9] к-ферма, [5] [8] k-реберно-связный, [12] [13] и т. д. Среди этих мер метрика k-core является наиболее популярной и использовалась во многих недавних исследованиях, как описано в . [1]
Ссылки
[ редактировать ]- ^ Jump up to: а б Фанг, Синь, Цинь, Лу; Чжан, Вэньцзе; Ченг, Линь ( Сюэмин ) 2019 , . .
- ^ Jump up to: а б с Созио, Мауро; Гионис, Аристид (2010). «Проблема поиска сообщества и как спланировать успешную коктейльную вечеринку». Материалы 16-й международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных - KDD '10 . п. 939. дои : 10.1145/1835804.1835923 . ISBN 9781450300551 . S2CID 11484255 .
- ^ Jump up to: а б с Цуй, Ваньюнь; Сяо, Янхуа; Ван, Хайсюнь; Лу, Ици; Ван, Вэй (2013). «Онлайн-поиск пересекающихся сообществ». Материалы международной конференции по управлению данными 2013 года — SIGMOD '13 . п. 277. дои : 10.1145/2463676.2463722 . ISBN 9781450320375 . S2CID 953025 .
- ^ Jump up to: а б с Цуй, Ваньюнь; Сяо, Янхуа; Ван, Хайсюнь; Ван, Вэй (2014). «Локальный поиск сообществ в больших графах». Материалы Международной конференции ACM SIGMOD 2014 по управлению данными . стр. 991–1002. дои : 10.1145/2588555.2612179 . ISBN 9781450323765 . S2CID 4653380 .
- ^ Jump up to: а б Хуан, Синь; Ченг, Хун; Цинь, Лу; Тянь, Вэньтао; Ю, Джеффри Сюй (2014). «Опрос сообщества k-truss в больших и динамических графиках». Материалы Международной конференции ACM SIGMOD по управлению данными 2014 г. стр. 1311–1322. дои : 10.1145/2588555.2610495 . ISBN 9781450323765 . S2CID 207211829 .
- ^ Jump up to: а б Ли, Ронг-Хуа; Цинь, Лу; Ю, Джеффри Сюй; Мао, Жуй (2015). «Влиятельный поиск сообществ в крупных сетях». Труды Фонда VLDB . 8 (5): 509–520. CiteSeerX 10.1.1.667.4074 . дои : 10.14778/2735479.2735484 . S2CID 17672355 .
- ^ Jump up to: а б Барбьери, Никола; Бончи, Франческо; Галимберти, Эдоардо; Гулло, Франческо (2015). «Эффективный и результативный поиск сообществ». Интеллектуальный анализ данных и обнаружение знаний . 29 (5): 1406–1433. дои : 10.1007/s10618-015-0422-1 . S2CID 13440433 .
- ^ Jump up to: а б Хуан, Синь; Лакшманан, Лакс В.С.; Ю, Джеффри Сюй; Ченг, Хун (2015). «Примерный поиск ближайших сообществ в сетях». Труды Фонда VLDB . 9 (4): 276–287. arXiv : 1505.05956 . дои : 10.14778/2856318.2856323 . S2CID 2905457 .
- ^ Jump up to: а б с д и Фан, Исян; Ченг, Рейнольд; Ло, Сыцян; Ху, Цзяфэн (2016). «Эффективный поиск сообщества больших графов с атрибутами». Труды Фонда VLDB . 9 (12): 1233–1244. дои : 10.14778/2994509.2994538 . hdl : 10722/232839 .
- ^ Jump up to: а б Фан, Исян; Ченг, Рейнольд; Ли, Сяодун; Ло, Сыцян; Ху, Цзяфэн (2017). «Эффективный поиск сообществ по большим пространственным графам». Труды Фонда VLDB . 10 (6): 709–720. дои : 10.14778/3055330.3055337 . hdl : 10722/243528 .
- ^ Jump up to: а б «Эффективный поиск сообщества для больших графов с атрибутами» .
- ^ Чанг, Лицзюнь; Линь, Сюэмин; Цинь, Лу; Ю, Джеффри Сюй; Чжан, Вэньцзе (2015). «Оптимальные алгоритмы на основе индексов для вычисления компонентов Штейнера с максимальной связностью». Материалы Международной конференции ACM SIGMOD 2015 по управлению данными . стр. 459–474. дои : 10.1145/2723372.2746486 . ISBN 9781450327589 . S2CID 18282516 .
- ^ Ху, Цзяфэн; Ву, Сяовэй; Ченг, Рейнольд; Ло, Сыцян; Фан, Исян (2017). «О минимальных запросах подграфа Штайнера с максимальной связностью». Транзакции IEEE по знаниям и инженерии данных . 29 (11): 2455–2469. дои : 10.1109/TKDE.2017.2730873 . S2CID 40432915 .