Nombre de communautés «Quoi?» O?? Quand? »(ChGK) ou combien de poignées de main avant un ami?

Bonjour, Habr!

Les vacances du Nouvel An sont le moment idéal pour prendre une pause de l'informatique Utilisez des compétences professionnelles dans votre passe-temps préféré. En fouillant sur le site de la cote sportive ChGK , j'ai trouvé une excellente API qui vous permet d'obtenir des données sur tous les jeux de tous les tournois. J'ai donc eu l'idée de construire un graphique de la communauté d'experts et de tester la théorie des six poignées de main sur une communauté géographiquement dispersée et strictement hors ligne. Sous katom des images de graphiques et de statistiques inutiles.

Pour commencer, un bref programme éducatif, qu'est-ce que le sport ChGK.

Récupération de données

Nous supposons que les joueurs se connaissent bien s'ils ont joué au moins une fois sur une table de jeu. Grâce à la bonne API, le téléchargement de données sur tous les tournois et toutes les équipes n'est pas un problème.

Sous les spoilers, même la Beautiful Soup n'est pas utilisée, seulement les demandes. Un cahier jupyter avec tout le code source sera à la fin de l'article.

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

Il reste à télécharger les listes de jeu de tous les tournois et à se souvenir de toutes les connaissances. Au départ, j'avais prévu de stocker les faits d'un jeu en commun dans un DataFrame, mais la vitesse d'ajout de nouveaux enregistrements était déprimante. Par conséquent, nous allons définir à partir de tuples (id1, id2), où id1, id2 sont les identifiants des joueurs qui se connaissent. En même temps, débarrassez-vous des doublons.

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

Obtenir un graphique et explorer les composants connectés

La préparation des données est donc terminée, il est temps de construire un graphique! Pour ce faire, nous utiliserons la bibliothèque networkx , dont les capacités sont tout à fait suffisantes pour notre cluster.

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

Maintenant, il y a environ deux cent mille personnes dans la communauté ChGK, et en moyenne, un expert sur une carrière a joué avec 12 personnes:

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

Il est temps de découvrir le nombre de composants connectés dans le graphique de datation. Networkx a une excellente fonction appelée connected_components qui fait exactement ce dont vous avez besoin:

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

Près des trois quarts des joueurs sont dans un composant connecté, les autres sont divisés en très petits sous-graphiques. Il y en a plus de huit mille.

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

Même à l'échelle logarithmique, la dominance de la composante principale semble impressionnante. Sur l'axe X - le numéro du composant du plus grand au moins, sur l'axe Y - sa taille (l'axe logarithmique).

Qu'est-ce qui a causé une telle répartition inégale des personnes dans les composants connectés? À mon avis, le point est le suivant:

• un petit groupe de personnes vient pour la première fois au jeu et forme ainsi un petit groupe pour 4-6 personnes;
• si la ville a déjà une grande communauté, un tel cluster fusionnera très rapidement avec le principal - une seule personne doit jouer pour une équipe du cluster principal;
• si dans la ville de ChGK vient d'apparaître, le cluster vivra plus longtemps, car jouer pour une équipe du cluster principal est plus difficile.

Le processus ressemble à la formation de gouttes de pluie dans les nuages: une grosse goutte attire les petites et se développe rapidement.

Avant de traiter du composant principal, regardons les composants en première ou neuvième place (je considère que le composant principal est nul). Nous testons l'hypothèse que les habitants de ces composantes sont de la même ville. Le connaisseur n'a aucun attachement à la ville (ce qui est logique dans notre monde moderne). Cependant, vous pouvez regarder le port d'attache de l'équipe pour laquelle il a joué pour la dernière fois

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

Plaque de résumé:

Oui, les petites grappes proviennent presque entièrement d'une seule ville. Veuillez prêter attention à la composante de soixante-douze résidents de Tambov, qui est associée au Luxembourg. Aux septième et neuvième places se trouvent des composants de Gorno-Altaysk, qui pour une raison quelconque ne sont pas interconnectés. J'imagine facilement la lutte de deux clans ChGK-ash, comme Montecca et Capulet, qui se battent pour le contrôle de la ville.
Je suppose que dans un avenir proche, ces composants fusionneront dans le principal mais continuera à se battre .

Le principal composant de la connectivité

