Социальный граф хабрасообщества

Сегодня, я хотел бы поведать рассказ о своём небольшом эксперименте над аудиторией Хабра. Предметом эксперимента стало построение социального графа хабрасообщества.



Описание

Цели, преследуемые в эксперименте:
  • Выполнить парсинг хабрацентров пользователей
  • Создать граф пользователей, на основании заполненного поля «Друзья»
  • Визуализировать построенный граф


Парсинг и заполнение графа

Для получения информации о пользователях и их друзьях, я написал скрипт parser.py:

# -*- coding:utf-8 -*-
# parser.py

from BeautifulSoup import BeautifulSoup
from urllib2 import urlopen, URLError
from draw import Drawer

class Parser(object):
    def __init__(self, address='http://habrahabr.ru/people/page', begin = 1, end = 3098):
        self.drawer = Drawer()
        self.queue_user = []  
        self.__begin = begin
        self.__end = end
        self.__address = address
    
    def parse(self):
        for i in xrange(self.__begin, self.__end):
            try:
                doc = BeautifulSoup(urlopen(self.__address + str(i)))
                #находим всех пользователей на заданной странице.
                page = doc.findAll('td', attrs = {'class':'user'})
                for user in page:
                    # для каждого пользователя проверяем список друзей
                    print 'Parsing for user: %s' %user.dl.dt.a.string
                    doc = BeautifulSoup(urlopen(user.dl.dt.a['href']))
                    page = doc.findAll('a', attrs = {'rel' : 'friend'})
                    # находим друзей текущего пользователя и добавляем их в граф
                    if page:
                        for friend in page:
                            self.drawer.graph.add_nodes_from((user.dl.dt.a.string, friend.string))
                            self.drawer.graph.add_edge(user.dl.dt.a.string, friend.string)
                            print "Add edge (%s, %s)"%(user.dl.dt.a.string, friend.string)
                    else:
                        self.drawer.graph.add_node(user.dl.dt.a.string)
            except URLError:
                # иногда сразу страница не получается загрухить-попытаться снова
                i -= 1
        print 'Nodes: %s' %self.drawer.graph.size()
        self.drawer.draw()
if __name__ == '__main__':
    parse = Parser(end=8)
    parse.parse()


Для разбора страниц я использовал BeautifulSoup. Класс Drawer отвечает за хранение и отрисовку графа.

Отрисовка графа и сохранение изображения

Как уже было сказано выше, за хранение и отрисовку графа отвечает класс Drawer из модуля draw.py:

# -*- coding:utf-8 -*-
# draw.py
import networkx as nx
import matplotlib.pyplot as plt

class Drawer(object):
    def __init__(self, file_name = 'graph.png'):
        self.graph = nx.Graph()
        self.file_name = file_name
    def draw(self):
        '''
        отрисовываем граф с заданными параметрами
        '''
        nx.draw(self.graph,pos=nx.spring_layout(self.graph), node_size=3500, nodecolor='r',edge_color='b', node_shape='o')
        # устанавливаем размер изображения в дюймах
        plt.gcf().set_size_inches(100,100)
        plt.savefig(self.file_name)


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

Результаты

Результат проделанной работы, несколько отличается от планируюмых. В ходе работы скрипта, я выявил очень значительное потребление ресурсов. Как известно, примерное количество пользователей Хабра 60 000 человек. Даже если отбросить(как я собственно и делал) пользователей у которых отсутствуют друзья число всё равно значительное. Проверка работы программы осуществлялась на машине с 3 Гб оперативной памяти. Как только, начинается отрисовка графа, система начинала безбожно свопиться, поэтому число пользователей в графе пришлось сократить. В итоге я получил несколько версий отрисованного графа с разным количеством пользователей.
На рисунке представлен граф, содержащий 852 пользователя:


Как видите изображения приходится сильно сжимать для статьи, поэтому остальные приведу ссылками, ввиду большого размера изображений(7-14Мб):


Перспективы

  • Провести оптимизацию, и попытаться получить граф охватывающий всех пользователей.
  • На основании полученного графа проверить теорию 6 рукопожатий.


