[PYTHON] Evaluation of cluster coefficient of VTuber channel

Samari

--A brief summary of cluster coefficients, which is one of the network analysis methods --I tried to apply the cluster coefficient to the network where the edge was drawn by the common ratio of the viewers created last time. --Result --Calculate the cluster coefficient of Nijisanji and hololive by Zhang's method --The top 5 channels with cluster coefficients in each office are as follows.

Cluster coefficient

What is the cluster coefficient?

How cluster-centric are the nodes in the network in the network? Is one of the quantitative expressions of. As you can see from the definition, if it is a cluster, there is a desire that the surrounding area be a creek. .. .. The definition of the cluster coefficient differs depending on whether the weight of the edge of the graph is taken into consideration or not. In addition, all the definitions introduced below are definitions in undirected graphs.

For undirected graphs without weights

Definition

The cluster factor $ C_i $ for node $ i $ is defined below. However, if the number of adjacent nodes is 1 or less, it is set to 0.

\displaystyle{
\begin{aligned}
C_i &:= \frac{\sum_{j, k \in \Pi(i), j\neq k} a_{ij}a_{jk}a_{ki}}{k_i (k_i - 1)}\\
k_i &:= \sum_{j\in \Pi(i)} a_{ij}\\
a_{ij} &:Adjacency matrix\ A\of\ (i, j)\component\\
\Pi(i) &:node\ i\A set of nodes adjacent to
\end{aligned}
}

Since we are dealing with an undirected graph without weights, the components of the adjacency matrix have only $ 1 $ or $ 0 $ as values.

As for feelings, the more cluster-centric --The self and the two nodes connected to it are more closely connected --In many cases, you and the two nodes connected to you become a 3-creek (in other words).

Concrete example

Abbreviation

It will come out soon if you go around

For weighted undirected graphs

There seem to be various definitions of cluster coefficients in the case of weighted undirected graphs. Here are some of them. A weighted adjacency matrix is represented by $ W , and an adjacency matrix with only connection information ( 1 $ or $ 0 $) is represented by $ A $. Also, let $ s_i: = \ sum_ {j \ in \ Pi (i)} w_ {ij} $.

Note that if the weight matrix component is 0 or 1 (that is, an unweighted adjacency matrix), they match the cluster coefficients with no weights (see the reference link because the calculation is crappy).

reference

• http://downloads.hindawi.com/journals/ddns/2008/375452.pdf
• https://pdfs.semanticscholar.org/acb2/3e3c2264dbc900bac278c5b4477737741027.pdf

Definition

Zhang

\displaystyle{
\begin{aligned}
C_{i}^Z := \frac{\sum_{j, k \in \Pi(i), j\neq k} w_{ij}w_{jk}w_{ki}}{\left((\sum_{j\in\Pi(i)} w_{ij})^2 - \sum_{j\in\Pi(i)} w_{ij}^2\right) \max(w_{jk})}
\end{aligned}
}

--A simple extension of the cluster coefficient, where the numerator simply replaces $ a $ in the cluster coefficient with $ w $ and has a similar format if the denominator is also rearranged. -Useful when you want to consider all the weights of $ ij, jk, ki $ --The weight matrix $ w $ is normalized by $ \ max (w_ {jk}) $

Lopez-Fernandez

\displaystyle{
\begin{aligned}
C_{i}^L := \frac{\sum_{j, k \in \Pi(i), j\neq k} w_{jk}}{k_i (k_i-1)}
\end{aligned}
}

--Useful when you want to focus only on the weight between adjacent nodes $ j, k $ -I don't care about the weights of $ ij and ik $ --The weight matrix is not standardized

Onnela

\displaystyle{
\begin{aligned}
C_{i}^O := \frac{\sum_{j, k \in \Pi(i), j\neq k} (w_{ij}w_{jk}w_{ki})^{1/3}}{k_i (k_i-1) \max(w_{jk})}
\end{aligned}
}

