Хабрахабр

Граф сообщества «Что? Где? Когда?» (ЧГК) или сколько рукопожатий до Друзя?

Привет, Хабр!

Ковыряясь на сайте рейтинга спортивного ЧГК, я обнаружил отличный API, позволяющий получить данные о всех играх всех турниров. Новогодние праздники — отличное время, чтобы отдохнуть от IT использовать профессиональные навыки в любимом хобби. Под катом картинки графов и бесполезная статистика. Так у меня появилась идея построить граф сообщества знатоков и проверить теорию шести рукопожатий на географически разбросанном и строго оффлайновом коммьюнити.

Для начала краткий ликбез, что такое спортивное ЧГК.

Что такое спортивное ЧГК

Турнин по спортивному ЧГК

Где? Уверен, что с телевизионной версией «Что? Спортивное ЧГК — это расширение телевизионного формата, позволяющее играть нескольким командам одновременно. Когда?» с волчком и письмами телезрительниц читатель знаком.

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

А примеры вопросов можно найти тут. Существует много турниров по ЧГК, есть даже чемпионат Европы и мира, любопытных отсылаю к авторитетнейшему источнику информации.

Получение данных

Благодаря хорошему API скачивание данных о всех турнирах и всех командах не представляет проблем. Будем считать, что игроки знакомы друг с другом, если они сыграли хотя бы раз за одним игровым столом.

Jupyter notebook со всем исходным кодом будет в конце статьи. Под спойлерами не используется даже Beautiful Soup, только requests.

Скачивание данных о всех турнирах

url = 'https://rating.chgk.info/api/tournaments.json/?page='
df = pd.DataFrame(columns=['name', 'start'])
for i in range(1, 7): data = requests.get(url.format(i)).json() for item in data["items"]: df.loc[item["idtournament"]] = (item["name"], item["date_start"])
df.to_csv('tournaments.csv')

Первоначально я планировал хранить факты совместной игры в DataFrame, однако скорость добавления новых записей оказалось удручающей. Осталось скачать игровые составы всех турниров и запомнить все знакомства. Заодно избавимся от дубликатов. Поэтому заведём set из tuple'ов (id1, id2), где id1, id2 — идентификаторы игроков, знакомых между собой.

Скачивание составов и формирование знакомств

df = pd.read_csv('tournaments.csv').set_index('Unnamed: 0')
url = 'https://rating.chgk.info/api/tournaments/{}/recaps.json'
links = set()
for id in df.index: teams = requests.get(url.format(id)).json() for team in teams: t = team["recaps"] for i in range(len(t)): for j in range(i + 1, len(t)): first = int(t[i]["idplayer"]) second = int(t[j]["idplayer"]) if first < second: links.add((first, second)) else: links.add((second, first)) # побережём сайт рейтинга sleep(1) clear_output(wait=True) display('Current tournament: ' + str(df.index.get_loc(id) + 1) + '/' + str(len(df))) display('Links total: ' + str(len(links)))

Получение графа и исследование компонент связности

Для этого воспользуемся библиотекой networkx, возможностей которой вполне достаточно для нашего кластера. Итак, с подготовкой данных покончено, пора строить граф!

players = itertools.chain(*links)
G = nx.Graph()
G.add_nodes_from(players)
for t in links: G.add_edge(*t)
print(nx.info(G))

Сейчас в сообществе ЧГК около двухсот тысяч человек, а в среднем знаток за карьеру играл с 12 людьми:

Number of nodes: 198145
Number of edges: 1206076
Average degree: 12.1737

В networkx есть замечательная функция connected_components, которая делает как раз то, что нужно: Пришло время узнать, сколько компонент связности есть в графе знакомств.

clusters_l = [len(c) for c in sorted(nx.connected_components(G), key=len, reverse=True)]
print(clusters_l[:20])

Всего их более восьми тысяч. Почти три четверти игроков состоят в одной компоненте связности, остальные разбиты по очень маленьким подграфам.

[145922, 153, 124, 74, 72, 56, 50, 47, 42, 40, 39, 39, 38, 38, 37, 36, 36, 36, 36, 35]

По оси Х — номер компоненты от большей к меньшей, по оси Y — её размер (ось логарифмическая). Даже в логарифмическом масштабе доминирование главной компоненты выглядит внушительно.

На мой взгляд, дело в следующем: Чем же вызвано такое неравномерное распределение людей по связным компонентам?

  • небольшая группа людей первый раз приходит на игру и тем самым образует небольшой кластер на 4-6 человек;
  • если в городе уже есть большое коммьюнити, такой кластер очень быстро сольётся с главным — достаточно всего одному человеку сыграть за команду из основного кластера;
  • если же в городе ЧГК только появилось, кластер проживёт дольше, т.к. сыграть за команду из основного кластера сложнее.

