Маленькие секреты больших графов

[mahoro]

Ого! Очень вдохновляющий пост, чтения на все выходные. Спасибо!

[TedBeer]

число тестовых вершин 262588, число ребер в графе 9437519

Как скромно.
Вот ссылка на статью Your Laptop Can Now Analyze Big Data про софтину GraphChi, которая на обычном мак мини перемалывает граф с данными твитера 2010 года (40 миллионов пользователей, 1.2 миллиарда соединений) за час(!).
Сайт проекта — graphlab.org/graphchi
Тут есть ссылки на данные ЖЖ(65 млн ребер) и Твитер(1.5 млрд) — graphchi example apps
Собственно исходные тексты (С++) и документация — code.google.com/p/graphchi
На сайте проекта есть также ссылка на ранние исходники написанные на Java.

[semenoffalex]

Я бы поостерёгся называть задачи, связанные с кластеризацией графов френдов, «выявлением сообществ». Всё-таки сообщества, даже он-лайн, подразумевают постоянство участников, общность их целей/интересов, длительность и регулярность взаимодействий. Членство в сообществах, обладающих для своих участников какой-либо ценностью, требует затрат ресурсов. В контексте Интернета это в первую очередь время и внимание (на чтение/написание постов, комментов, ведение дискуссий и т.д.).

В то же время, для создания «дружбы» в любой он-лайн соцальной сети как правило требуется пара кликов мышью, а поддержание данного типа отношений зачастую и вовсе не требует усилий (вы поздравляете все свои контакты с днём рождения?). Более того, люди вкладывают различные смыслы и цели в контакты в социальных мидиях (поддержание офф-лайн отношений, адресная книга, демонстрация связи с примечательной персоной и т.д.).

Это, как показывает мой опыт и исследования, делает графы, основанные на списках контактов в ЖЖ, Твиттере и прочих сервисах, достаточно сложными (а иногда и вовсе бессмысленными) для содержательной интерпретации.

Математическое моделирование в данном контексте и вовсе отдельная песнь.

[Lakret]

Не буду вдаваться в длинную дискуссию, но замечу, что «содержательная интерпретация» таких графов вполне возможна. Для того, чтобы на самом деле получить много актуальной информации из них, впрочем, одного анализа графа недостаточно; но граф может и должен быть использован при таком анализе.

[semenoffalex]

«содержательная интерпретация» таких графов вполне возможна.

Например?

[Lakret]

Например, я могу выделить сильносвязные компоненты и предположить, что все люди в таких компонентах относятся к определённым социальным группам — а по информации из профайла я могу понять, что именно их объединяет. Или же, можно сравнить аккаунт пользователя с аккаунтами его друзей по отдельным факторам, и таким образом определить, насколько значимыми являются выбранные факторы для данного пользователя при выборе круга общения. Второй пример я на самом деле делал для небольшого графа и был слегка поражён результатами — это правда работает.

[semenoffalex]

Например, я могу выделить сильносвязные компоненты и предположить, что все люди в таких компонентах относятся к определённым социальным группам — а по информации из профайла я могу понять, что именно их объединяет.

По моему опыту это работает на эгоцентрических сетях Вконтакта и Фейсбука, т.к. они более-менее связаны с офф-лайн знакомствами. В графе френдов ЖЖ ситуация несколько иная, т.к. там контексты «дружбы» сильно различаются.

можно сравнить аккаунт пользователя с аккаунтами его друзей по отдельным факторам, и таким образом определить, насколько значимыми являются выбранные факторы для данного пользователя при выборе круга общения

Это зовётся «гомофилией» — склонностью контактировать с похожими на себя людьми. Однако, тут нужно быть аккуратным с направлением каузальности, ведь существует другой процесс (в западной литературе он зовётся «social contagion», адекватного перевода на русский я еще не нашел), согласно которому близкие люди со временем становятся во многом похожими.

[Lakret]

Меня не особо интересует ЖЖ и его граф :)
Ну, проблема различения следствия и причины вообще характерна для статистики.

[semenoffalex]

Я это всё к тому, что в последнее время физики/математики/компьютерщики сильно возбудились по поводу «социальных сетей» и начали перекладывать на них модели и алгоритмы из своих областей (зачастую совершенно бездумно), приходя таким образом не к самым корректным выводам. Поэтому называть кластеризацию на графах «обнаружением сообществ» не совсем корректно.

[semenoffalex]

«содержательная интерпретация» таких графов вполне возможна.

Например?