-Useful when you want to consider all the weights of $ ij, jk, ki $ ――Because it is 1/3 powered, the effect of individual weights is weaker than that of Zhang. --The weight matrix is normalized by $ \ max (w_ {jk}) $ --This is implemented by the clustering method of NetworkX, one of the python libraries.

Barrat

\displaystyle{
\begin{aligned}
C_{i}^B := \frac{\sum_{j, k \in \Pi(i), j\neq k} (w_{ij} + w_{ki})a_{jk}}{2s_i (k_i-1)}
\end{aligned}
}

--The weights are not products, but sums. -Does not consider weights between $ jk $ --Lopez-The opposite of Fernandez. Useful when you want to consider the connection strength of $ ij, ik $ --The weight is standardized by $ \ max (s_i) $

Serrano

\displaystyle{
\begin{aligned}
C_{i}^S &:= \frac{\sum_{j, k \in \Pi(i), j\neq k} w_{ij}a_{jk}w_{ki}}{s_i^2 (1-Y_i)}\\
Y_i &:= \sum_{j\in\Pi(i)} \left(\frac{w_{ij}}{s_i}\right)^2
\end{aligned}
}

-Does not consider weights between $ jk $ --Barrat and Nori are the same --The weight is standardized by $ \ max (s_i) $

Application to VTuber network

As a motivation, I would like to find out whether the core distributor can be found with these indicators, and whether these indicators work in the network defined last time.

Last defined network

The edges between each channel are weighted by a common percentage of the set of commented viewers.

\displaystyle{
\begin{aligned}
w_{ij} &:= \frac{|U_i \cap U_j|}{U_i \cup U_j|}\\
U_i &:A set of users who commented on channel i
\end{aligned}
}

Network features

--Almost fully connected (users almost never suffer) ――The strength of the bond is basically strong inside the same office and weak outside the office. --However, except for those who have a strong relationship with another office, such as Tamaki Inuyama and Shigure Ui. ――In a large office, the fluctuation of weight is small in the same office

Data used, conditions, etc. --Data: Comments obtained from YouTube archive broadcast --Period: 2020/1/1 ~ 2020/6/30

The whole network looks like this (I added a few channels from the last time). The line thickness corresponds to the high percentage of viewers in common.

Calculation of cluster coefficient

Here, the calculation is performed for the network of Nijisanji only and the network of hololive only. The reason for not calculating the cluster coefficient that mixes multiple offices is that the number of nodes in the cluster is imbalanced. For nodes in a large cluster, a calculation result with a large cluster coefficient can be obtained. I don't know (currently I) how to calculate the appropriate cluster coefficient for a network between clusters with an imbalanced number of nodes, so I will narrow down the calculation once.

For each network, calculate the cluster coefficient and list the top 5, bottom 5, and percentiles. Also, the code used will be posted at the end of the article.

Adaptation to Nijisanji

The graph of Nijisanji looks like this. The number of nodes and the number of edges are both large, and the graph is not clear. .. ..

Zhang

Lopez-Fernandez

Onnela

Barrat

Serrano

Adaptation to hololive

The hololive network is below. It is easy to see because it has fewer nodes than Nijisanji. .. .. The cluster coefficients of Barrat and Serrano are omitted here because all cluster coefficients are 1 for the same reason. The reason will be described later.

Zhang

Lopez-Fernandez

Onnela

Impressions

--Lower (higher in Lopez-Fernandez) broadcasts less frequently, has not been broadcast for a long time, and has many channels with few live broadcasts in the first place When the broadcast period is free, the viewer suffers less. obvious.

――The upper (lower) differs greatly depending on the method For Lopez_Fernandez, it depends only on the weight $ w_ {jk} $ of the nodes $ j, k $ adjacent to the node $ i $. Therefore, in the case of a fully connected network, the one with the smaller weight of $ w_ {ij}, w_ {ik} $ comes to the top of the cluster coefficient. Looking at hololive, for example, Mr. Yozora Mel was ranked high because he had a long pause, and the official channel was ranked high because the number of live broadcasts was small in the first place. Is it considered that the other high-ranking channels (Choco-san, Tokino Sora-san, etc.) have weak cluster formation with other nodes?