Процесс напоминает образование дождевых капель в облаках: большая капля притягивает маленькие и быстро растёт.

Проверим гипотезу, что люди в этих компонентах из одного города. Прежде чем заняться основном компонентой, давайте посмотрим на компоненты на первом-девятом месте (считаю основную компоненту нулевой). Однако можно посмотреть на порт приписки команды, за которую он играл в последний раз У знатока нет привязки к городу (что логично в нашем современном мире).

Код получения статистики о городах

for i in range(1, 10): _g = list(sorted(nx.connected_components(G), key=len, reverse=True)[i]) s = pd.Series() p_url = 'https://rating.chgk.info/api/players/{}/tournaments.json' t_url = 'https://rating.chgk.info/api/teams/{}.json' for player in _g: data = requests.get(p_url.format(player)).json() for item in data: team_id = data[item]["tournaments"][0]["idteam"] data = requests.get(t_url.format(team_id)).json() town = data[0]["town"] s.at[len(s)] = town print('Кластер #{}'.format(i)) print(s.value_counts())

Итоговая табличка:

Прошу обратить внимание на компоненту из семидесяти двух тамбовчан, которая связана с Люксембургом. Да, малые кластеры почти полностью из одного города. Мне охотно представляется борьба двух ЧГК-ашных кланов, наподобие Монтекки и Капулетти, которые бьются за контроль над городом.
Предположу, что в ближайшем будущем эти компоненты вольются в состав основной, но будут продолжать бороться. На седьмом и девятом месте компоненты из Горно-Алтайска, которые почему-то не связаны между собой.

Основная компонента связности

Получим нужный подграф и посмотрим на его статистику: Итак, мы подобрались к основной компоненте.

subgraph_v = list(sorted(nx.connected_components(G), key=len, reverse=True)[0])
subgraph = G.subgraph(subgraph_v)
print(nx.info(subgraph))

Среднее число связей получилось больше.

Number of nodes: 145922
Number of edges: 1070504
Average degree: 14.6723

А каково максимальное количество связей одного игрока?

for t in sorted(G.degree, key=lambda x: x[1], reverse=True)[:10]: print('Игрок {} играл с {} игроками'.format(t[0], t[1]))

Игрок 42511 играл с 818 игроками
Игрок 15051 играл с 798 игроками
Игрок 29800 играл с 678 игроками
Игрок 23020 играл с 666 игроками
Игрок 16581 играл с 662 игроками
Игрок 5328 играл с 657 игроками
Игрок 29887 играл с 651 игроками
Игрок 15811 играл с 645 игроками
Игрок 30352 играл с 605 игроками
Игрок 1055 играл с 602 игроками

Если каждый раз играть с новой командой, то понадобится 818/5 ≈ 164 игры, чтобы выйти на первое место. Признаться, я немного шокирован полученными цифрами. Невероятно.
Первых двух знатоков в этом рейтинге мы запомним и будем использовать их коммуникативные навыки далее.
Давайте оценим, сколько ближайших знакомств у среднего знатока:

Получение данных и отрисовка графика

_count = 50
values = nx.degree_histogram(subgraph)
plt.figure(figsize=(16, 8), dpi=80)
plt.plot(range(_count),values[:_count],'ro-') # in-degree
plt.xlabel('Число знакомств', fontsize=18)
plt.xticks(range(0,_count, 5))
plt.ylabel('Число игроков', fontsize=18)
plt.title('Число знакомств', fontsize=22)
plt.show()

Например, по пять знакомств имеют приблизительно 40 000 знатоков.
Отметим, что мода — 5 знакомств (забавно, что за столом может находиться до шести человек). По оси X — число ближайших знакомств, по оси Y — количество знатоков, которое имеет соответствующее число знакомств. 67, а медиана — 7. При этом среднее арифметическое числа знакомств — 14. Если сто человек не играют в ЧГК, а один имеет 800 знакомств, то в среднем они играют в ЧГК. Дело в том, что господа из рейтинга выше сильно завышают среднее.

Расстояния до игроков

