We analyze the strength of ties through three different clustering algorithms applied to co-authorship social networks from three different research areas. This study reveals if tie strength metrics can be used to evaluate clusters quality. We obtain different results for each algorithm and observe that Markov cluster algorithm provides the best results for co-authorship social networks. Also, researchers in overlapped communities detected by clique percolation method work as bridges.
Clustering algorithms represent a classical problem of data mining and has many
applications over a plethora of domains. Then, identifying which algorithm is
proper to one such domain is a challenge per se. Likewise, evaluating the
quality of the created clusters is hard due to its problem-driven nature, as a good
clustering algorithm for a problem may not be as good for another [
In the context of social networks (SN), clustering algorithms are useful for
detecting (finding) communities. Examples of studies include to explore regional
innovation systems, clustering effect in scientific communities and concentration
of developers in a country [
Here, we apply clustering techniques in co-authorship SN, a type of academic
SN in which the nodes are researchers and there are edges between those who
have published together. By definition, a cluster in SN is a collection of
individuals with dense interactions patterns internally and sparse interactions externally
[
In summary, when the strength of ties is measured by metrics that consider
the neighborhood of nodes, the strength of ties intra cluster should be higher than
inter clusters. Hence, we measure tie strength using two metrics that provide such
information [
Brief Related Work. There are many clustering techniques and they are
applied to different types of networks, for example, similarity graphs [
Also, there are different ways to measure clustering quality, such as BetaCV,
C-index and modularity [
Contributions. Overall, our contributions are the analyses of: the distribution of strong and weak ties intra and inter clusters and the dynamism of the strength of ties through different clustering algorithms. Such analyses reveal whether tie strength metrics can be used to evaluate clusters quality based on the definition that ties intra a community should be strong and inter should be weak.
Next, we present the analysis setup that includes creating reals SNs (Section
2). Then, we analyze three clustering methods: Louvain method (Section 3.1),
clique percolation method (Section 3.2) and Markov cluster algorithm (Section
3.3), and compare their results (Section 4). We have chosen such algorithms
because they are important to detect core groups (a.k.a. clusters or
communities) on SN [
A co-authorship social network can be modeled as a weighted graph Gw =
(V; E w), with V the set of nodes and E w the set of non-directed weighted links.
Nodes are researchers (or authors), a tie between any two researchers exists if
they have published together, and the tie weight represents the absolute number
of publications between them, called as co-authorship frequency or simply W ,
which has been applied to measure the strength of ties [
Another topological property to measure the strength of ties is Neighborhood
Overlap – N O [
Here, we build three co-authorship SNs using the CiênciaBrasil datasets1. The publications available in CiênciaBrasil are from Brazilian researchers and have been collected from Lattes, an online platform for archiving researchers’ curriculum vitae, in November 2013. Each network represents the co-authorships among researchers from three areas: computer science, medicine and sociology. Table 1 has the datasets statistics: number of authors (researchers), number of
publications, average number of publications per author and number of pairs of co-authors (and number of distinct pairs of co-authors).
Considering these datasets, we apply three clustering algorithms: Louvain
method (LM), clique percolation method (CPM) and Markov cluster algorithm
(MCL). Then, we measure the strength of ties for each pair of researchers in
each cluster detected by the algorithms. Such strength is measured by using N O
and W . Following Brandão and Moro [
Overall, analyses provide insights whether the strength of ties metrics can
be used to evaluate clustering quality. By clusters definition [
One of the problems in evaluating clustering quality is the absence of a ground
truth for comparison [
Note the minimum value of N O is 0.2, i.e., most communities are composed
by strong ties. The smallest clusters have N O equal to 1 (i.e., all ties are strongly
connected), because all nodes are connected to each other, but in a real social
network this hardly happens. We emphasize that a high N O indicates that pairs
of researchers are more connected to each other intra a cluster. Also, W of all
clusters has the median higher than 20. This is a property strictly related to the
frequency of nodes interactions – not always found in real networks. However,
co-authorship SN with a high degree of collaboration tend to have a high W [
In this section, considering three real co-authorship networks, we analyze three
clustering techniques: Louvain method (Section 3.1), Clique Percolation method
(Section 3.2) and Markov Cluster algorithm (Section 3.3). For space constraint,
all graphs are presented in [
The Louvain method (LM) [
Considering only computer science (CS), Figure 2 presents the results for measuring intra and inter-communities created by LM using both N O and W . Overall, medicine has more communities with smaller mean and median N O values than computer science, but W of such communities are higher than computer science. Also, in both areas, the communities with highest N O do not indicate communities with highest W . In sociology, N O and W of researchers in each community is small, but communities with the highest N O do not have the highest W . Such aspects suggest that the strength of the intensity of coauthorships among researchers measured by W does not always correspond to the strength of the interactions among researchers’ neighbors measured by N O. Moreover, there are communities with N O equal to zero, few edges compose all such communities in the three SN, and all edges have one node in common. These smaller communities are detected by LM because the researchers are not (a) CS: LM Intra-community with N O (b) CS: LM Intra-community with W (c) CS: LM Inter-community with N O (d) CS: LM Inter-community with W densely connected to other communities. Also, considering the outliers, the communities have less outliers to N O than to W . For future work, the study of such outliers might reveal interesting properties about co-authorships. 3.2
The clique percolation method (CPM) locates the k-clique communities of
networks and considers that a typical node in a community is linked to many others,
but not necessarily to all other nodes in the community [
We apply this method using the algorithm implemented in CFinder2 and k=3. By definition, a community is actually a connected graph when k=2 and
(a) Med: CPM Intra-community with N O (b) Med: CPM Intra-community with W
a set of disconnected nodes without any edge when k=1. The parameter k
determines the nature of the communities. Using different values for k reveals the
nature of the communities [
Figure 3a show the communities uncovered by the CPM (k=3) applied to the medicine SN. Note that it considers the social network as unweighted. The N O values reveal that although the communities are formed by cliques, some of them have only weak ties (i.e., pairs of researchers weakly connected regarding N O): seven in medicine, ten in computer science, and two in sociology. In other words, cliques formed by co-authorship of researchers do not have only strong interactions. Additionally, each community may have ties linking different cliques, and such ties are also weak in communities with only weak ties. Other communities have only strong ties: eight in medicine, four in computer science, and two in sociology. It is also interesting to investigate these communities in order to identify patterns in the high cooperativeness. In the remaining communities, there is a mix of strong and weak ties. Furthermore, most communities have the median and mean different from the others, meaning that researchers have distinct behavior of co-authorship in each community.
Regarding W as a measure of the strength of tie, Figure 3b shows that most communities are composed by ties between researchers with small W . In medicine and computer science, only one community has tie with W greater than 10. In sociology, W does not reach five. Although the cliques compose such communities, the high connectivity among researchers groups does not indicate a strong intensity of co-authorship.
According to CPM definition, one researcher may be in more than one
community. The number of overlaps is small in the three networks: in computer
science, only one researcher is in four communities; in sociology, there is no
overlap; and in medicine, one researcher is in three communities. An analysis
(a) CS: MCL Intra-communitity with NO (b) Soc: MCL Intra-communitity with NO
(c) CS: MCL Intra-communitity with W
(d) Soc: MCL Intra-communitity with W
Fig. 4: MCL intra-communities with N O and W for computer science (CS),
sociology (soc) – clusters’ identifiers in x axis are ordered by the size of communities.
suggests that researchers in overlapped communities have weak ties with other
researchers and work as a bridge (details available in [
The Markov Cluster Algorithm (MCL) is an unsupervised clustering algorithm
for graphs based on simulation of stochastic flow in graphs (known as network)
[
One input to MCL is a file describing the graph edges: the source and target nodes, and W as edges weight. The MCL interprets W of the edges as similarity to cluster the nodes. In order to understand how N O and W influence on clustering formation, we run the algorithm twice changing the value of the edge weight (one time weights equal to N O and another to W ). Using N O, the MCL
has found 140 clusters in computer science, 35 in sociology and 139 in medicine. Then, using W , the MCL has detected 82 clusters in computer science, 16 in sociology and 68 in medicine. Some clusters are composed of only one node, and they are more present in clusters formed with N O as edge weight. This result indicates that the similarity among researchers is lower considering N O than W .
Figure 4 shows the results ordered by the size of communities when N O and W between researchers are considered as edge weight. The graphs do not include clusters with only one node for clarity. There are communities formed only by weak ties and only by strong ties, for example, the communities #25 and #34 in computer science, respectively. However, most communities include both types of tie. Considering the clusters size, the biggest communities are in the beginning of each graphic. For example, clusters #0 and #1 are the largest in sociology. The number of nodes in the largest clusters for N O and W as edges weight is respectively 30 and 27 for computer science, four nodes (two communities of the same size) and four nodes (four communities of the same size) for sociology, 22 and 17 for medicine. Figure 4 also presents that the largest clusters are more formed by strong ties than weak ties, because the first quartile of these clusters is higher or equal to 0.2. Then, the largest communities have high W , because the third quartile pass 30 in the three areas.
Lastly, MCL does not find ties connecting researchers from different
communities for the three co-authorships SN. This reveals that MCL provides a good
clustering result since clustering algoritms minimizes inter-cluster edges [
We now compare the results of the three clustering methods. Figures 5 and 6 contrast the clusters of each method regarding N O and W , respectively. We observe that LM tends to find less and larger clusters than the other two methods. Also, MCL detects a huge number of clusters, and some of them are singleton. In the co-authorship context, although CPM allows community overlaps, as a researcher may publish with researchers from others communities, MCL provides the best clusters because most of the detected ones are composed by strong ties.
Moreover, Figure 5 shows a high concentration of edges until N O reaches 0.6 in computer science and medicine. In sociology, the maximum value of N O is 0.5, and there is more concentration of edges between 0.2 to 0.3. Also, note that CPM and MCL exclude edges with N O equal to 0. Some strong ties are also removed in CPM, probably because these edges are in a 2-clique (we choose k=3 for CPM). Here, MCL better differentiates the relationships putting them in distinct clusters. On the other hand, the concentration of points in CPM and LM does not show the same for these methods. Additionally, Figure 6 shows a high concentration of edges for W less than 100 in computer science and medicine, and less than 10 in sociology. We also note that co-authorship frequencies equal to zero are not removed in any clustering method. Overall, the three algorithms form clusters with weak and strong ties. However, MCL mostly detects clusters with more strong ties than weak ones. 5
We applied three clustering algorithms in three co-authorship SN. For the unweighted LM, its evaluation results showed it identifies less clusters than the others. When applying CPM, there was a small number of overlaps between communities and researchers in the overlaps are weak ties (they work as bridges). For MCL, we have applied it twice in each algorithm: one with N O as weight and another with W . MCL identified a larger number of clusters than the other methods. Furthermore, the tie strength inter-communities tends to be weak for LM and CPM; whereas MCL algorithm does not find edges inter-communities.
A main conclusion of using N O and W in clustering evaluation is: MCL is the best clustering algorithm to be applied in co-authorship SN when compared to LM and CPM. Nevertheless, we also conclude that considering only the strength of ties metrics is not enough to define clustering qualities. Therefore, in the next steps, we plan to apply internal measures (like BetaCV, C-index, and so on) to compare with the results generated by the tie strength metrics. Also, we plan to investigate how the network structure affects the clustering results. Acknowledgments. Work funded by CAPES, CNPq and FAPEMIG, Brazil.