La Théorie Des Graphes: Le Calcul De Coefficient De Clustering

J'ai fais quelques recherches et je suis arrivé à un point où j'ai calculer le coefficient de clustering de graphe.

Selon ce document directement liées à ma recherche:

Le clustering coefficient C(p) est
définis comme suit. Supposons qu'un
sommet v a kv voisins; puis, à
la plupart (kv * (kv-1)) /2 arêtes peuvent
existent entre eux (ce qui se produit lorsque
chaque voisin de v est connecté à
tous les autres voisins de v). Laissez-Cv
indiquer la fraction de ces admissible
bords qui existent réellement. Définir C comme
la moyenne de Cv sur tous les v

Mais cet article de wikipédia sur le sujet, dit différemment:

C = (nombre de triplets) /(nombre de connectés triples)

Il me semble que ce dernier est plus gourmand en ressources.

Donc ma question est: sont-ils équivalents?

Il convient de noter que le document est cité par l'article de Wikipedia.

Merci pour votre temps.

Il y a un site pour que cstheory.stackexchange.com
Ah, je ne savais pas à ce sujet. Je demanderai la même chose là-bas. Merci
sûr? N'est-ce pas cstheory pour recherche niveau de CS? Je ne suis pas sûr qu'ils sont réceptifs à ce genre de question.
Peut appartenir simultanément sur math.stackexchange.com bien que
Je ne sais pas vraiment. Mais le top question sur leur page d'accueil est: "Que les hiérarchies et/ou des hiérarchies théorèmes savez-vous?" alors que je pense qu'il y répandre dans la qualité.

OriginalL'auteur Griffin | 2011-07-10

  1. 6

    Je pense qu'ils sont équivalents. La page wiki que vous lien donne une preuve que les triples formulation est équivalente à la fraction du possible les bords de la formulation lors du calcul de la local clustering coefficient, c'est à dire calculée simplement à un sommet. De là, il semble que vous avez juste besoin de montrer que

    sum_v lambda(v)/tau(v) = 3 x # triangles /# connected triples

    où lambda(v) est le nombre de triangles contenant v, et tau(v) est le nombre de connectés triples pour laquelle v est le milieu du vertex, c'est à dire adjacents les uns des autres 2 bords.

    Maintenant, chaque triangle est compté trois fois dans le numérateur de la LHS. Cependant, chacun connecté triple est comptabilisé qu'une seule fois pour le milieu de vertex sur la GAUCHE, de sorte que les dénominateurs sont les mêmes.

    Je vais devoir revenir frais demain pour aller au-dessus de ce que vous avez dit de nouveau. En regardant en bas de la page, cependant, il semble que c'est "à la moyenne du Réseau de clustering coefficient" je suis à la recherche d'. Depuis la page prouve que les deux méthodes sont équivalentes pour le regroupement local coefficint. Et que la moyenne du Réseau de clustering coefficient est simplement la moyenne de l'ensemble du cluster local coefficients. Il semblerait que les deux méthodes sont équivalentes, puisque la méthode dans l'étude et la citation dans cet article sont issus des mêmes auteurs (Watts et Strogatz). Qu'en dites-vous?
    Ouais, la moyenne du réseau est ce que vous êtes en train de regarder. Vous avez juste besoin de prouver que la somme de la moyenne du réseau à l'aide de la fraction de bords formulation est équivalente à la mondiaux de clustering coefficient présentées dans la partie supérieure de la page - c'est ce que ma réponse est en train de faire.
    Il semble donc que je dois marquer votre réponse acceptée, oui?
    Eh bien, si vous vous sentez que vous voulez l'accepter, oui 😛 Mais n'hésitez pas à travailler à travers et vous convaincre que je suis le premier à droite!
    Ok, merci beaucoup pour votre aide. J'en ferai part demain.

    OriginalL'auteur Whatang

  2. 9

    Les deux formules ne sont pas les mêmes; ils sont deux manières différentes dans le clustering coefficient peut être calculé.

    L'une d'elles est la moyenne des coefficients de clustering (C_i [1]) de tous les nœuds (c'est la méthode que vous avez cité de Watts et Strogatz). Cependant, dans [2, p204] Newman affirme que cette méthode est moins avantageux que le second (celui que vous avez obtenu de wikipedia). Il justifie en soulignant comment la valeur de la mondial de clustering coefficient peut être dominé par des nœuds de faible degré, en raison de C_i du dénominateur [1]. Ainsi, dans un réseau avec de nombreux nœuds de faibles degrés, vous vous retrouvez avec une grande valeur pour le mondial de clustering coefficient, qui Newman affirme serait pas représentatif.

    Cependant, de nombreuses études de réseaux (ou, dans mon expérience, au moins de nombreuses études de réseaux sociaux en ligne) semblent avoir utilisé cette méthode, afin d'être en mesure de comparer vos résultats avec les leurs, vous auriez besoin d'utiliser la même méthode. En outre, la critique soulevée par Newman n'a pas d'incidence sur la mesure dans laquelle les comparaisons mondiales de clustering coefficients peuvent être faites, à condition que la même méthode a été utilisée pour la mesure.

    Les deux formules sont différentes et ont été proposées à différents moments dans le temps. Celui que vous avez cité de Watts et Strogatz est plus, ce qui est peut-être pourquoi il semble avoir été plus couramment utilisés. Newman explique également que les deux formules sont loin d'équivalent, et ne devrait pas être utilisé comme tel. Il dit qu'ils peuvent donner sensiblement différents numéros pour un réseau donné, cependant, n'explique pas pourquoi.

    [1] C_i = (nombre de paires de voisins de je qui sont connectés) /(nombre de paires de voisins de je)

    [2] Newman, M. E. J.. Réseaux : une introduction. Oxford, New York: Oxford University Press, 2010. D'impression.

    Edit:

    Je joins ici une série de calculs pour la même ER aléatoire graphique. Vous pouvez voir comment les deux méthodes donnent des résultats différents, même pour les graphes non dirigés. (fait à l'aide de Mathematica)

    La Théorie Des Graphes: Le Calcul De Coefficient De Clustering

    Et ceci est soutenu par le présent document: i11www.iti.uni-karlsruhe.de/_media/projects/spp1126/files/... (voir les sections I & II-A)

    OriginalL'auteur WindChimes

  3. 2

    Je suis partiellement en désaccord avec Whatang. Ces méthodes ne sont que l'équivalent pour les graphes non dirigés. Toutefois, pour les graphes orientés, ils retournent des résultats différents. À mon avis, le local de clustering coefficient méthode est la bonne. Sans parler de son moins gourmand en ressources. Par exemple

      <-----
4 -----> 5
|<--||-->
|   ||
|-> 6  -> 7

4(IN [5,6], OUT [5,6])
5(IN [4,6], OUT [4])
6(IN [4], OUT [4,5,7])
7(IN [6], OUT [])

    centrale = 6

    localCC = 2 /4*3 = 1/6

    globalCC = 1 /3

    OriginalL'auteur alien01

  4. 0

    Je n'aurais pas confiance en l'article de wikipédia. La première formule que vous avez cité est actuellement définie comme la Moyenne de Clustering Coefficient, c'est donc la moyenne de l'ensemble des coefficients de clustering de graphes g. Ce n'est en aucune façon le même que le mondial de clustering coefficient, comme xk_id avec justesse.

    OriginalL'auteur Workhorse

  5. 0

    il y a une grande page pour apprendre les bases de!

    http://www.learner.org/courses/mathilluminated/interactives/network/

    tout à propos de cluster coefficients, le monde est petit et ainsi de suite ...

    OriginalL'auteur Peter Piper