UPD: архив с изображениями

Извиняюсь за проблемы со скачиванием изображений, залил на народ.

UPD2: изображения на zoom.it

Спасибо пользователю mstyura за совет и содействие.
4095 пользователей
7071 пользователь.
Метки:
Поделиться публикацией
Похожие публикации
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 97
  • 0
    Используйте тег source lang="". Спасибо.
    • –22
      Лучшая оптимизация — написать всё на C
      • +14
        Я вот очень люблю С\С++ но прикинул так на глазок сколько бы занял parser.py на чистом С — вышло раз в 5 больше кода. Так зачем?
        • +7
          Т.е. не весь проект, а обработку результатов.
          • НЛО прилетело и опубликовало эту надпись здесь
          • НЛО прилетело и опубликовало эту надпись здесь
          • +5
            Ваши изображения, приведенные ссылками, не открываются. Или это только у меня?
            • 0
              Не только у Вас. Что-то dropbox после последней оптимизации не хочет многое открывать.
              • 0
                оно открылось, его надо сохранить, бразуер почему-то не показывает его(у меня так)
              • 0
                они на дропбоксе, странно что не открываются. Изображения большие и на habrastorage залить нельзя. Может кто подскает нормальный хостинг картинок?
                • 0
                  Яндекс.Фотки
                  • 0
                    яндекс.фотки почему то тоже не загружает
                    • НЛО прилетело и опубликовало эту надпись здесь
                  • 0
                    Может лучше залить архивом на народ.ру
                  • 0
                    попробуйте i.zlowiki.ru — бесплатный хостинг картинок без излишних наворотов
                  • +6
                    У меня картинки загрузились, но браузер похоже в шоке от 20000x20000 и не отображает их.
                    В редакторе открываются.
                    • +7
                      Аналогично.

                      Может, автору стоило использовать формат SVG? Мне кажется, вышло бы значительно компактнее png.
                      • +5
                        Свг для графиков идеален. Особенно таких.
                        • 0
                          он то компактнее, но надо протестить всеравно.
                          в последнее время оптимизацией svg, по-моему, только опера занималась, остальные ударились в canvas
                        • 0
                          У меня сначала завис браузер, потом винда начала бешено свопить и зависла полностью :)
                          Через несколько минут всё само отвисло, я скачал картинку и открыл в фотошопе (стандартный просмотрщик сразу сказал, что не может).
                          • +5
                            OH SHI~

                            Я больше никогда не буду открывать большие картинки в браузере. До сих пор глючит.
                            • +1
                              Только 0 — это сколько? :)
                              • +1
                                Грустный у вас диск це :)
                                Может стоит его держать посвободнее?
                                • +11
                                  Замечательная, поучительная история, без сомнения достойная одного экрана скролла.
                              • +8
                                открыл в браузере — у того инфаркт
                                сохранил, открыл во вьювере — у винды инсульт
                                открыл в паинте — красота!
                                • 0
                                  паинт.нет имеется ввиду
                                  • 0
                                    У меня не получается, кидает Недостаточно памяти.
                                  • 0
                                    Что за браузеры с вьюерами у вас? :)
                                    У меня с оперой абсолютно ничего не случилось при открытии — просто пустота вместо картинки.
                                    Открыл в древнем ACDSee — нет проблем.
                                    • +2
                                      Да тут больше от железа зависит, ИМХО.
                                    • +7
                                      Блин, а я подумал и вправду paint откроет. Пожалел…
                                      • 0
                                        не, паинт отмирает. Но обнаружил, что Просмотрщик изображений и факсов еще тянет, даже зумит приемлемо
                                    • 0
                                      у меня нормально открывает, но после пяти-шести зумов вкладка умирает и больше не раегирует
                                      • +1
                                        В Опере открылось, правда вся система повисла.
                                        • +4
                                          Нормально чо:

                                          Подвинься, виндовс, мне надо картинку открыть.
                                                                           С ув. Опера
                                          
                                      • 0
                                        изображения очень большие, и браузер их попросту не может отобразить.
                                        Попробуй сохранить как объект, и открыть в каком нибудь навороченном вьювере.
                                        • –1
                                          FF6, win xp x64 — открывает меньше чем за минуту
                                      • +6
                                        начинается конкурс «найди себя на графе»
                                        • +4
                                          первая мысль воспользоватся поиском, но очень быстро приходит разочарование :(
                                          • +4
                                            А будь оно в SVG или PDF — и поиск бы работал.
                                            • 0
                                              Думается, тогда и проблемы с количеством пикселей в картинке 20к х 20к — не было б.
                                              Векторный формат в данном конкретном случае кажется мне более соответствующим.
                                          • +3
                                            Воооон, вижу вас! )
                                          • +13
                                            А вы не пробовали сначала нормально пропарсить пользователей откладывая результаты например в SQLite и уже по полученным данным рисовать граф? А так как вы сделали неудивительно, что у вас всё быстро начало тормозить.
                                            • +6
                                              + было бы реюзабельно.
                                              • 0
                                                Мне кажется не помогло бы.

                                                Для алгоритмах на графах очень четко действует баланс «память-скорость». Да, можно все хранить в базе/на диске и при всякой необходимости лезть туда. А таких необходимостей будет ой как много. Соответственно тормоза.

                                                Можно держать в памяти. Но если у вас не 64-bit с 8-16 гигами то о больших графах даже и не думайте.

                                                Можно переписать на с++ — у него требования к памяти не такие убийственные как у структур питона или перла, но все равно это временная оптимизация.
                                                • 0
                                                  Мне почему-то думается, что использование SQLite и graphviz даже не кашлянули на 70 000 узлах. Количество связей, скорее всего отличается от кол-ва пользователей не более чем на 1 или 2 порядка.
                                                  • 0
                                                    *что если бы были использованы SQLite и graphiz, то они даже не кашлянули бы
                                                • 0
                                                  Пробывал, только хранил в MongoDB, просто тормаза начинались на этапе отрисовки — то бишь работы networkx. В перспективе — попробую оптимизовать и переработать изображения, что бы не казались «скомканными»
                                                • –5
                                                  По поводу теории 6 рукопожатий советую не учитывать пользователей у которых 0 друзей, т.к. они видимо просто не заинтересованы добавлять…
                                                  • +2
                                                    Пользователей у которых нет друзей, мой скрипт не добавляет в граф, так как было бы много «висячих» вершин
                                                • –3
                                                  Надо теперь объявить конкурс: «Найди себя на картинке»
                                                  • +1
                                                    Буквально в пятницу на работе об этом говорили, только касательно соц. сетей в целом.
                                                    Теперь можно сделать сервис, который будет по имени пользователя выдавать его социальный граф.
                                                    • 0
                                                      На 7071 все в куче больше половины картинки 20000х20000 просто пустует, зато пользователи полезли друг на друга, в итоге как писали выше в игру «найти себя на графе» играть почти невозможно…
                                                      • +6
                                                        Зато картинка напоминает логотип хабры :)
                                                      • +9
                                                        Мне одному кажется, что визуализация графа выбрана какая-то, мягко говоря, не самая удачная? Даже тот же Graphviz dotty или neato даст скорее всего что-то более адекватное.
                                                        • +6
                                                          именно для таких случаев — когда важна лишь структура связей, а не надписи — придумали www.gephi.org
                                                      • +1
                                                        самая первая картинка чем-то похожа на два полушария мозга. вот вам и искусственный интеллект ))
                                                        • –1
                                                          Хм, забавно, недавно делал то же самое, но на php.
                                                          А 6 рукопожатий так и не доаделал, по причине медленного алгоритма поиска кратчайших путей. Так же можно вычислять возможных друзей хабрапользователя.
                                                          • 0
                                                            при 60 тысячах вершин будет месиво на картинке и такие изображения лучше в векторе хранить
                                                            • 0
                                                              Вектор наверно решение, и с масштабированием проблем не будет… И как развитие идеи, можно наверно даже что то типа Гугл Земля, только с пользователями).
                                                            • +2
                                                              Было бы классно в каком-нибудь векторном формате сохранить. И поиск бы по тексту работал бы, и места столько не съело бы.
                                                              • 0
                                                                Спасибо за совет, постараюсь исправить все огрехи по работе с изображениями. О векторе, к своему стыду, я почему то не подумал.
                                                              • 0
                                                                поле одуванчиков
                                                                • +8
                                                                  Введите ваши данные в gephi.org и перестаньте насиловать комп! Эта замечательная программа в состоянии отриовать 60к точек за удвительно разумное время
                                                                  • 0
                                                                    Интересный эксперимент. Интересно было бы посмотреть на граф контакта или фейсбука… и при этом увидеть в каком месте находится конкретный пользователь… =)
                                                                    • 0
                                                                      в таком случае еще и к карте привязать бы хоть примерно
                                                                      • 0
                                                                        я имел ввиду не про географию, а про место в графе =)
                                                                        • 0
                                                                          я понял, но интереснее еще с географией, чтобы мог сказать: «О, я через 3 человек знаком с каким-нибудь австралийцем» и всё-таки какие-нибудь прикольные фишки проглядеть))
                                                                    • 0
                                                                      Dropbox невыдержал, 509 error :-(
                                                                      • +3
                                                                        Интересно. А можно сделать такой же граф, только на основе того, кто чьи статьи комментирует? Так сказать, связь по интересам.
                                                                        • +1
                                                                          Так вы уж сразу ализара можете вставить в середину…
                                                                        • +4
                                                                          А зачем нужны друзья на Хабре? Что это даёт в практическом плане?
                                                                          • +1
                                                                            Ничего. Но хабра вроде как соц. сеть, поэтому без этого никуда.
                                                                            • 0
                                                                              Даже отдельной ленты друзей нет?
                                                                              • 0
                                                                                Посты друзей попадают в Хабраленту 3.0. Удобно добавлять тех, чьи посты нравятся.
                                                                            • –1
                                                                              на мозги похоже
                                                                              • 0
                                                                                ага, большие картинки похожи на взорванный неземной мозг (по бокам — ошмётки)

                                                                                видимо, НЛО не выдержало
                                                                              • 0
                                                                                BeautifulSoup? — чем быстрее перейдёте на lxml, тем меньше потратите времени и нервов в итоге.
                                                                                • 0
                                                                                  А чем последний (lxml) лучше? Интересуюсь, как старый юзер BSoup'а.
                                                                                  Ведь проблемы производительности были уже не в парсинге, а в отрисовке графа?
                                                                                  • 0
                                                                                    «А чем последний (lxml) лучше? Интересуюсь, как старый юзер BSoup'а.»

                                                                                    я и сам был такой :)

                                                                                    вечный линк на irc freenode #python говорит:

                                                                                    When parsing XML or HTML, use the lxml library
                                                                                    lxml is probably the best library for XML and HTML parsing available. Its lxml.etree module is API-compatible with the stdlib ElementTree module, while providing many extensions such as full XPath support, XSLT support, and DTD/schema validation. Its HTML support (in lxml.html) is both fast and correct, optionally using either html5lib or BeautifulSoup for corner cases. See Ian Bicking's post about its HTML abilities.


                                                                                    далее, любой затык с BS и на ваш вопрос по нему в irc-чате начинается дурацкое дежа вю: «а чё не lxml? a чё BS? если бы lxml, то мог бы глянуть ;)»

                                                                                    и наконец быстрее lxml, намного быстрее.
                                                                                    • 0
                                                                                      «Ведь проблемы производительности были уже не в парсинге, а в отрисовке графа?»

                                                                                      это верно (впрочем, если вредничать, то не столько в отрисовке, сколько в рендеринге/разводке).

                                                                                      Вообще, если говорить в контексте графов, то несмотря на 2011 год ситуация совершенно незрелая. Бодаясь с graphviz можно вполне полезно работать с графами невысокой связности до тысячи вершин. выше — пэйн в жо. matplotlib'ом пользовался меньше, но там та же ситуация. а что делать если даже для невысокой связности вершин на порядки больше? А мне такое часто было надо по работе.

                                                                                      Давно уже нужен серьезный динамический графброузер с on-fly rendering. Героев нет :)
                                                                                  • +1
                                                                                    что у вас за формат такой, 7 Мб файл вгоняет систему в ступор, когда снимки неба по 250 Мб открывались нормально?
                                                                                    • 0
                                                                                      Эффектнее будет, если каждого пользователя сделать не как круг, а как маленькие частички. Рядом с пользователями у которых много друзей можно написать ихние ники. И отрисовываться будет быстрее. А еще можно рендеринг графа переписать на C, используя OpenGL или DirectX — получится вполне сносно.
                                                                                      • 0
                                                                                        eax.me/graphviz/ — это должно решить проблему с нехваткой памяти
                                                                                        • 0
                                                                                          Исследование интересное, но выборка вряд ли будет показательной. Основная причина в том, что habr в первую очередь пространство для публикаций и обсуждений, а уже потом социальная сеть. Предполагаю, что многие здесь имеют контакты, но не стремятся их найти и добавить в друзья.

                                                                                          Вот если бы взять граф вконтакте или facebook, то на них можно смело проверять теорию «6 рукопожатий» и её достоверность.
                                                                                          • +1
                                                                                            Судя по приведённым графам, большинству банально лень указывать друзей т.к. особых преимуществ от этого никаких.
                                                                                            • 0
                                                                                              Лучше бы Контакт распарсил)))
                                                                                              • 0
                                                                                                У Вас вместо целей перечислены задачи. Было бы интересно узнать цели — зачем Вы это делали?

                                                                                                И как именно Вы будете проверять «теорию», в которой говорится о всех людях не земле, на весьма специфическом срезе из 60000 человек?
                                                                                                • 0
                                                                                                  Зачем я это делал — просто для интереса, и наработки скилла. Никаких глобальных целей не преследовал.
                                                                                                  Проверять на выборке из 60 000 человек я думаю самое то. Вас не устраивает размер выборки, или то что выборка «специфичная»?
                                                                                                  • 0
                                                                                                    Прошу прощения, промахнулся и ответил в общую ленту.
                                                                                                • 0
                                                                                                  Спасибо, теперь цель ясна. Стоило именно её указать как цель, а перечисленные цели — это задачи.

                                                                                                  «Самое то»? Давайте рассмотрим аналогию. Пусть есть теория, что средний рост всех людей в мире — 166 см. А теперь представьте, что я решил её проверить на 60000 китайцах, или на 60000 баскетболистах, или на 60000 учёных. Для китайцев я, скрорей всего, получу меньшее среднее значение, для баскетболистов — большее, для учёных — вероятно, такое же.

                                                                                                  Но никакой из этих результатов абсолютно ничего не сможет сказать о теории среднего роста всех людей в мире.

                                                                                                  Получается, что я просто хожу с рулеткой и меряю всех прохожих. Просто для интереса и наработки скилла измерения людей рулеткой.
                                                                                                  • 0
                                                                                                    А я и не претендую на примере хабра доказать/опровергнуть теорию 6 рукопожатий. Мне просто интересно — выполняется это правило в конкретно определённом комьюнити или нет:) Я не собираюсь делать никакой аналогии и экстраполяции результатов на весь мир и на всю человеческую популяцию.
                                                                                                    Не ищите сложностей в простом:)
                                                                                                    • 0
                                                                                                      Я не ищу сложностей, я ищу смысл. Которого не особо много и в исходной теории, а в исследовании произвольных выборок на предмет средней длины всех возможных цепочек из вершин графа — и вовсе нет.

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

                                                                                                    Спасибо, весьма интересно. Не думал, что Хабр так легко парсится.

                                                                                                    Вообще, NetworkX очень хороший пакет для анализа социальных сетей и соответствующих методик. Можно, например, выявить различные «клики» юзеров или «лидеров мнений».

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

                                                                                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.