Community-Zählung "Was?" Wo? Wann? “(ChGK) oder wie viele Handshakes vor einem Freund?

Hallo habr

Neujahrsferien sind eine gute Zeit, um Machen Sie eine Pause von der IT Verwenden Sie professionelle Fähigkeiten in Ihrem Lieblingshobby. Beim Stöbern auf der Seite mit dem Sport-ChGK-Rating habe ich eine hervorragende API gefunden, mit der Sie Daten zu allen Spielen aller Turniere abrufen können. So kam mir die Idee, ein Diagramm der Expertengemeinschaft zu erstellen und die Theorie von sechs Handshakes in einer geografisch verteilten und streng offline arbeitenden Community zu testen. Unter katom Bilder von Graphen und unbrauchbaren Statistiken.

Zunächst ein kurzes Bildungsprogramm, was Sport ChGK ist.

Datenabruf

Wir gehen davon aus, dass die Spieler miteinander vertraut sind, wenn sie mindestens einmal an einem Spieltisch gespielt haben. Dank der guten API ist das Herunterladen von Daten zu allen Turnieren und Teams kein Problem.

Unter den Spoilern wird nicht einmal Beautiful Soup verwendet, nur Nachfragen. Ein Jupyter-Notizbuch mit dem gesamten Quellcode wird am Ende des Artikels erscheinen.

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') 

Es bleibt noch Zeit, die Spielpläne aller Turniere herunterzuladen und sich an alle Bekannten zu erinnern. Ursprünglich wollte ich die Fakten eines gemeinsamen Spiels in einem DataFrame speichern, aber die Geschwindigkeit, mit der neue Datensätze hinzugefügt wurden, war bedrückend. Aus diesem Grund setzen wir Tupel (id1, id2), wobei id1, id2 die Bezeichner von Spielern sind, die mit einander vertraut sind. Gleichzeitig werden Sie Duplikate los.

 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))) 

Ein Diagramm erstellen und verbundene Komponenten untersuchen

Nach Abschluss der Datenvorbereitung ist es Zeit, ein Diagramm zu erstellen! Dazu verwenden wir die networkx- Bibliothek, deren Funktionen für unseren Cluster völlig ausreichen.

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

Mittlerweile gibt es in der ChGK-Community ungefähr zweihunderttausend Menschen, und im Durchschnitt hat ein Experte für eine Karriere mit 12 Menschen gespielt:

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

Es ist Zeit herauszufinden, wie viele verbundene Komponenten in der Datierungsgrafik enthalten sind. Networkx hat eine großartige Funktion namens connected_components, die genau das tut, was Sie brauchen:

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

Fast drei Viertel der Spieler befinden sich in einer zusammenhängenden Komponente, der Rest ist in sehr kleine Untergraphen unterteilt. Es gibt mehr als achttausend von ihnen.

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

Selbst im logarithmischen Maßstab sieht die Dominanz der Hauptkomponente beeindruckend aus. Auf der X-Achse - die Nummer der Komponente vom größten bis zum kleinsten, auf der Y-Achse - ihre Größe (die Achse ist logarithmisch).

Was hat eine so ungleichmäßige Verteilung der Personen in verbundenen Komponenten verursacht? Meiner Meinung nach geht es um Folgendes:

• Eine kleine Gruppe von Menschen kommt zum ersten Mal zum Spiel und bildet so einen kleinen Cluster für 4-6 Personen.
• Wenn die Stadt bereits eine große Gemeinde hat, verschmilzt ein solcher Cluster sehr schnell mit dem Hauptcluster. Nur eine Person muss für ein Team aus dem Hauptcluster spielen.
• Wenn in der Stadt ChGK gerade erschienen ist, wird der Cluster länger leben, weil Schwieriger ist es, für eine Mannschaft aus dem Hauptcluster zu spielen.

Der Prozess ähnelt der Bildung von Regentropfen in den Wolken: Ein großer Tropfen zieht kleine Tropfen an und wächst schnell.

Bevor wir uns mit der Hauptkomponente befassen, schauen wir uns die Komponenten an erster oder neunter Stelle an (ich betrachte die Hauptkomponente als Null). Wir testen die Hypothese, dass die Menschen in diesen Komponenten aus derselben Stadt stammen. Der Kenner hat keine Bindung an die Stadt (was in unserer modernen Welt logisch ist). Sie können sich jedoch den Heimathafen der Mannschaft ansehen, für die er das letzte Mal gespielt hat

 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()) 

Zusammenfassung Platte:

Ja, kleine Gruppen stammen fast ausschließlich aus einer Stadt. Bitte beachten Sie die Komponente von zweiundsiebzig Tambow-Bewohnern, die mit Luxemburg verbunden ist. Auf den Plätzen sieben und neun befinden sich Komponenten von Gorno-Altaisk, die aus irgendeinem Grund nicht miteinander verbunden sind. Ich stelle mir den Kampf zweier ChGK-Ash-Clans wie Montecca und Capulet vor, die um die Kontrolle über die Stadt kämpfen.
Ich nehme an, dass diese Komponenten in naher Zukunft in die Hauptkomponente übergehen werden werde aber weiter kämpfen .