Nous sommes donc arrivés au composant principal. Nous obtiendrons le sous-graphique souhaité et regarderons ses statistiques:

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

Le nombre moyen de connexions s'est avéré être plus.

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

Et quel est le nombre maximum de connexions par joueur?

 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  

Franchement, je suis un peu choqué par les chiffres. Si vous jouez avec une nouvelle équipe à chaque fois, vous aurez besoin de 818/5 ≈ 164 matchs pour atteindre la première place. Incroyable.
Nous nous souviendrons des deux premiers experts de cette notation et utiliserons davantage leurs compétences en communication.
Estimons le nombre de connaissances les plus proches d'un expert moyen:

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

Sur l'axe X - le nombre de connaissances les plus proches, sur l'axe Y - le nombre d'experts qui ont le nombre correspondant de connaissances. Par exemple, environ 40 000 experts ont chacun cinq connaissances.
Notez que la mode a 5 connaissances (c'est drôle que jusqu'à six personnes puissent être à table). Dans le même temps, la moyenne arithmétique du nombre de connaissances est de 14,67 et la médiane est de 7. Le fait est que les messieurs de la notation ci-dessus surestiment largement la moyenne. Si une centaine de personnes ne jouent pas en ChGK, et qu'une a 800 connaissances, alors en moyenne elles jouent en ChGK.

Distances par rapport aux joueurs

Parce que compter le diamètre d'un tel graphique est un peu difficile , faisons-le plus facilement: prenez une liste de plusieurs joueurs et trouvez le maximum des distances les plus courtes entre eux et d'autres experts. En tant que ces joueurs, j'ai pris plusieurs experts bien connus, moi-même, un joueur au hasard et deux experts avec le plus grand nombre de connaissances (voir note ci-dessus). Voici ce qui s'est passé:

 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 -       

Il s'avère qu'une formulation forte de la théorie des six poignées de main (deux personnes quelconques sont séparées par pas plus de cinq niveaux d'amis communs) est incorrecte. Le diamètre du graphique est très probablement 13-14.
Qu'en est-il d'une formulation plus faible (deux personnes en moyenne sont séparées par pas plus de cinq niveaux d'amis communs)?

 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 -       

Si nous desserrons le libellé, alors la théorie est remplie - en moyenne entre experts sur 4-5 niveaux de connaissances. Nous traçons le nombre de personnes qui connaissent le connaisseur aléatoire A. Druzem directement, à travers un, deux, etc. connaisseurs.

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

Sur l'axe X, le degré de connaissance avec A. Druzem (directement, à travers un, deux, etc.), sur l'axe Y, le nombre d'experts qui connaissent A. Druzem de cette manière.

Graphiques sociaux

Parce que construire un graphique pour près de 200 000 personnes n'est pas une bonne idée, nous allons vous faciliter la tâche: nous allons construire le composant de connectivité Kerch et un graphique des personnes associées à l'auteur.

Composant Kerch

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

Vous pouvez voir la séparation des composants en équipes. De plus, les équipes sont interconnectées avec l'aide, en règle générale, d'un ou deux connaisseurs sociables. Au centre se trouve un noyau d'experts assez restreint qui a joué avec un grand nombre d'autres joueurs.

Nombre d'une personne

Nous trouverons les connaissances les plus proches d'une personne et verrons comment elles sont liées. Pour simplifier le graphique, nous n'ajouterons pas la personne elle-même (elle est déjà connectée avec tout le monde)

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

Le graphique est beaucoup plus dense, un noyau de 10 à 15 personnes qui se connaissent se distingue. La taille de clic maximale est de 13.

Conclusion

• Il est beaucoup plus difficile d'apprendre à connaître une personne dans le sport ChGK que sur un réseau social, vous devez vous déconnecter et jouer à au moins un tournoi. Dans le même temps, les experts sont dispersés à travers le monde. Cependant, la distance moyenne entre experts est en effet inférieure à cinq.
• Le site de notation utilise le numéro Snyatkovsky , qui est un analogue du numéro Erdös dans le monde de ChGK. M. Snyatkovsky lui-même prend la troisième place dans notre classement des connaisseurs les plus sociables.
• Code d'un article dans mon github .
• Pour ses précieux commentaires, l'auteur remercie le White Noise et Who Framed Roger Federer, Mikhail Akulov, Vera Terentyeva et Firemoon .