--Lopez_Fernandez and Onnela have similar top (and bottom) and bottom (and top) The main difference between Zhang and Onnela is whether the third-order term of the weight is 1/3 power. When multiplied by 1/3, the fluctuation of weight becomes smaller. Calculations show that the first-order contributions of fluctuations are the same, but the second-order contributions are kept small (in Zhang ratio) by the contributions from the 1 / 3rd power.

--Barrat and Serrano cluster coefficients are all 1 In the case of a fully connected network, all cluster coefficients are 1 by definition. obvious.

――What kind of cluster coefficient is good? Since this network is a weighted fully connected network, Lopez_Fernandez will calculate a large cluster coefficient even if a node is isolated (in the sense that the weight is light). So is Lopez_Fernandez suitable? There is a big difference between Zhang and Onnela with or without 1/3 power. Since the weight is leveled by the presence of 1/3, it is only necessary to select how sensitive the fluctuation of the edge weight should be. This time, it is a fully connected network and the fluctuation of weight is small, so I want you to be sensitive to the small fluctuation. So Zhang's model looks good?

――Which is cluster-centric after all? With Zhang down, the top 5 channels with cluster coefficients in Nijisanji and hololive are: As for hololive, it's intuitive, but I'm still ignorant of Nijisanji, so I'm not sure if this result is intuitive. .. .. Please let me know. .. ..

(Fucking) code

like this

class clustering_coefficient:
    def __init__(self, df):
        self.df = df.copy()
        self.names = list(self.df.columns)
        for c in self.names: self.df.loc[c, c] = 0
        self.ki = {name: (self.df.loc[self.df.index[self.df.index != name], :][name] > 0).sum() for name in self.names}
        self.si = {name: self.df.loc[self.df.index[self.df.index != name], :][name].sum() for name in self.names}
        self.max_w = self.df.values.ravel().max()

    def Zhang(self):
        return {name: sum([(self.df.loc[n1, n2] * self.df.loc[n1, name] * self.df.loc[name, n2]) \
            for n1, n2 in itertools.permutations(self.names, 2)])\
            / sum([(self.df.loc[n1, name] * self.df.loc[name, n2]) \
            for n1, n2 in itertools.permutations(self.names, 2)]) / self.max_w\
            for name in self.names}

    def Lopez_Fernandez(self):
        return {name: sum([(self.df.loc[n1, n2] * (self.df.loc[n1, name] > 0) * (self.df.loc[name, n2] > 0)) \
            for n1, n2 in itertools.permutations(self.names, 2)]) / (self.ki[name]* (self.ki[name] - 1)) for name in self.names}

    def Onnela(self):
        return {name: sum([(self.df.loc[n1, n2] * self.df.loc[n1, name] * self.df.loc[name, n2]) ** (1/3.)\
                for n1, n2 in itertools.permutations(self.names, 2)]) \
                / (self.ki[name]* (self.ki[name] - 1) * self.max_w) for name in self.names}

    def Barrat(self):
        return {name: sum([(self.df.loc[n1, name] + self.df.loc[name, n2]) * (self.df.loc[name, n1] > 0) * \
                (self.df.loc[name, n2] > 0) * (self.df.loc[n1, n2] > 0)for n1, n2 in itertools.permutations(self.names, 2)]) \
         / ((self.ki[name] - 1)* self.si[name] * 2) for name in self.names}

    def Serrano(self):
        return {name: sum([((self.df.loc[n1, n2] > 0) * self.df.loc[n1, name] * self.df.loc[name, n2]) \
                for n1, n2 in itertools.permutations(self.names, 2)]) \
                / (self.si[name] ** 2 * (1 - ((self.df[name] / self.si[name]) ** 2).sum()))\
                for name in self.names}