считать диаметр такого графа немного сложно, поступим проще: возьмём список из нескольких игроков и найдём максимальное из кратчайших расстояний от них до других знатоков. Т.к. рейтинг выше). В качестве этих игроков я взял нескольких известных знатоков, себя, случайного игрока и двух знатоков с наибольшим числом знакомств (см. Вот что получилось:

famous_players = {9808: 'Александр Друзь', 5195: 'Анатолий Вассерман', 25882: 'Максим Поташев', 29333: 'Михаил Скипский', 118622: 'Михаил Атепаев', 42511: 'Николай Некрылов', 15051: 'Георгий Коколия', 118621: 'Михаил Акулов'}
for key in famous_players: print('{}: {} - максимальное расстояние от игрока до других' .format(famous_players[key], nx.eccentricity(subgraph, v=key)))

Александр Друзь: 12 - максимальное расстояние от игрока до других
Анатолий Вассерман: 12 - максимальное расстояние от игрока до других
Максим Поташев: 12 - максимальное расстояние от игрока до других
Михаил Скипский: 12 - максимальное расстояние от игрока до других
Михаил Атепаев: 13 - максимальное расстояние от игрока до других
Николай Некрылов: 12 - максимальное расстояние от игрока до других
Георгий Коколия: 13 - максимальное расстояние от игрока до других
Михаил Акулов: 13 - максимальное расстояние от игрока до других

Диаметр графа, скорее всего, равен 13-14.
А что насчёт более слабой формулировки (любые два человека в среднем разделены не более чем пятью уровнями общих знакомых)? Получается, что сильная формулировка теории шести рукопожатий (любые два человека разделены не более чем пятью уровнями общих знакомых) неверна.

for key in famous_players: paths = nx.shortest_path_length(subgraph, source=key).values() print('{}: {} - среднее расстояние от игрока до других' .format(famous_players[key], sum(paths) / len(paths)))

Александр Друзь: 3.941461876893135 - среднее расстояние от игрока до других
Анатолий Вассерман: 3.7971107852140182 - среднее расстояние от игрока до других
Максим Поташев: 3.89353216101753 - среднее расстояние от игрока до других
Михаил Скипский: 3.8634887131481204 - среднее расстояние от игрока до других
Михаил Атепаев: 4.1443373857266215 - среднее расстояние от игрока до других
Николай Некрылов: 3.575478680390894 - среднее расстояние от игрока до других
Георгий Коколия: 3.608674497334192 - среднее расстояние от игрока до других
Михаил Акулов: 4.564102739819904 - среднее расстояние от игрока до других

Построим график, сколько людей знакомы со случайным знатоком А.Друзём напрямую, через одного, двух и т.д. Если ослабить формулировку, то теория выполняется — в среднем между знатоками 4-5 уровней знакомств. знатоков.

Получение данных и отрисовка графика

paths = nx.shortest_path_length(subgraph, source=9808)
neighbours = [0] * 15
for k in paths: neighbours[paths[k]] += 1 _count = 15
plt.figure(figsize=(16, 8), dpi=80)
plt.plot(range(_count),neighbours[:_count],'ro-') # in-degree
plt.xlabel('Степень рукопожатия', fontsize=18)
plt.xticks(range(_count))
plt.ylabel('Число игроков', fontsize=18)
plt.title('Число рукопожатий А.Друзя', fontsize=22)
plt.show()

По оси X степень знакомства с А.Друзём (напрямую, через одного, двух и т.д.), по оси Y — количество знатоков, которые знакомы с А.Друзём таким образом.

Социальные графы

строить граф на почти 200 тысяч человек не очень хорошая идея, сделаем проще: построим Керченскую компоненту связности и граф людей, связанных с автором. Т.к.

Керченская компонента

little_v = list(sorted(nx.connected_components(G), key=len, reverse=True)[1])
little = G.subgraph(little_v) plt.figure(figsize=(24, 12), dpi=200)
pos = nx.kamada_kawai_layout(little)
nx.draw(little, pos=pos, node_size=100, edge_color='gray', node_color=[val for (node, val) in little.degree()], cmap=plt.cm.jet)
plt.show()

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

Граф одного человека

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

id = 118622
ego_graph = [n for n in G.neighbors(id)]
#ego_graph.append(id)
ego_graph = G.subgraph(ego_graph) plt.figure(figsize=(24, 16), dpi=200)
pos = nx.kamada_kawai_layout(ego_graph)
nx.draw(ego_graph, pos=pos, node_size=100, edge_color='gray', node_color=[val for (node, val) in ego_graph.degree()], cmap=plt.cm.jet)
plt.show()

Размер максимальной клики равен 13. Граф существенно плотнее, различимо ядро из 10-15 человек, которые хорошо знакомы друг с другом.

Заключение

  • В спортивном ЧГК познакомиться с человеком значительно труднее, чем в социальной сети, необходимо выйти в оффлайн и сыграть хотя бы один турнир. При этом знатоки разбросаны по всему земному шару. Тем не менее, среднее расстояние между знатоками действительно меньше пяти.
  • На сайте рейтинга используется число Снятковского, которое является аналогом числа Эрдёша в мире ЧГК. Сам господин Снятковский занимает третье место в нашем рейтинге самых коммуникабельных знатоков.
  • Код из статьи в моём гитхабе.
  • За ценные замечания автор выражает благодарность командам "Белый шум" и "КПРФ", Михаилу Акулову, Вере Терентьевой и Firemoon.
Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»