Die Hauptkomponente der Konnektivität

Also kamen wir zur Hauptkomponente. Wir erhalten den gewünschten Subgraphen und sehen uns dessen Statistiken an:

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

Es stellte sich heraus, dass die durchschnittliche Anzahl der Verbindungen höher war.

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

Und was ist die maximale Anzahl von Verbindungen pro Spieler?

 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  

Ehrlich gesagt bin ich ein bisschen schockiert von den Zahlen. Wenn Sie jedes Mal mit einer neuen Mannschaft spielen, benötigen Sie 818/5 ≈ 164 Spiele, um den ersten Platz zu erreichen. Unglaublich.
Wir werden uns an die ersten beiden Experten in diesem Rating erinnern und ihre Kommunikationsfähigkeiten weiter einsetzen.
Lassen Sie uns schätzen, wie viele engste Bekannte ein Durchschnittsfachmann hat:

 _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() 

Auf der X-Achse - die Anzahl der nächsten Bekannten, auf der Y-Achse - die Anzahl der Experten, die über die entsprechende Anzahl von Bekannten verfügen. Zum Beispiel haben ungefähr 40.000 Experten jeweils fünf Bekannte.
Beachten Sie, dass die Mode 5 Bekannte hat (es ist lustig, dass bis zu sechs Personen am Tisch sitzen können). Gleichzeitig beträgt der arithmetische Durchschnitt der Anzahl der Bekannten 14,67 und der Median 7. Fakt ist, dass die Herren aus der obigen Bewertung den Durchschnitt stark überschätzen. Wenn hundert Leute nicht in ChGK spielen und man 800 Bekannte hat, dann spielen sie im Durchschnitt in ChGK.

Entfernungen zu den Spielern

Weil Den Durchmesser eines solchen Graphen zu bestimmen, ist etwas schwierig . Machen wir es uns leichter: Nehmen Sie eine Liste mit mehreren Spielern und finden Sie das Maximum der kürzesten Entfernungen von ihnen zu anderen Experten. Als diese Spieler habe ich einige bekannte Experten genommen, mich selbst, einen zufälligen Spieler und zwei Experten mit der größten Anzahl an Bekannten (siehe Bewertung oben). Folgendes ist passiert:

 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 -       

Es stellt sich heraus, dass eine starke Formulierung der Theorie von sechs Handshakes (zwei Personen sind durch nicht mehr als fünf Ebenen gemeinsamer Freunde getrennt) falsch ist. Der Durchmesser des Diagramms beträgt höchstwahrscheinlich 13-14.
Was ist mit einer schwächeren Formulierung (zwei Personen sind durchschnittlich durch nicht mehr als fünf Ebenen gemeinsamer Freunde getrennt)?

 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 -       

Wenn wir den Wortlaut lockern, ist die Theorie erfüllt - im Durchschnitt zwischen Experten auf 4-5 Ebenen von Bekannten. Wir zeichnen auf, wie viele Leute den zufälligen Kenner A. Druzem direkt kennen, durch einen, zwei usw. Kenner.

 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() 

Auf der X-Achse der Bekanntheitsgrad von A. Druzem (direkt, durch eine, zwei usw.), auf der Y-Achse die Anzahl der Experten, die mit A. Druzem auf diese Weise vertraut sind.

Soziale Graphen

Weil Es ist keine gute Idee, ein Diagramm für fast 200.000 Personen zu erstellen. Wir machen es einfacher: Wir werden die Kerch-Konnektivitätskomponente und ein Diagramm der Personen erstellen, die dem Autor zugeordnet sind.

Kertsch-Komponente

 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() 

Sie können die Aufteilung der Komponenten in Teams sehen. Darüber hinaus sind die Teams in der Regel durch ein oder zwei gesellige Kenner miteinander verbunden. In der Mitte befindet sich ein eher kleiner Kern von Experten, die mit einer großen Anzahl anderer Spieler spielten.

Zählung von einer Person

Wir werden die engsten Bekannten einer Person finden und sehen, wie sie miteinander verwandt sind. Um das Diagramm zu vereinfachen, werden wir die Person nicht selbst hinzufügen (sie ist bereits mit allen verbunden).

 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() 

Die Grafik ist viel dichter, ein Kern von 10-15 Personen, die sich auskennen, ist erkennbar. Die maximale Klickgröße beträgt 13.

Fazit

• Es ist viel schwieriger, eine Person in der Sport-ChGK kennenzulernen als in einem sozialen Netzwerk. Sie müssen offline gehen und mindestens ein Turnier spielen. Gleichzeitig sind Experten auf der ganzen Welt verteilt. Die durchschnittliche Entfernung zwischen Experten beträgt jedoch weniger als fünf.
• Die Bewertungsseite verwendet die Snyatkovsky-Nummer , die der Erdös-Nummer in der Welt von ChGK entspricht. Herr Snyatkovsky selbst belegt in unserer Rangliste der geselligsten Kenner den dritten Platz.
• Code aus einem Artikel in meinem Github .
• Für wertvolle Kommentare dankt der Autor Roger Federer, Mikhail Akulov, Vera Terentyeva und Firemoon .