# SCOREH+: A High-Order Node Proximity Spectral Clustering on Ratios-of-
Eigenvectors Algorithm for Community Detection

Yanhui Zhu<EMAIL_ADDRESS>
Department of Mathematics and Statistics
University of West Florida
Pensacola, FL 32514, USA
Department of Computer Science
Iowa State University
Ames, IA 50011, USA Fang Hu<EMAIL_ADDRESS>
Department of Mathematics and Statistics
University of West Florida
Pensacola, FL 32514, USA
College of Information Engineering
Hubei University of Chinese Medicine
Wuhan 430065, P.R. China. Lei Hsin Kuo<EMAIL_ADDRESS>
Department of Mathematics and Statistics
University of West Florida
Pensacola, FL 32514, USA Jia Liu<EMAIL_ADDRESS>
Department of Mathematics and Statistics
University of West Florida
Pensacola, FL 32514, USA

###### Abstract

The research on complex networks has achieved significant progress in
revealing the mesoscopic features of networks. Community detection is an
important aspect of understanding real-world complex systems. We present in
this paper a High-order node proximity Spectral Clustering on Ratios-of-
Eigenvectors (SCOREH+) algorithm for locating communities in complex networks.
The algorithm improves SCORE and SCORE+ and preserves high-order transitivity
information of the network affinity matrix. We optimize the high-order
proximity matrix from the initial affinity matrix using the Radial Basis
Functions (RBFs) and Katz index. In addition to the optimization of the
Laplacian matrix, we implement a procedure that joins an additional
eigenvector (the $(k+1)^{th}$ leading eigenvector) to the spectrum domain for
clustering if the network is considered to be a ”weak signal” graph. The
algorithm has been successfully applied to both real-world and synthetic data
sets. The proposed algorithm is compared with state-of-art algorithms, such as
ASE, Louvain, Fast-Greedy, Spectral Clustering (SC), SCORE, and SCORE+. To
demonstrate the high efficacy of the proposed method, we conducted comparison
experiments on eleven real-world networks and a number of synthetic networks
with noise. The experimental results in most of these networks demonstrate
that SCOREH+ outperforms the baseline methods. Moreover, by tuning the RBFs
and their shaping parameters, we may generate state-of-the-art community
structures on all real-world networks and even on noisy synthetic networks.

Keywords: Community Detection, Spectral Clustering, Radial Basis Functions,
High-Order Proximity, Graph Decomposition

##  1 Introduction

Complex networks model many entities and their relations as nodes and edges in
real-world scenarios, which are ubiquitous and can be applied to any data as
long as pair-wise interactions exist among the objects. Non-trivial
topological features preserved in the network structure have attracted
researchers from various fields, for example, biology (Guerrero et al., 2017;
Berahmand et al., 2021), climate (Boers et al., 2019), epidemiology (Rentería-
Ramos et al., 2018; Kinsley et al., 2020), etc. In complex networks, community
detection discovers clusters in the network model to mine latent information
among the objects. The nodes are densely connected by edges within clusters
while sparsely connected between clusters. Researchers have developed various
algorithms to discover community structures, for example, Walktrap (Pons and
Latapy, 2005), Infomap (Rosvall and Bergstrom, 2007), Louvain algorithm
(Blondel et al., 2008), deep learning-based algorithms (Yang et al., 2016; Jin
et al., 2021), spectral-based methods (Ng et al., 2002; Jin, 2015; Hu et al.,
2019), diffusion-based algorithms (Roghani and Bouyer, 2022), algorithms on
overlapping networks (Kumar et al., 2017; Gupta and Kumar, 2020), to name a
few. On the other hand, hiding nodes from community algorithms for privacy
purposes (Liu et al., 2022), and vulnerability assessment (Li et al., 2021)
have also become hot spots.

Spectral clustering, rooted in graph theory, is one of the state-of-the-art
algorithms for detecting communities in complex networks. A spectral
clustering algorithm consists of three procedures: (1) regularization of a
suitable adjacency or Laplacian matrix; (2) a form of spectral truncation; and
(3) a k-means algorithm on the reduced spectral domain (Zhou and Amini, 2019).
For the first step, the formation and selection of the graph proximity method
and Laplacian are significant. A similarity matrix models the local
neighborhood relationships of pair-wise data points. Researchers typically use
the network affinity matrix as the node similarity representation or implement
the similarity measures to construct a new similarity matrix. Radial Basis
Functions (RBFs) are commonly used kernels in constructing those similarity
matrices (Law et al., 2017; Park and Zhao, 2018). In the third step, the
number of clusters is a prerequisite. Nonetheless, by decomposing the
Laplacian matrix, the first large gap between two eigenvalues generally
indicates the number of clusters. That is to say, the number of eigenvalues
before this gap is the number of clusters (Polito and Perona, 2002). However,
this approach lacks a theoretical justification (Zelnik-manor and Perona,
2004).

The challenges and drawbacks of existing spectral-based and community
detection are presented as follows:

  * •

The affinity matrix is insufficient to capture graph local information. It
only captures the direct neighbors’ information between nodes, while the
higher-order motif information is natural and essential for forming a
community (Shang et al., 2022).

  * •

Given the number of clusters $k$, researchers generally preserve the exact top
$k$ eigenvectors for posting k-means clustering. However, for some networks,
other eigenvectors may also carry information for clustering (Jin et al.,
2018). Thus, an eigen-selection strategy is essential.

  * •

Most graph affinity matrices are large, sparse matrices with huge condition
numbers (can be approximated by the ratio of the largest and smallest
eigenvalues or singular values). If the linear system is ill-conditioned with
huge condition numbers, we may have a large error in the numerical results
from the eigenvalue and eigenvector methods. Therefore, optimization of the
affinity matrix is a necessary step.

This paper proposes an improved community detection algorithm to address those
challenges. First, it utilizes RBFs to approximate the similarity matrix from
the original affinity matrix and considers its high-order proximity. The
optimization of the RBFs helps reduce the condition number of the original
affinity matrix. The resulting linear system will be less ill-conditioned so
that the performance of the eigenvalue decomposition will be stable and
robust. We select the Katz index to obtain the high-order proximity on the
resulting matrix from the RBF transformation. The Katz index is easy to
implement and has a relatively lower time complexity than other methods, such
as Common neighbors, Propagation, and Eigenvector Centrality. We analyze the
eigenvalue distribution and determine if one more eigenvector is necessary.
Moreover, given the substantial impact of an appropriate RBF shaping parameter
(Noorizadegan et al., 2022), we conduct a comprehensive analysis encompassing
a range of optimal RBFs and their shaping parameters.

We tested the proposed algorithm and demonstrated its effectiveness on eleven
real-world networks spanning various areas. In addition, we generated
benchmark networks using a criterion presented by Lancichinetti, Fortunato,
and Radicchi (Lancichinetti et al., 2008), in short, the LFR benchmark. Taking
advantage of these data sets, we analyzed the multi-view results concerning
the number of clusters and mixing parameters.

Overall, our paper makes the following contributions:

  * •

Well-conditioned network data. We apply the RBF transformation to the affinity
matrix of the network data. This procedure can reduce the condition number of
the similarity matrix from the network affinity, resulting in a well-
conditioned matrix, which is important for data clustering.

  * •

High-order proximity. Compared to the local direct relationship between nodes,
high-order information is essential for preserving the network. We utilize the
Katz index to compute the high-order proximity of nodes, allowing us to
preserve more node-local information for more accurate clustering purposes.

  * •

RBF shaping parameter optimization process. We analyze the selection of RBFs
and their shaping parameters. Extensive experiments show that some RBFs have
an “optimal” shaping parameter domain where near-optimal results can be
obtained.

The remainder of this paper is organized as follows: In Section 2, an overview
of related work is presented, encompassing topics such as spectral clustering,
SCORE/SCORE+ algorithms, high-order proximities, and Radial Basis Function
(RBF) applications. Section 3 offers an in-depth exploration of our algorithm,
delving into its design, stepwise execution, pseudocodes and complementing
these with a comprehensive flowchart illustration. Moving forward, Section 4
outlines our experimental setup, dataset selection, evaluation metrics,
baseline algorithms, and more. Section 5 is dedicated to the presentation of
our experimental outcomes, followed by their thorough analyses. Finally, we
draw our paper to a close with a concise summary of our findings and a glimpse
into future research prospects, detailed in Section 6.

##  2 Related Work

In this section, we present the related work concerned with the community
detection algorithms, SCORE, and SCORE+ algorithms, higher-order proximities,
and RBF applications.

###  2.1 Community Detection Algorithms

Community detection models are basic tools that enable us to discover the
organizational principles in the network. In the last two decades, researchers
have developed various efficient and effective models, for example, the famous
Louvain algorithm (Blondel et al., 2008), and the fast greedy algorithm
(Clauset et al., 2004), to name a few. The abovementioned algorithm can only
solve simple static networks; however, in real applications, network data is
changing and evolving (Zhang et al., 2019). Therefore, Li et al. introduced a
novel dynamic fuzzy community detection method (Li et al., 2022a) and a new
highly efficient belief dynamics model (Li et al., 2022b).

Spectral Methods. Spectral clustering is one of the common community detection
algorithms. It uses information from the eigenvalues of the Laplacian of an
affinity matrix and maps the nodes to a low-dimensional space where data is
more separable, enabling us to perform eigen-decomposition and form clusters
(Ng et al., 2002). Spectral clustering has wide applications in other
datasets, such as attributed network (Berahmand et al., 2021), multi-layer
network (Dabbaghjamanesh et al., 2019), multi-view network (Huang et al.,
2019), etc. In particular, if one considers the network’s topology structures
as well as node attribute information, the algorithm should apply to
attributed networks. Berahmand et al. proposed a spectral method for
attributed graphs showing that the identified communities have structural
cohesiveness and attribute homogeneity (Berahmand et al., 2022). To reveal the
underlying mechanism of biological processes, a novel spectral-based algorithm
was proposed for attributed protein-protein interaction networks (Berahmand et
al., 2021).

SCORE and its Variants. Jin et al.(Jin, 2015) first proposed the SCORE
algorithm, which uses the entry-wise ratios between eigenvectors for
clustering to improve the effectiveness of spectral clustering. SCORE
effectively removes the effect of degree heterogeneity by taking entry-wise
ratios between the first leading eigenvector and each of the other
eigenvectors. The SCORE provides novel ideas about computing communities in
networks and can be extended in various directions.

Jin et al. (Jin et al., 2018) applied two normalizations and eigen selections
to improve SCORE’s performance. The new algorithm SCORE+ demonstrated the
rationality of Laplacian regularization as a pre-PCA normalization and
retained an additional eigenvector as a post-PCA normalization. SCORE+ has two
tuning parameters, but each is easy to set and not sensitive. Therefore, SCORE
is fast, and SCORE+ is slightly slower. Their experimental results showed that
the clustering error rate was reduced dramatically compared to SCORE on
testing networks. Researchers have borrowed ideas from SCORE and SCORE+ for
the community detection field (Gao et al., 2018; Duan et al., 2019).

###  2.2 Higher-Order Proximities

In networks, to measure the similarity of every pair of nodes, the adjacency
matrix and Laplacian matrix represent the first-order proximity, which
simulates the local pair-wise proximity between vertices. Cosine similarity,
Euclidean similarity, and Jaccard similarity are also popularly used. However,
these similar methods can only preserve local information by using its
connectivity to its neighbors. They are not sufficient to fully simulate the
pair-wise proximity between nodes. How to preserve high-order proximity,
therefore, has become a hot topic recently. People have also explored higher-
order similarities to simulate the strength between two nodes (Cao et al.,
2015; Tang et al., 2015).

Three commonly used high-order proximities are Common Neighbors and
Propagation (Liben-Nowell and Kleinberg, 2007), Katz Proximity (Katz, 1953),
and Eigenvector Centrality (Bonacich, 2007). The Katz index was proposed by
Katz (Katz, 1953) to compute the similarity of two nodes in a heterogeneous
network by computing the walks between two nodes. We selected the Katz index
in our paper for two reasons. First, it has been popularly used in related
areas, for example, graph embedding (Ou et al., 2016) (Zhang et al., 2018),
complex networks (Lü et al., 2009), and relationship prediction in networks
(Chen, 2015; Zhang et al., 2017). Second, compared to Common Neighbors and
Propagation (Liben-Nowell and Kleinberg, 2007) and Eigenvector Centrality
(Bonacich, 2007), the Katz index has lower complexity in implementation since
Eigenvector Centrality (Bonacich, 2007) requires the eigenvector computations,
which is known to be time-consuming. Ou et al. (Ou et al., 2016) proposed
applying multiple high-order proximity measurements, e.g., Katz index (Katz,
1953) on the graph embedding task. This work has attracted much attention.
Plenty of proximity measurements have emerged in the last century. The Katz
index is a widely used measurement considering the total number of walks
between two nodes rather than the shortest one.

###  2.3 RBF applications

The Gaussian similarity function $\exp(-r^{2}/(2c^{2}))$ is one of the most
common Radial Basis Functions (RBFs) or similarity functions in the neural
networks, where $r$ is the distance between the two nodes and $c$ is the
shaping parameter. This function is equivalent to the Gaussian RBF in Table 2.
The Multiquadric (MQ) RBF is effective in geographical data sets, and the
density of the local dataset determines the shaping parameter $c$. The
selection of RBFs used for the interpolation matrix is strongly problem-
dependent. On the other hand, the interpolation matrix, the same weight matrix
we use in the complex network, is highly ill-conditioned. Thus, the selection
of RBFs and the parameters are significant. Zhang et al. (Zhang and Xu, 2021)
proposed a framework that integrates the attention mechanism and auto-kernel
learning. The hyperparameter tuning for kernels largely facilitated improving
the performance of graph convolutional networks.

In network sciences, researchers consider undirected graphs where the weighted
adjacency matrix $\mathbf{W}=\mathbf{W}^{T}$ is symmetric. The structures of
the networks could be studied by exploring the structures of the matrix
$\mathbf{W}$ (Newman, 2013). The pattern of the vertices and edges of the
adjacency graph or the corresponding adjacency matrix may reveal information
about the network’s divisions, clusters, and communities. The first step is to
transform the given data set into a graph called a “similarity graph”. The
goal of constructing the similarity graph is to model the local neighborhood
relationships from the network data.

A well-condition matrix is important and has better properties (Sharma et al.,
2015). The condition number of a matrix can be approximated by the ratio of
the largest eigenvalue and smallest eigenvalue (in absolute value). Therefore,
to reduce the condition number, we need the absolute eigenvalue to be bounded
away from 0. RBFs are such methods that bound the eigenvalues with at least
$\Omega(\delta/\sqrt{d})$ (Ball, 1992), where $\delta$ is the minimum
separation and $d$ is the dimension of the data.

##  3 The High-order Proximity Preserved Spectral Clustering

In this section, we present a fast community detection algorithm that uses the
ratios of eigenvectors and the Eigen selection strategy while preserving
higher-order proximities in the networks using the RBF and Katz index to
capture more node-local information.

Before introducing the algorithm, we clarify the symbols and definitions used.
Table 1 summarizes the notations used in this paper. The following sections
will formally define these notations when we introduce our network model and
technical details.

Table 1: Important Notations and Naming Conventions

Notation | Description
---|---
$\mathbf{G=\\{V,\ E\\}}$ | Graph with set of nodes and edges
$n,m$ |  number of nodes, number of edges in graph $\mathbf{G}$
(italic math style letter represents a single variable) |
$\Phi(\mathbf{v})$ |  Radial basis function value of node vector $\mathbf{v}$
(bold math style letter represents a vector/matrix) |
$d_{max}$ | maximal node degree in a graph
$\mathbf{A}$ | Graph affinity matrix from $\mathbf{G}$
$\mathbf{D}$ | Degree matrix from $\mathbf{G}$
$\mathbf{W}$ | Weighted matrix
$\mathbf{K}$ | High-proximity Katz matrix
$\mathbf{I}$ | Identity matrix with size $n\times n$
$\beta$ | decay parameter of Katz index
$\sigma$ | ridge regularization parameter
$\mu$ | mixing parameter of LFR network
$c$ | shaping parameter of RBFs
$k$ | number of clusters

###  3.1 The Algorithm

The algorithm constructs the high-order proximity matrix while preserving the
high-order transitivity information from the original affinity matrix using
the RBF technique and Katz index. From the high-order proximity matrix, we
obtain the normalized graph Laplacian. Next, we normalize the $k$ leading
eigenvectors of the proximity matrix by dividing the leading eigenvectors into
an additional $(k+1)^{th}$ eigenvector, which will be used for clustering if
the network is considered to be a “weak signal”.

####  3.1.1 Radial Basis Functions

We begin by outlining the methodology for creating an RBF matrix from the
graph’s original ill-conditioned affinity matrix.

For a given node vector
$\left\\{\mathbf{v}_{i}\right\\}_{i=1}^{n}\in\mathbf{A}$ where $\mathbf{A}$ is
an $n$-dimensional affinity matrix. The approximation that utilizes RBF is an
unknown function $f$, which can be expressed as linear combinations of data
norms.

$f\left(\mathbf{v}\right)\approx\tilde{f}\left(\mathbf{v}\right)=\sum_{i=1}^{n}\alpha_{i}\Phi\left(\left\|\mathbf{v}-\mathbf{v}_{i}\right\|\right),\quad\mathbf{v}\in\Omega$
(1)

where $\left\|\cdot\right\|$ represents the Euclidean norm on
$\mathbb{R}^{d}$, $\alpha_{i}$ is the coefficients, and
$\Phi:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is called a Radial Basis Function
(RBF) (Fasshauer, 2007) if,

$\displaystyle\Phi\left(\mathbf{v}\right)=\Phi\left(\mathbf{u}\right),\quad\text{whenever}\quad\|\mathbf{v}\|=\|\mathbf{u}\|,\quad\mathbf{v},\mathbf{u}\in\mathbb{R}^{d}$
(2)

In Table 2, we list the most common RBFs widely used in neural networks and
the numerical approximations. The symbol $c$ is a shaping parameter, and the
symbol $r$ in the table denotes the Euclidean distance of
$\mathbf{v}\in\mathbb{R}^{d}$ from the original point,
$r=\left\|\mathbf{v}\right\|_{2}=\sqrt{\sum_{i=1}^{d}x_{i}^{2}}$

Table 2: Some common choices of RBFs

Choice of RBF | Definition
---|---
Multiquadric (MQ) | $\Phi(r,c)=\sqrt{c^{2}+r^{2}}$
Inverse Multiquadric (IMQ) | $\Phi(r,c)=1/\sqrt{c^{2}+r^{2}}$
Gaussian | $\Phi(r,c)=\exp\left({r^{2}/c^{2}}\right)$

Follows Equation (1) with the collocation scheme,

$\tilde{f}\left(\mathbf{v}_{i}\right)=f\left(\mathbf{v}_{i}\right),\quad
i=1,2,\cdots,n$ (3)

leads to a system of linear equations,

$\mathbf{W}\bm{\alpha}=\mathbf{f}$ (4)

where $\bm{\alpha}=\left[\alpha_{1},\cdots,\alpha_{n}\right]^{T}$,
$\mathbf{f}=\left[f\left(\mathbf{v}_{1}\right),\cdots,f\left(\mathbf{v}_{n}\right)\right]^{T}$,
and a matrix $\mathbf{W}_{ij}=\Phi\left(r_{ij}\right)\in\mathbb{R}^{n\times
n}$. The distance matrix, $r_{ij}$, contained within $\mathbf{W}$ can be
expressed as follows,

$r_{ij}=\left[\begin{array}[]{ccc}\left\|\mathbf{\\!}{u}_{1}\\!-\\!\mathbf{\\!}{v}_{1}\\!\right\|_{2}&\cdots&\left\|\mathbf{\\!}{u}_{1}\\!-\\!\mathbf{\\!}{v}_{n}\\!\right\|_{2}\\\
\vdots&\ddots&\vdots\\\
\left\|\mathbf{\\!}{u}_{n}\\!-\\!v_{1}\\!\right\|_{2}&\cdots&\left\|\mathbf{\\!}{u}_{n}\\!-\\!\mathbf{\\!}{v}_{n}\\!\right\|_{2}\end{array}\right],\quad
i,j\\!=\\!1,\\!\cdots\\!,n$ (5)

After applying RBF to the data sets, we obtain the similarity graph and the
weighted matrix $\mathbf{W}_{ij}$, with entries
$\mathbf{W}_{ij}=\Phi(\|\mathbf{v}_{i}-\mathbf{v}_{j}\|_{2})$, $i=1,\cdots,n$,
also the interpolation matrix. $\mathbf{W}_{ij}$ consists of the functions
serving as the basis of the approximation space. For distinct data points in
the data sets and a constant shape parameter $c$, $\mathbf{W}_{ij}$ is a
nonsingular matrix. Both the choice of the RBF and its corresponding shaping
parameter play an important role in calculating the final interpolations and
partitions in the resulting graph.

####  3.1.2 Higher-Order Proximities

We compute the high-order similarity matrix with the RBF transformation from
Section 3.1.1 using the Katz index.

The Katz index (Katz, 1953; Ou et al., 2016) computes the relative influence
of a node within a network. We call nodes that are directly connected to a
node as immediate neighbors. Therefore, the Katz index measures the number of
immediate neighbors and the immediate neighbors of its immediate neighbors. It
is a weighted summation of the path node-set between two nodes. The weight of
a path is an exponential function of its length (the number of nodes on this
path). We formularize the Katz high-order proximity matrix $\mathbf{K}$ as:

$\mathbf{K}=(\mathbf{I}-\beta\cdot\mathbf{W})^{-1}\cdot\beta\cdot\mathbf{W}$
(6)

where $\mathbf{W}$ is the weighted matrix acquired from the RBF
transformation, $\beta$ is a decay parameter, which determines the weight of a
path decay speed as the length of the path grows. $\beta$ should be properly
set to preserve the series convergence. In practice, the decay parameter
$\beta$ must be smaller than the spectral radius of the weighted matrix
$\mathbf{W}$. Conventionally, in this paper, we set $\beta$ to $0.0025$.

The pseudocode for computing the high-order proximity of an affinity matrix
using Gaussian RBF is shown in Algorithm 1. This algorithm first generates a
list of $n$ shaping parameters $\mathbf{c}$ (Line 2). Then, iteratively find
an optimal shaping parameter (Line 3-4) where GaussianRBF(·,·) computes the
distance using the Gaussian RBF. We can compute MQ and iMQ RBFs using the
procedures analogous to Algorithm 1 by substituting Line 4 with the respective
RBF distances.

1

Input : Affinity matrix: $\mathbf{A}\in\mathbb{R}^{n\times n}$

Output : High-order matrix: $\mathbf{K}$

2 $\mathbf{x}\leftarrow\textnormal{{linspace}}(0.001,\ 1,\ n)$;

3 $\mathbf{c}\leftarrow\textnormal{{linspace}}(0.001,\ 1,\ 100)$;

4 for  _$i\leftarrow 1\;\textnormal{{to}}\;n$_ do

5
$\mathbf{B}\leftarrow\textnormal{{GaussianRBF}}(\mathbf{c}_{i},\textnormal{{DMatrix}}(\mathbf{x}^{T},\mathbf{x}^{T}))$;

6

7$\mathbf{C}\leftarrow$ optimal $\mathbf{B}$;

8 $\hat{\mathbf{C}}\leftarrow\mathbf{C}\cdot\mathbf{A}$;

9 $\mathbf{K}\leftarrow\textnormal{{Katz}}(\hat{\mathbf{C}})$;

10

Algorithm 1 High-order Proximity (HOP)

####  3.1.3 Normalized Eigens

We have obtained the high-order similarity matrix $\mathbf{K}$ in Section
3.1.1 and 3.1.2. Then, we obtain the eigen features to prepare for the post-
clustering procedure.

The diagonal matrix $\mathbf{D}\vcentcolon=\mathrm{diag}(\mathbf{K})$, where
the diagonal value $\mathbf{D}_{ii}$ is the degree of the row $i$ of
$\mathbf{K}$ and the off-diagonal elements are $0$. The normalized Laplacian
matrix $\mathbf{L}_{\sigma}$ with ridge regularization $\sigma$ can then be
formed.

$\mathbf{L}_{\sigma}=(\mathbf{D}+\sigma\cdot
d_{max}\cdot\mathbf{I})^{-\frac{1}{2}}\mathbf{K}(\mathbf{D}+\sigma\cdot
d_{max}\cdot\mathbf{I})^{-\frac{1}{2}}$ (7)

where $d_{max}$ is the maximum node degree of the network. The empirical
setting of $\sigma$ is $0.1$.

Next, we compute $k+1$ largest eigenvalues $\bm{\mathbf{\hat{\lambda}}}$ and
their corresponding eigenvectors $\bm{\mathbf{\hat{\Xi}}}$, a.k.a. $k+1$
leading eigenvectors, and sort them in non-descending order by
$\bm{\mathbf{\hat{\lambda}}}$. Consequently, the feature matrix’s dimension is
reduced from $n\times n$ to $n\times(k+1)$. The reduced feature matrix
$\hat{\bm{\Theta}}$ is computed by:

$\hat{\bm{\Theta}}\vcentcolon=\bm{\hat{\Xi}}\cdot
Diag(\bm{\mathbf{\hat{\lambda}}})$ (8)

where $Diag(\bm{\mathbf{\hat{\lambda}}})$ forms a diagonal matrix from a tuple
of eigenvalues $\hat{\lambda}$. Thus, the feature matrix can be expressed as
the matrix dot product of $\bm{\hat{\Xi}}$ and
$Diag(\bm{\mathbf{\hat{\lambda}}})$

####  3.1.4 Eigen-selection and Clustering

We now select a subset of eigen features from $\hat{\bm{\Theta}}$ obtained
from Section 3.1.3 for clustering.

Suppose the high-order matrix $\mathbf{K}$ contains “signal” and “noise”
network information. A network with a “strong signal” has a large gap between
the $k^{th}$ and the $(k+1)^{th}$ eigenvectors of its Laplacian matrix. We
determine whether a network has a “weak” signal profile by setting a threshold
$t>0$,

$\delta_{k+1}=\frac{\bm{\mathbf{\hat{\lambda}}}_{k+1}}{\bm{\mathbf{\hat{\lambda}}}_{k}}\geq
1-t$ (9)

If the above Equation (9) is satisfied, then we say that a network is of “weak
signal” profile. In that case, therefore, the $(k+1)^{th}$ eigenvector
contains useful information as the $k^{th}$ eigenvector. Consequently, we
consider it as one more feature contributing to label clustering. Finally, we
apply the k-means algorithm to the new normalized feature matrix with $k+1$
dimensions to compute the communities.

The pseudocode is presented in Algorithm 2. Line $1$ computes the high-order
proximity of a network from the original affinity matrix using Algorithm 1 and
returns a matrix with the same dimension as its input. Then, we collect
eigenpairs (eigenvalue, eigenvector) of $\mathbf{K}$ and arrange them in
decreasing order by eigenvalues (Lines $2$ to $5$). Lines $8$ \- $9$ determine
if the network has a strong or weak signal profile and assign $k^{\prime}$
accordingly. The algorithm returns a list of clustered node labels. A
flowchart is illustrated in Fig. 1 for easier access to our model framework.

1

Input : $\mathbf{A}\in\mathbb{R}^{n\times n},\sigma>0$,
$t\in(0,1),k\in\mathbb{N}_{>1}$

Output : Node labels: $\hat{\mathbf{y}}$

2 $\mathbf{K}\leftarrow\textnormal{{HOP}}(\mathbf{A})$;

3 $\mathbf{D}\leftarrow\mathrm{Diag}(\mathbf{K})$;

4 $\mathbf{L}_{\sigma}\leftarrow(\mathbf{D}+\sigma\cdot
d_{max}\cdot\mathbf{I})^{-\frac{1}{2}}\mathbf{K}(\mathbf{D}+\sigma\cdot
d_{max}\cdot\mathbf{I})^{-\frac{1}{2}}$;

5 $k^{\prime}\leftarrow k+1$;

6 $\bm{\mathbf{\hat{\lambda}},\
\mathbf{\hat{\Xi}}}\leftarrow\textnormal{{eigsh}}(\mathbf{L}_{\sigma},\
k^{\prime})$;

7
$\mathbf{\hat{\Lambda}}\leftarrow\textnormal{{Diag}}(\bm{\mathbf{\hat{\lambda}}})$
;

8 $\hat{\bm{\Theta}}\leftarrow\bm{\hat{\Xi}}\cdot\hat{\Lambda}$;

9

10if  _$\frac{\hat{\lambda}_{k^{\prime}}}{\hat{\lambda}_{k}} <1-t$_ then

11 $k^{\prime}\leftarrow k$;

12

13$\hat{\mathbf{E}}\leftarrow\\{\frac{\hat{\bm{\Theta}}_{h}}{\hat{\bm{\Theta}}_{1}},\cdots,\frac{\hat{\bm{\Theta}}_{k^{\prime}}}{\hat{\bm{\Theta}}_{1}}\\}$;

$\hat{\mathbf{y}}\leftarrow\textnormal{{k-means}}(\hat{\mathbf{E}},\ k)$;

Algorithm 2 SCOREH+ Figure 1: Flowchart of SCOREH+ Model. This model consists
of three phases: i) the high-order proximity matrix extraction from the
original graph using RBF and Katz; ii) eigen-decomposition from the normalized
Laplacian from the high-proximity matrix; iii) eigen-selection (lines 8 - 9 of
Algorithm 2) and clustering. A step-by-step computation of this toy example is
included in Appendix A.

###  3.2 Time Complexity

The time complexity of the classic spectral clustering (SC) is $O(n^{3})$,
which consists of the construction of similarity matrix ($O(n^{2})$),
computing the $k$ leading eigenvectors ($O(n^{3})$) and the post-k-means
clustering ($O(nk^{2}\ell)$), where $\ell$ is the number of iterations of
convergence at time. Our SCOREH+ algorithm enjoys the same time complexity
bound as SC. Algorithm 1 takes at most $O(n^{3})$ to find the optimal RBF and
calculate the Katz index of the resulting RBF matrix. Algorithm 2 also
requires $O(n^{3})$ to get the leading eigenpairs. Note that the post-k-means
clustering may need $O(n(k+1)^{2}\ell)$ since we consider the $(k+1)^{th}$
eigenvector as a feature for clustering. However, the overall time complexity
is still $O(n^{3})$. In comparison, the time complexity of FastGreedy (Clauset
et al., 2004) and Louvain (Blondel et al., 2008) algorithms are $O(nm^{2})$
and $O(n\log n)$, respectively.

The most expensive step of spectral-based clustering is the computation of the
eigenvalues/eigenvectors of the Laplacian matrix. However,
eigenvalues/eigenvectors can be efficiently computed with approximation
algorithms (Boutsidis et al., 2015). Moreover, the complexity of k-means can
also be reduced to $O(k^{2}\log^{2}k)$ (Tremblay et al., 2016). In social
networks/complex networks, the network is sparse due to the small-world
effect. Therefore, the matrix computations in social networks are efficient in
practice.

##  4 Experimental Settings

We first give an overview of the real-world network and synthetic networks.
Then, we also briefly present the baseline algorithms for comparisons.
Subsequently, we introduce two widely used metrics (modularity and NMI) in
community detection tasks. Finally, we gave the detailed experimental design,
including the programming language, experiment platform, online resources,
etc.

###  4.1 Datasets

####  4.1.1 Real-world Networks

We tested our algorithm and others (ASE, Louvain, fast-Greedy, SC, SCORE, and
SCORE+) on $11$ public real-world network datasets originating from diverse
domains such as social sciences and political sciences. The specific
statistical details for each dataset are provided in Table 3. Note that the
Polbooks network is accessible to the public through
http://www.orgnet.com/divided.html.

Table 3: Statistics of the 11 real-world datasets. The number of nodes and
edges are $n$ and $m$, respectively; the number of clusters is $k$, and the
minimum and maximum of the node degrees are $\min(d)$ and $\max(d)$,
respectively.

No. | Dataset | Reference | $n$ | $m$ | $k$ | $\min(d)$ | $\max(d)$
---|---|---|---|---|---|---|---
$1$ | Les Misérable | (Knuth, 1993) | $77$ | $254$ | $11$ | $1$ | $36$
$2$ | Caltech | (Red et al., 2011) | $590$ | $12,822$ | $172$ | $1$ | $179$
$3$ | Dolphins | (Lusseau et al., 2003) | $62$ | $159$ | $2$ | $1$ | $12$
$4$ | Football | (Girvan and Newman, 2002) | $110$ | $568$ | $11$ | $7$ | $12$
$5$ | Karate | (Zachary, 1977) | $34$ | $78$ | $2$ | $1$ | $17$
$6$ | Polbooks | (Krebs, ) | $92$ | $374$ | $2$ | $1$ | $24$
$7$ | Blog | (Adamic and Glance, 2005) | $1,222$ | $16,714$ | $2$ | $1$ | $351$
$8$ | Simmons | (Traud et al., 2012) | $1,137$ | $24,257$ | $4$ | $1$ | $293$
$9$ | UKfaculty | (Nepusz et al., 2008) | $79$ | $552$ | $3$ | $2$ | $39$
$10$ | Github | (Rozemberczki et al., 2021) | $37,700$ | $289,003$ | $2$ | $1$ | $9,458$
$11$ | Facebook | (Rozemberczki et al., 2021) | $22,470$ | $171,002$ | $4$ | $1$ | $709$

####  4.1.2 Synthetic Networks

We generate a series of synthetic networks using the LFR criteria, first
proposed by Lancichinetti, Fortunato, and Radicchi (Lancichinetti et al.,
2008). A network can be generated in terms of the given parameters: the power-
law exponent for the degree distribution $\tau_{1}$, the power-law exponent
for the community size distribution $\tau_{2}$, the number of nodes $n$, the
average degree $\langle d_{ave}\rangle$, the minimum of communities $c_{min}$,
and the mixing parameter $\mu$. Most importantly, $\mu$ controls the fraction
of edges between communities. Thus, it reflects the amount of noise in the
network. When $\mu=0$, all links are within community links; when $\mu=1$, all
links are between nodes from different communities.

We generate networks by setting the number of nodes ranging from $150$ to
$10,000$ and the key parameter $\mu$ (mixing parameter) from $0.15$ to $0.85$.

###  4.2 Baseline Algorithms

We select traditional greedy methods (Louvain (Blondel et al., 2008), Fast-
Greedy (Clauset et al., 2004)), spectral methods (spectral clustering (SC) (Ng
et al., 2002), Spectral Clustering on Ratios-of-Eigenvectors (SCORE) (Jin,
2015), SCORE+ (Jin et al., 2018)), and a graph embedding based algorithm ASE
as baseline algorithms for comparisons.

  * •

Louvain (Blondel et al., 2008): Louvain is one of the most successful
community detection algorithms with a good balance of effectiveness and
efficiency.

  * •

Fast-Greedy (Clauset et al., 2004): A greedy algorithm that iteratively
searches for nodes with the largest modularity.

  * •

SC (Ng et al., 2002): SC is the classic spectral clustering, wherein the top
$k$ eigenvectors are retained to form the feature matrix, followed by using
k-means as the post-clustering algorithm.

  * •

SCORE (Jin, 2015): SCORE is a modification to the SC algorithm by
incorporating a normalization step that involves the leading eigenvector.

  * •

SCORE+ (Jin et al., 2018): This algorithm extends the SCORE algorithm, and it
considers one more eigenvector as the feature matrix for “weak” signal
networks.

  * •

Adjacency spectral embedding (ASE) (Sussman et al., 2012): ASE is an approach
used to infer the latent positions of a network that is represented as a
Random Dot Product Graph. This embedding serves as both dimensionality
reduction and fitting a generative model.

###  4.3 Evaluation Metrics

####  4.3.1 Modularity

Newman and Girvan (Newman and Girvan, 2004) proposed modularity $\mathit{Q}$
to assess the quality of the detected community structure. It represents the
difference between the actual number of connections and the expected number of
connections in random graphs. The equation is as follows:

$Q=\sum\limits_{s=1}^{k}\left[\dfrac{\ell_{s}}{\ell}-\left(\dfrac{d_{s}}{2\ell}\right)^{2}\right]$
(10)

where $k$ is the number of communities in the network, $\ell$ is the total
number of edges, $\ell_{s}$ is the sum of all edges in the community $s$, and
$d_{s}$ is the sum of the degree of all nodes in $s$. Modularity usually takes
value from $[-0.5,1]$, with positive values indicating the possible presence
of community structure (Newman, 2006). Modularity is used when the ground-
truth labels of a network are unknown. Usually, higher modularity implies a
better community structure.

####  4.3.2 Normalized Mutual Information

Normalized mutual information (NMI) (Danon et al., 2005) is used to evaluate
the community detection algorithms’ network partitioning. It is widely used
due to its comprehensive meaning and ability to compare community labels
$\mathbf{\hat{y}}$ obtained from an algorithm and $\mathbf{y}$, the list of
ground-truth labels. Denote $H(\cdot)$ as the entropy function for graph
partitioning. Then, the mutual information between the ground truth and the
detected labels is:

$\text{MI}(\mathbf{\hat{y}},\mathbf{y})=\sum_{i=1}^{|\mathbf{\hat{y}}|}\sum_{j=1}^{|\mathbf{y}|}\frac{|\mathbf{\hat{y}}_{i}\cap\mathbf{y}_{j}|}{n}\log\left(n\frac{|\mathbf{\hat{y}}_{i}\cap\mathbf{y}_{j}|}{|\mathbf{\hat{y}}_{i}||\mathbf{y}_{j}|}\right)$

Then, the normalized mutual information is:

$\text{NMI}(\mathbf{\hat{y}},\mathbf{y})=\frac{\text{MI}(\mathbf{\hat{y}},\mathbf{y})}{\text{mean}(H(\mathbf{\hat{y}}),H(\mathbf{y}))}$

This metric is independent of the absolute values of the labels and the number
of communities. Note that NMI takes value from 0 to 1, inclusive. When network
labels are known, NMI is a good metric to evaluate the “accuracy” of the
results of a community detection algorithm.

###  4.4 Experimental Design

Our experiments were carried out on a 16.0 GB RAM, 1.90GHz Intel(R) Core(TM)
i7-8650U CPU. The implementations of all algorithms are based on Python 3.9
and its packages. Specifically, the classic spectral clustering (SC) was
adopted from scikit-learn. We re-implement the MatLab codes of SCORE and
SCORE+ from (Jin, 2015; Jin et al., 2018) using Python, where we utilized
scipy and numpy packages for matrix computations. We called the functions of
NetworkX package for the Louvain and FastGreedy algorithms. For ASE, we
followed the graspologic package (Chung et al., 2019) by Johns Hopkins
University and Microsoft
111https://microsoft.github.io/graspologic/latest/index.html. The
implementations of our algorithm in Python is publicly accessible
222https://github.com/yz24/RBF-SCORE.

We tested the proposed algorithm and the baselines on the above-mentioned two
types of data sets. For every network, we run each model ten times on
spectral-based baselines and SCOREH+, evaluate two metrics, and then report
the mean and variance of the results in the form of $mean~{}(variance)$.

##  5 Experimental Results and Analyses

In this section, we show how to choose the number of clusters and select
parameters (RBF function and the corresponding shaping parameter) for RBFs. We
also compare our algorithm SCOREH+ with baseline algorithms on real-world and
synthetic networks. We report the experimental results by scoring the quality
of the discovered communities with modularity and NMI. Moreover, to show the
differences among these models, we compare and analyze the topological
structures of four small networks: Karate, UKfalculty, Dolphin, and Polbooks.

###  5.1 Experimental Results on Real-world Datasets

####  5.1.1 Number of Clusters

We use the method introduced in Section 3.1.4 to determine the number of
clusters for our algorithm. Table 4 reports the type (weak or strong) of each
network by using the value $\delta_{k+1}$ from the high-order matrix computed
by Algorithm 1. We defer the analogous results with respect to the original
affinity matrix to Appendix B.1.

Table 4: type of networks from the high-order matrix and the eigenvalue ratios

No. | Dataset | Type | $\delta_{k+1}$ | $\delta_{k+2}$ | $\delta_{k+3}$
---|---|---|---|---|---
1 | Les Misérable | Strong | 0.172 | 0.04 | 0.231
2 | Caltech | Weak | 0.079 | 0.025 | 0.075
3 | Dolphins | Strong | 0.486 | 0.187 | 0.076
4 | Football | Weak | 0.019 | 0.098 | 0.101
5 | Karate | Strong | 0.257 | 0.426 | 0.164
6 | Polbooks | Strong | 0.818 | 0.092 | 0.148
7 | Blog | Strong | 0.369 | 0.198 | 0.041
8 | Simmons | Strong | 0.242 | 0.328 | 0.205
9 | Ukfaculty | Strong | 0.397 | 0.109 | 0.143
10 | Github | Strong | 0.224 | 0.124 | 0.031
11 | Facebook | Strong | 0.115 | 0.365 | 0.216

Algorithm 1 alters Football to “weak” signal while the Simmons becomes
“strong”. For each “weak” network, our algorithm selects one more eigenvector.
We report the comparison results in Table 5 (Modularity) and Table 6 (NMI). In
this comparison, we use the default Gaussian RBF with shaping parameter $0.1$.
We will analyze the effect of various RBF choices and shaping parameters in
Section 5.1.2.

For the two “weak” signal networks Caltech and Football, we conducted
extensive experiments to show if additional eigenvectors beyond the
$(k+1)^{th}$ one are necessary, and the results are shown in Appendix B.2. The
results demonstrate that more eigenvectors have a limited contribution to the
accuracy of the community detection task. In contrast, additional eigenvectors
can increase the time complexity. Thus, the eigen selection method in this
paper is sufficient.

Table 5: Numerical results on real-world networks (Modularity)

No. | Dataset | ASE | Louvain | Fast-Greedy | SC | SCORE | SCORE+ | SCOREH+
---|---|---|---|---|---|---|---|---
$1$ | Les Misérable | 0.381 | 0.556 | $0.501$ | $-0.019(0.021)$ | $0.386(0.057)$ | $0.239(0.038)$ | $\underline{0.486(0.002)}$
$2$ | Caltech | 0.322 | 0.412 | $0.335$ | $0.39(0.0)$ | $0.372(0.002)$ | $0.373(0.001)$ | $0.368(0.003)$
$3$ | Dolphins | 0.223 | 0.519 | $0.495$ | $0.379(0.0)$ | $0.276(0.0)$ | $0.353(0.0)$ | $0.379(0.0)$
$4$ | Football | 0.622 | $0.622$ | $0.58$ | 0.624(0.0) | $0.622(0.021)$ | 0.624(0.0) | $0.622(0.01)$
$5$ | Karate | 0.37 | 0.42 | $0.381$ | $0.36(0.0)$ | $0.371(0.0)$ | $0.36(0.0)$ | $0.371(0.0)$
$6$ | Polbooks | 0.475 | 0.51 | $0.503$ | $0.479(0.0)$ | $0.473(0.0)$ | $0.479(0.0)$ | $0.479(0.0)$
$7$ | Blog | 0.25 | 0.427 | 0.427 | $0.0(0.0)$ | $\underline{0.423(0.0)}$ | $0.424(0.0)$ | $0.415(0.001)$
$8$ | Simmons | 0.343 | 0.486 | $0.478$ | $0.482(0.0)$ | $0.462(0.0)$ | $0.46(0.0)$ | $0.447(0.004)$
$9$ | UKfaculty | 0.425 | 0.461 | $0.457$ | $0.442(0.0)$ | $0.262(0.131)$ | $0.44(0.0)$ | $0.442(0.0)$
$10$ | Github | 0.171 | $0.153$ | 0.284 | $0.11(0.0)$ | $0.185(0.01)$ | $0.271(0.0)$ | $0.281(0.0)$
$11$ | Facebook | 0.088 | $0.113$ | $0.173$ | $0.154(0.0)$ | $0.145(0.0)$ | $0.097(0.0)$ | 0.175(0.0)

Table 6: Numerical results on real-world networks (NMI)

No. | Dataset | ASE | Louvain | Fast-Greedy | SC | SCORE | SCORE+ | SCOREH+
---|---|---|---|---|---|---|---|---
$1$ | Les Misérable | 0.641 | 0.864 | $0.668$ | $0.377(0.038)$ | $0.686(0.032)$ | $0.616(0.022)$ | $\underline{0.752(0.008)}$
$2$ | Caltech | 0.554 | 0.685 | $0.44$ | $0.63(0.001)$ | $0.58(0.003)$ | $0.574(0.003)$ | $\underline{0.637(0.006)}$
$3$ | Dolphins | 0.383 | $0.484$ | $0.557$ | 1.0(0.0) | $0.588(0.0)$ | $0.811(0.0)$ | 1.0(0.0)
$4$ | Football | 0.944 | $0.884$ | $0.74$ | $0.934(0.0)$ | $0.946(0.022)$ | $0.934(0.0)$ | 0.958(0.012)
$5$ | Karate | 1.0 | $0.687$ | $0.692$ | $0.836(0.0)$ | 1.0(0.0) | $0.836(0.0)$ | 1.0(0.0)
$6$ | Polbooks | 0.784 | $0.553$ | $0.701$ | $0.87(0.0)$ | 0.924(0.0) | $0.87(0.0)$ | $0.87(0.004)$
$7$ | Blog | 0.176 | $0.636$ | $0.654$ | $0.006(0.0)$ | $\underline{0.725(0.0)}$ | 0.751(0.0) | $0.646(0.001)$
$8$ | Simmons | 0.425 | 0.707 | $0.693$ | $\underline{0.702(0.001)}$ | $0.621(0.0)$ | $0.615(0.001)$ | $0.658(0.005)$
$9$ | UKfaculty | 0.621 | $0.834$ | $0.878$ | 0.95(0.0) | $0.658(0.187)$ | $0.917(0.0)$ | 0.95(0.0)
$10$ | Github | 0.146 | $0.0$ | $0.005$ | $0.12(0.0)$ | $0.212(0.01)$ | $0.241(0.0)$ | 0.307(0.0)
$11$ | Facebook | 0.081 | $0.002$ | $0.006$ | $0.08(0.0)$ | $0.11(0.0)$ | $0.132(0.0)$ | 0.146(0.0)

The modularity and NMI values of each algorithm are reported in Table 5
(Modularity) and Table 6 (NMI). The numerical results show that using the
default RBF parameter settings, SCOREH+ achieves the best and second-best on
eight out of eleven networks regarding NMI. It is worth mentioning that Fast-
Greedy (Clauset et al., 2004) and Louvain (Blondel et al., 2008) are designed
to optimize the metric modularity, while spectral-based methods are not.
Therefore, Fast-Greedy (Clauset et al., 2004) and Louvain (Blondel et al.,
2008) usually achieve high modularity and low NMI. However, our algorithm is
based on graph decomposition, neither optimization of modularity nor NMI. The
results from our algorithm are more objective and competitive. Regarding
computational efficiency, our algorithm demonstrates similar runtime
performance to both SCORE and SCORE+. Detailed comparisons of the running
times are provided in Appendix C.

####  5.1.2 RBF selection and tuning of shaping parameters on real-world
networks

In Section 3.1.1, we discussed three common RBFs and their definitions. Each
RBF has a shaping parameter $c$, and it can affect the final graph
interpolation matrix, which, as a consequence, can cause a difference in the
final clustering result. Therefore, we fine-tune the type of RBF and shaping
parameter $c$, and search the optimal parameters where NMI is the criterion.

Tables 5 and 6 show that our algorithm has already achieved the best results
on Dolphins, Football, Karate, UKfaculty, Facebook, and Github without tuning
the RBF shaping parameter. Moreover, we would like to see the domain of
optimal shaping parameters for each RBF. Therefore, we experiment on the
general range of each RBF and report the results in Fig. 2. From Fig. 2, iMQ
RBF is more stable with a constantly small shaping parameter, which means that
using iMQ RBF is more likely to achieve optimal results after a small number
of iterations. Moreover, although the shaping parameter ranges from $[0,1]$
for iMQ RBF, the empirical experiments from these $11$ real-world networks
show that the optimal parameter falls into $[0,0.1]$. This aids in fine-tuning
the parameters in real-life applications.

Table 7: Optimal RBF and corresponding shaping parameter

No. | Datasets | optimal RBF | shaping parameter | NMI | Modularity
---|---|---|---|---|---
$1$ | Les Misérable | gaussian | $0.64$ | $0.752$ | $0.48$
$2$ | Caltech | gaussian | $0.57$ | $0.646$ | $0.4$
$3$ | Dolphins | MQ | $0$ | $1$ | $0.379$
$4$ | Football | MQ | $0.303$ | $0.958$ | $0.62$
$5$ | Karate | iMQ | $0.0245$ | $1$ | $0.371$
$6$ | Polbooks | iMQ | $0.0318$ | $0.924$ | $0.473$
$7$ | Blog | iMQ | $0.0664$ | $0.789$ | $0.415$
$8$ | Simmons | MQ | $1.1616$ | $0.703$ | $0.481$
$9$ | UKfaculty | gaussian | $0.53$ | $0.95$ | $0.442$
$10$ | Github | gaussian | $0.21$ | $0.307$ | $0.281$
$11$ | Facebook | gaussian | $0.17$ | $0.146$ | $0.175$

In addition, our algorithm performs better if we fine-tune the shaping
parameters. Table 7 lists the optimal RBF for each network and the
corresponding optimal shaping parameter. We can also interpret that the
algorithm has no preferences for any RBFs, and all the common RBFs work well
on some networks. The results demonstrate that overall, with the optimal RBF,
our algorithm made improvements on Caltech, Polbooks, Blog, and Simmons.

Figure 2: Optimal shaping parameters with RBF choices on real-world networks.

###  5.2 Analyses: Real-World Networks

In this section, we analyze and visualize the results of spectral-based
algorithms on Karate, UKfaculty, Dolphins, and Polbooks. The analyses of the
last two networks are deferred to Appendix D. We draw the network structure
using the node size to differentiate the node degree and the node color to
distinguish the community label. For each smaller network, we plot the
topological structure of the results detected by SC, SCORE, SCORE+, and our
SCOREH+ to show the differences between those algorithms.

####  5.2.1 Analysis of Karate Network

Zachary’s karate club network is a social network widely used to test
community detection algorithms. This network contains $34$ nodes and $78$
edges, and it was divided into two communities because of the contradictions
between the “president” and the “instructor” of the karate club. The real
topological structure of this network is present in Figure 3(a), and the
community detected by SCORE, SCORE+, and our SCOREH+ are present in Figure
3(b), 3(c), and 3(d), respectively. Note that the numbering of the subgraphs
for the other networks is the same as in Karate.

(a) Ground-truth network

(b) Results from SCORE

(c) Results from SCORE+

(d) Results from SCOREH+

Figure 3: The topological displays for the Karate network from SCORE, SCORE+,
and our SCOREH+ algorithms (3(a) is plotted from the ground truth of the
network for comparison. 3(b), 3(c)) and 3(d) are from the node labels
discovered by SCORE, SCORE+, and our SCOREH+, respectively. The similar
settings apply to Fig. 4.

For this network, SCORE+ misclassified the number $3$ node while SCORE and our
SCOREH+ achieved state-of-the-art results.

####  5.2.2 Analysis of UKfaculty Network

The UKfaculty network (Nepusz et al., 2008) is a personal friendship network
of UK university faculty, and the school affiliation of each individual is
stored as a node label. It comprises $81$ vertices (individuals) and $817$
weighted edges, and three communities.

(a) Ground-truth network

(b) Results from SCORE

(c) Results from SCORE+

(d) Results from SCOREH+

Figure 4: The topological displays for the UKfaculty network from SCORE,
SCORE+, and our SCOREH+ algorithms (4(a) is from the ground-truth of the
network).

For this network, the experimental comparisons in Fig. 4 indicate that SCORE
misclassified the numbers $9$, $38$, $59$, $61$, $79$ nodes, and SCORE+ made
mistakes on the numbers $59$ and $61$ nodes. However, our SCOREH+ only has one
misclassified node at node number $61$.

####  5.2.3 Community structures of other Networks

It becomes more work to visualize the structural quality for larger-scale
networks. In that case, for Caltech, Football, Blog, and Simmons, we present
the topological plots in Fig. 5 by our SCOREH+ algorithm. The Football network
(Girvan and Newman, 2002) contained the relationships of American football
games between Division IA colleges during the regular season in Fall 2000. The
Blog is a directed network of hyperlinks between weblogs on US politics,
recorded in 2005 by Adamic and Glance (Adamic and Glance, 2005). In our
experiment, we treat it as an undirected network. Simmons and Caltech (Red et
al., 2011) are parts of the Facebook friendship networks, recorded in 2005.

(a) Caltech

(b) Football

(c) Blog

(d) Simmons

Figure 5: The topological displays for Caltech (Fig. 5(a)), Football (Fig.
5(b)), Blog (Fig. 5(c)), and Simmons (Fig. 5(d)), respectively, from the
results of our SCOREH+ algorithms.

SCOREH+ can detect communities from the above four larger networks. Moreover,
the communities show clear clustering properties where the nodes of the same
color are close to each other, while the nodes are sparsely connected between
different communities. For example, the Caltech social network has eight large
clusters and hundreds of small clusters. The political Blog network has two
communities in reality, but some “blogs” are neutral (green on nodes). It is
also reasonable and natural to split this network into three clusters.

###  5.3 Analyses: Synthetic Networks

In this subsection, we use the networks generated from the LFR criteria
(Lancichinetti et al., 2008). The parameters $\tau_{1}$ and $\tau_{2}$ are
fixed to be $1.0$ and $1.5$, respectively, for all networks. The number of
nodes ranges from $150$ to $10,000$, and the key parameter $\mu$ (mixing
parameter) from $0.15$ to $0.85$. Since $\mu$ determines the network noise, we
only compare the results with $0.35\leq\mu\leq 0.65$. When $\mu$ is too small
($\mu\leq 0.25$), the network will be too easy to discover for all the
algorithms, while it will be too hard when $\mu$ is too large ($\mu>0.65$).

We report the results when the numbers of nodes are $5,000$ and $10,000$ with
$\mu$ varying from $0.15$ to $0.85$, and when $\mu=0.35,0.55$ with $N$ chosen
from $150$ to $10,000$. The detailed tables and extensive figures are attached
to Appendix E.1, Appendix E.2, and Appendix E.3, respectively.

####  5.3.1 Comparisons with respect to the number of nodes

We fix the mixing parameter $\mu$ and compare the performance acquired from
ASE, Louvain, fast-Greedy, SC, SCORE, SCORE+, and our SCOREH+. As we can
observe from the modularity and NMI comparisons (Fig. 6), when $\mu$ are
relatively small, SCORE+ and SCOREH+ can obtain excellent community structure,
especially for small networks. However, as $\mu$ grows, the superiority of
SCOREH+ is obvious. The reason is that our SCOREH+ can preserve more local
information, and this property makes a difference when the network is noisy.

Figure 6: The comparison plots on LFR datasets with various numbers of nodes
($N$). The top two plots show the comparisons of modularity measure with
respect to the various number of nodes when the mixing parameter $\mu$ is
fixed. The bottom two plots are comparisons regarding NMI.

####  5.3.2 Comparisons with respect to mixing parameter $\mu$

In this subsection, we compare the performance of each algorithm when the
mixing parameter $\mu$ is fixed. Next, we show how mixing parameters affect
the results on the same scale as networks. The modularity and NMI comparisons
(Fig. 7) show that $\mu$ greatly affects the performance of algorithms. This
is reasonable since it determines the difficulty of a network. When $\mu$ is
very small, every algorithm can detect nearly perfect communities, while a
large $\mu$ can result in a modularity metric with approximately $0$,
representing a nearly random community discovery.

Figure 7: The comparison plots on LFR datasets with various mixing parameters
$\mu$. The top two plots show the comparisons of modularity measures with
respect to the mixing parameters. The bottom two plots are comparisons
regarding NMI.

##  6 Conclusion and Future Work

We proposed an improved algorithm based on SCORE+ for detecting communities in
complex networks. The RBF implementation and the choice of the optimal shaping
parameter cast the node vector into an approximation domain while retaining
high-order information. This approach proves particularly robust in noisy
networks, surpassing the performance of conventional algorithms. A careful
selection of radial basis functions (RBFs) and shaping parameters is of
greatest significance in order to attain a successful result. Furthermore,
numerical results show that the optimal parameters frequently exist within a
limited range. This observation provides a valuable guideline for adjusting
RBF settings in similar large systems, promoting greater efficiency and
optimal resutls.

In the future, there are various enhancements that we intend to implement.
Firstly, the cost of finding the eigenvalues and eigenvectors of a large
sparse matrix is very high. In the case of a large network, it is necessary to
use an iterative approach, such as the Lanczos algorithm, to solve eigenvalue
problems. Additionally, when implementing the Katz index for large sparse
networks, applying iterative methods, for instance, the Krylov iterative
methods is advantageous. Lastly, we would focus on developing a correlation
between specific metrics and the optimal RBF shaping parameter. This
correlation could aid in the iterative optimization of the algorithm without
the need to compute the final results.

## References

  * Adamic and Glance (2005) Lada A Adamic and Natalie Glance.  The political blogosphere and the 2004 us election: divided they blog.  In _Proceedings of the 3rd international workshop on Link discovery_ , pages 36–43, 2005.
  * Ball (1992) Keith Ball.  Eigenvalues of euclidean distance matrices.  _Journal of Approximation Theory_ , 68(1):74–82, 1992.
  * Berahmand et al. (2021) Kamal Berahmand, Elahe Nasiri, Yuefeng Li, et al.  Spectral clustering on protein-protein interaction networks via constructing affinity matrix using attributed graph embedding.  _Computers in Biology and Medicine_ , 138:104933, 2021.
  * Berahmand et al. (2022) Kamal Berahmand, Mehrnoush Mohammadi, Azadeh Faroughi, and Rojiar Pir Mohammadiani.  A novel method of spectral clustering in attributed networks by constructing parameter-free affinity matrix.  _Cluster Computing_ , pages 1–20, 2022.
  * Blondel et al. (2008) Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre.  Fast unfolding of communities in large networks.  _Journal of statistical mechanics: theory and experiment_ , 2008(10):P10008, 2008.
  * Boers et al. (2019) Niklas Boers, Bedartha Goswami, Aljoscha Rheinwalt, Bodo Bookhagen, Brian Hoskins, and Jürgen Kurths.  Complex networks reveal global pattern of extreme-rainfall teleconnections.  _Nature_ , 566(7744):373–377, 2019.
  * Bonacich (2007) Phillip Bonacich.  Some unique properties of eigenvector centrality.  _Social networks_ , 29(4):555–564, 2007.
  * Boutsidis et al. (2015) Christos Boutsidis, Prabhanjan Kambadur, and Alex Gittens.  Spectral clustering via the power method-provably.  In _International conference on machine learning_ , pages 40–48. PMLR, 2015.
  * Cao et al. (2015) Shaosheng Cao, Wei Lu, and Qiongkai Xu.  Grarep: Learning graph representations with global structural information.  In _Proceedings of the 24th ACM international on conference on information and knowledge management_ , pages 891–900, 2015.
  * Chen (2015) Xing Chen.  Katzlda: Katz measure for the lncrna-disease association prediction.  _Scientific reports_ , 5(1):1–11, 2015.
  * Chung et al. (2019) Jaewon Chung, Benjamin D Pedigo, Eric W Bridgeford, Bijan K Varjavand, Hayden S Helm, and Joshua T Vogelstein.  Graspy: Graph statistics in python.  _J. Mach. Learn. Res._ , 20(158):1–7, 2019.
  * Clauset et al. (2004) Aaron Clauset, Mark EJ Newman, and Cristopher Moore.  Finding community structure in very large networks.  _Physical review E_ , 70(6):066111, 2004.
  * Dabbaghjamanesh et al. (2019) Morteza Dabbaghjamanesh, Boyu Wang, Abdollah Kavousi-Fard, Shahab Mehraeen, Nikos D Hatziargyriou, Dimitris N Trakas, and Farzad Ferdowsi.  A novel two-stage multi-layer constrained spectral clustering strategy for intentional islanding of power grids.  _IEEE Transactions on Power Delivery_ , 35(2):560–570, 2019.
  * Danon et al. (2005) Leon Danon, Albert Diaz-Guilera, Jordi Duch, and Alex Arenas.  Comparing community structure identification.  _Journal of statistical mechanics: Theory and experiment_ , 2005(09):P09008, 2005.
  * Duan et al. (2019) Yaqi Duan, Tracy Ke, and Mengdi Wang.  State aggregation learning from markov transition data.  _Advances in Neural Information Processing Systems_ , 2019.
  * Fasshauer (2007) Gregory E Fasshauer.  _Meshfree approximation methods with MATLAB_ , volume 6.  World Scientific, 2007.
  * Gao et al. (2018) Chao Gao, Zongming Ma, Anderson Y Zhang, and Harrison H Zhou.  Community detection in degree-corrected block models.  _The Annals of Statistics_ , 46(5):2153–2185, 2018.
  * Girvan and Newman (2002) Michelle Girvan and Mark EJ Newman.  Community structure in social and biological networks.  _Proceedings of the national academy of sciences_ , 99(12):7821–7826, 2002.
  * Guerrero et al. (2017) Manuel Guerrero, Francisco G Montoya, Raúl Baños, Alfredo Alcayde, and Consolación Gil.  Adaptive community detection in complex networks using genetic algorithms.  _Neurocomputing_ , 266:101–113, 2017.
  * Gupta and Kumar (2020) Samrat Gupta and Pradeep Kumar.  An overlapping community detection algorithm based on rough clustering of links.  _Data & Knowledge Engineering_, 125:101777, 2020.
  * Hu et al. (2019) Fang Hu, Yanhui Zhu, Jia Liu, and Yalin Jia.  Computing communities in complex networks using the dirichlet processing gaussian mixture model with spectral clustering.  _Physics Letters A_ , 383(9):813–824, 2019.
  * Huang et al. (2019) Zhenyu Huang, Joey Tianyi Zhou, Xi Peng, Changqing Zhang, Hongyuan Zhu, and Jiancheng Lv.  Multi-view spectral clustering network.  In _IJCAI_ , volume 2, page 4, 2019.
  * Jin et al. (2021) Di Jin, Zhizhi Yu, Pengfei Jiao, Shirui Pan, Dongxiao He, Jia Wu, Philip Yu, and Weixiong Zhang.  A survey of community detection approaches: From statistical modeling to deep learning.  _IEEE Transactions on Knowledge and Data Engineering_ , 2021.
  * Jin (2015) Jiashun Jin.  Fast community detection by score.  _The Annals of Statistics_ , 43(1):57–89, 2015.
  * Jin et al. (2018) Jiashun Jin, Zheng Tracy Ke, and Shengming Luo.  Score+ for network community detection.  _arXiv preprint arXiv:1811.05927_ , 2018.
  * Katz (1953) Leo Katz.  A new status index derived from sociometric analysis.  _Psychometrika_ , 18(1):39–43, 1953.
  * Kinsley et al. (2020) Amy C Kinsley, Gianluigi Rossi, Matthew J Silk, and Kimberly VanderWaal.  Multilayer and multiplex networks: An introduction to their use in veterinary epidemiology.  _Frontiers in veterinary science_ , 7:596, 2020.
  * Knuth (1993) Donald Ervin Knuth.  _The Stanford GraphBase: a platform for combinatorial computing_ , volume 1.  AcM Press New York, 1993.
  * (29) Valdis Krebs.  Political polarization during the 2008 us presidential campaign.  URL http://www.orgnet.com/divided.html.
  * Kumar et al. (2017) Pradeep Kumar, Samrat Gupta, and Bharat Bhasker.  An upper approximation based community detection algorithm for complex networks.  _Decision Support Systems_ , 96:103–118, 2017.
  * Lancichinetti et al. (2008) Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi.  Benchmark graphs for testing community detection algorithms.  _Physical review E_ , 78(4):046110, 2008.
  * Law et al. (2017) Marc T Law, Raquel Urtasun, and Richard S Zemel.  Deep spectral clustering learning.  In _International conference on machine learning_ , pages 1985–1994. PMLR, 2017.
  * Li et al. (2021) Hui-Jia Li, Lin Wang, Zhan Bu, Jie Cao, and Yong Shi.  Measuring the network vulnerability based on markov criticality.  _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , 16(2):1–24, 2021.
  * Li et al. (2022a) Hui-Jia Li, Shenpeng Song, Wenze Tan, Zhaoci Huang, Xiaoyan Li, Wenzhe Xu, and Jie Cao.  Characterizing the fuzzy community structure in link graph via the likelihood optimization.  _Neurocomputing_ , 512:482–493, 2022a.
  * Li et al. (2022b) Huijia Li, Wenzhe Xu, Chenyang Qiu, and Jian Pei.  Fast markov clustering algorithm based on belief dynamics.  _IEEE Transactions on Cybernetics_ , 2022b.
  * Liben-Nowell and Kleinberg (2007) David Liben-Nowell and Jon Kleinberg.  The link-prediction problem for social networks.  _Journal of the American society for information science and technology_ , 58(7):1019–1031, 2007.
  * Liu et al. (2022) Dong Liu, Guoliang Yang, Yanwei Wang, Hu Jin, and Enhong Chen.  How to protect ourselves from overlapping community detection in social networks.  _IEEE Transactions on Big Data_ , 2022.
  * Lü et al. (2009) Linyuan Lü, Ci-Hang Jin, and Tao Zhou.  Similarity index based on local paths for link prediction of complex networks.  _Physical Review E_ , 80(4):046122, 2009.
  * Lusseau et al. (2003) David Lusseau, Karsten Schneider, Oliver J Boisseau, Patti Haase, Elisabeth Slooten, and Steve M Dawson.  The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations.  _Behavioral Ecology and Sociobiology_ , 54(4):396–405, 2003.
  * Nepusz et al. (2008) Tamás Nepusz, Andrea Petróczi, László Négyessy, and Fülöp Bazsó.  Fuzzy communities and the concept of bridgeness in complex networks.  _Physical Review E_ , 77(1):016107, 2008.
  * Newman (2006) Mark EJ Newman.  Modularity and community structure in networks.  _Proceedings of the national academy of sciences_ , 103(23):8577–8582, 2006.
  * Newman (2013) Mark EJ Newman.  Community detection and graph partitioning.  _EPL (Europhysics Letters)_ , 103(2):28003, 2013.
  * Newman and Girvan (2004) Mark EJ Newman and Michelle Girvan.  Finding and evaluating community structure in networks.  _Physical review E_ , 69(2):026113, 2004.
  * Ng et al. (2002) Andrew Y Ng, Michael I Jordan, and Yair Weiss.  On spectral clustering: Analysis and an algorithm.  In _Advances in neural information processing systems_ , pages 849–856, 2002.
  * Noorizadegan et al. (2022) Amir Noorizadegan, Chuin-Shan Chen, DL Young, and CS Chen.  Effective condition number for the selection of the rbf shape parameter with the fictitious point method.  _Applied Numerical Mathematics_ , 178:280–295, 2022.
  * Ou et al. (2016) Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu.  Asymmetric transitivity preserving graph embedding.  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 1105–1114, 2016.
  * Park and Zhao (2018) Seyoung Park and Hongyu Zhao.  Spectral clustering based on learning similarity matrix.  _Bioinformatics_ , 34(12):2069–2076, 2018.
  * Polito and Perona (2002) Marzia Polito and Pietro Perona.  Grouping and dimensionality reduction by locally linear embedding.  In T. Dietterich, S. Becker, and Z. Ghahramani, editors, _Advances in Neural Information Processing Systems_ , volume 14. MIT Press, 2002.  URL https://proceedings.neurips.cc/paper/2001/file/a5a61717dddc3501cfdf7a4e22d7dbaa-Paper.pdf.
  * Pons and Latapy (2005) Pascal Pons and Matthieu Latapy.  Computing communities in large networks using random walks.  In _International symposium on computer and information sciences_ , pages 284–293. Springer, 2005.
  * Red et al. (2011) Veronica Red, Eric D Kelsic, Peter J Mucha, and Mason A Porter.  Comparing community structure to characteristics in online collegiate social networks.  _SIAM review_ , 53(3):526–543, 2011.
  * Rentería-Ramos et al. (2018) Rafael Rentería-Ramos, Rafael Hurtado, and B Piedad Urdinola.  Epidemiology, public health and complex networks.  _Memorias_ , pages 9–23, 2018.
  * Roghani and Bouyer (2022) Hamid Roghani and Asgarali Bouyer.  A fast local balanced label diffusion algorithm for community detection in social networks.  _IEEE Transactions on Knowledge and Data Engineering_ , 2022.
  * Rosvall and Bergstrom (2007) Martin Rosvall and Carl T Bergstrom.  An information-theoretic framework for resolving community structure in complex networks.  _Proceedings of the national academy of sciences_ , 104(18):7327–7331, 2007.
  * Rozemberczki et al. (2021) Benedek Rozemberczki, Carl Allen, and Rik Sarkar.  Multi-scale attributed node embedding.  _Journal of Complex Networks_ , 9(2):cnab014, 2021.
  * Shang et al. (2022) Ronghua Shang, Weitong Zhang, Jingwen Zhang, Jie Feng, and Licheng Jiao.  Local community detection based on higher-order structure and edge information.  _Physica A: Statistical Mechanics and its Applications_ , 587:126513, 2022.
  * Sharma et al. (2015) Dravyansh Sharma, Ashish Kapoor, and Amit Deshpande.  On greedy maximization of entropy.  In _International Conference on Machine Learning_ , pages 1330–1338. PMLR, 2015.
  * Sussman et al. (2012) Daniel L Sussman, Minh Tang, Donniell E Fishkind, and Carey E Priebe.  A consistent adjacency spectral embedding for stochastic blockmodel graphs.  _Journal of the American Statistical Association_ , 107(499):1119–1128, 2012.
  * Tang et al. (2015) Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei.  Line: Large-scale information network embedding.  In _Proceedings of the 24th international conference on world wide web_ , pages 1067–1077, 2015.
  * Traud et al. (2012) Amanda L Traud, Peter J Mucha, and Mason A Porter.  Social structure of facebook networks.  _Physica A: Statistical Mechanics and its Applications_ , 391(16):4165–4180, 2012.
  * Tremblay et al. (2016) Nicolas Tremblay, Gilles Puy, Rémi Gribonval, and Pierre Vandergheynst.  Compressive spectral clustering.  In _International conference on machine learning_ , pages 1002–1011. PMLR, 2016.
  * Yang et al. (2016) Liang Yang, Xiaochun Cao, Dongxiao He, Chuan Wang, Xiao Wang, and Weixiong Zhang.  Modularity based community detection with deep learning.  In _IJCAI_ , volume 16, pages 2252–2258, 2016.
  * Zachary (1977) Wayne W Zachary.  An information flow model for conflict and fission in small groups.  _Journal of anthropological research_ , 33(4):452–473, 1977.
  * Zelnik-manor and Perona (2004) Lihi Zelnik-manor and Pietro Perona.  Self-tuning spectral clustering.  In L. Saul, Y. Weiss, and L. Bottou, editors, _Advances in Neural Information Processing Systems_ , volume 17. MIT Press, 2004.  URL https://proceedings.neurips.cc/paper/2004/file/40173ea48d9567f1f393b20c855bb40b-Paper.pdf.
  * Zhang and Xu (2021) Haimin Zhang and Min Xu.  Graph neural networks with multiple kernel ensemble attention.  _Knowledge-Based Systems_ , 229:107299, 2021.
  * Zhang et al. (2019) Yunlei Zhang, Bin Wu, Nianwen Ning, Chenguang Song, and Jinna Lv.  Dynamic topical community detection in social network: A generative model approach.  _IEEE Access_ , 7:74528–74541, 2019.
  * Zhang et al. (2018) Ziwei Zhang, Peng Cui, Xiao Wang, Jian Pei, Xuanrong Yao, and Wenwu Zhu.  Arbitrary-order proximity preserved network embedding.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 2778–2786, 2018.
  * Zhang et al. (2017) Zuping Zhang, Jingpu Zhang, Chao Fan, Yongjun Tang, and Lei Deng.  Katzlgo: large-scale prediction of lncrna functions by using the katz measure based on multiple networks.  _IEEE/ACM transactions on computational biology and bioinformatics_ , 16(2):407–416, 2017.
  * Zhou and Amini (2019) Zhixin Zhou and Arash A Amini.  Analysis of spectral clustering algorithms for community detection: the general bipartite setting.  _The Journal of Machine Learning Research_ , 20(1):1774–1820, 2019.

##  A An Example on the Toy Example in Figure 1

To help the readers better understand our framework, we present step-by-step
computations on the toy example illustrated in Figure 1. In this undirected
toy network $G=(\\{1,2,3,4,5,6\\},\\{(1,2),(2,3),(2,4),(3,4),(3,5),(5,6)\\})$,
we assume the number of clusters is $k=2$.

  * Step 1:

Sample an affinity matrix $\mathbf{A}$ from the original (undirected) network
$G$.
The condition number of matrix $\mathbf{A}$ is $c_{A}=3.0896$.

$\mathbf{A}=\begin{bmatrix}0&1&0&0&0&0\\\ 1&0&1&1&0&0\\\ 0&1&0&1&1&0\\\
0&1&1&0&0&0\\\ 0&0&1&0&0&1\\\
0&0&0&0&1&0\end{bmatrix},\quad\mathbf{B}=\begin{bmatrix}0&0.404&0&0&0&0\\\
0.404&0&0.404&0.027&0&0\\\ 0&0.404&0&0.404&0.027&0\\\ 0&0.027&0.404&0&0&0\\\
0&0&0.027&0&0&0.404\\\ 0&0&0&0&0.404&0\end{bmatrix}\quad$

  * Step 2:

Form the RBF matrix $\mathbf{B}$.
Apply Gaussian RBF with shaping parameter $c=0.2$ and form the RBF matrix
$\mathbf{B}$, using Eq.(5). The condition number decreases to $c_{B}=1.486$.

  * Step 3:

Compute the high-order proximity matrix $\mathbf{K}$.
Compute $\mathbf{K}$ from the RBF matrix $\mathbf{B}$ using Katz index
($\beta=0.0025$). The high-order matrix preserving the more indirect neighbor
information is $\mathbf{K}$. The condition number of $\mathbf{K}$ is
$c_{K}=1.488$

$\mathbf{K}=\begin{bmatrix}$1.02e-06$&0.001&$1.02e-06$&$6.81e-08$&$6.76e-11$&$6.83e-14$\\\
0.001&$2.04e-06$&0.001&$6.74e-05$&$6.70e-08$&$6.76e-11$\\\
$1.02e-06$&0.001&$2.04e-06$&0.001&$6.64e-05$&$6.70e-08$\\\
$6.81e-08$&$6.74e-05$&0.001&$1.02e-06$&$6.70e-08$&$6.76e-11$\\\
$6.76e-11$&$6.70e-08$&$6.64e-05$&$6.70e-08$&$1.02e-06$&0.001\\\
$6.83e-14$&$6.76e-11$&$6.70e-08$&$6.76e-11$&0.001&$1.02e-06$\end{bmatrix}$

  * Step 4:

Construct a degree matrix $\mathbf{D}$ from $\mathbf{K}$.

$\mathbf{D}=\begin{bmatrix}28.627&0&0&0&0&0\\\ 0&20.865&0&0&0&0\\\
0&0&20.865&0&0&0\\\ 0&0&0&27.877&0&0\\\ 0&0&0&0&27.889&0\\\
0&0&0&0&0&28.639\end{bmatrix}$

  * Step 5:

Form a normalized Laplacian matrix $\mathbf{L}_{\sigma}$
$\mathbf{L}_{\sigma}$ is computed using Eq. (7) with $\sigma=0.1$.

$\mathbf{L}_{\sigma}=\begin{bmatrix}0.0008&0.6028&0.0006&$5.4e-05$&$5.4e-08$&$5.59e-11$\\\
0.6028&0.0008&0.4394&0.0392&$3.9e-05$&$4.0e-08$\\\
0.0006&0.4394&0.0008&0.5871&0.0386&$4.0e-05$\\\
$5.4e-05$&0.0392&0.5871&0.0007&$5.2e-05$&$5.4e-08$\\\
$5.4e-08$&$3.9e-05$&0.0386&$5.2e-05$&0.0007&0.8061\\\
$5.5e-11$&$4.0e-08$&$4.0e-05$&$5.4e-08$&0.8061&0.0008\end{bmatrix}$

  * Step 6:

Compute $k+1=3$ eigenvalues $\bm{\mathbf{\hat{\lambda}}}$ and their
corresponding three eigenvectors $\bm{\mathbf{\hat{\Theta}}}$.

$\bm{\mathbf{\hat{\lambda}}}=\begin{bmatrix}-0.8421\quad 0.8040\quad
0.8774\end{bmatrix},\quad\bm{\mathbf{\hat{\Theta}}}=\begin{bmatrix}0.3837&0.1053&0.3913\\\
-0.5371&0.1402&0.5684\\\ 0.5349&0.1044&0.5611\\\ -0.3475&0.0831&0.4012\\\
-0.2866&-0.6884&0.1608\\\ 0.2741&-0.6909&0.1479\\\ \end{bmatrix}$

  * Step 7:

Decide if the network is of weak signal or strong signal.
From the Step 6, it is clear that Eq. (9) is not satisfied since the smallest
eigenvalue $\bm{\mathbf{\hat{\lambda}}}_{3}$ is negative. Therefore, we
preserve the largest two eigenvalues and their corresponding eigenvectors
(last two columns).

  * Step 8:

Construct new feature matrix $\mathbf{F}$.
Normalize the eigenvectors with the largest eigenvector (last column of
$\bm{\mathbf{\hat{\Theta}}}$). Construct a new feature matrix $\mathbf{F}$.
Note that the largest eigenvector is discarded because we used it to normalize
the others. It should contain all $1$’s after normalization by itself, which
has no information for clustering.

$\mathbf{F}=\begin{bmatrix}0.2692\\\ 0.2467\\\ 0.1861\\\ 0.2072\\\ -4.2802\\\
-4.6704\\\ \end{bmatrix}$

  * Step 9:

Compute the communities.
Apply k-means on $\mathbf{F}$ and get the final node labels
$\bm{\mathbf{\hat{y}}}$.

$\bm{\mathbf{\hat{y}}}^{T}=[0\quad 0\quad 0\quad 0\quad 1\quad 1]$

  * Step 10:

Evaluate the results.
Evaluate the community structure using Modularity described in Section 4.3.1,
the metric value is $0.208$.

Remark: In this toy-network $G$, nodes $1,2,3,4$ are divided into the same
community and nodes $5,6$ are group to the other one. This result is intuitive
by the topological structure illustrated in Figure 1.

##  B Omitted Results in Subsection 5.1.1

###  B.1 Eigenvalue Ratios of Real-World Networks

Table 8: Type of networks from the original affinity matrix and the eigenvalue
ratios

No. | Dataset | Type | $\delta_{k+1}$ | $\delta_{k+2}$ | $\delta_{k+3}$
---|---|---|---|---|---
$1$ | Les Misérable | Weak | $0.032$ | $0.066$ | $0.103$
$2$ | Caltech | Weak | $0.078$ | $0.098$ | $0.132$
$3$ | Dolphins | Strong | $0.186$ | $0.143$ | $0.165$
$4$ | Football | Strong | $0.187$ | $0.071$ | $0.218$
$5$ | Karate | Strong | $0.414$ | $0.208$ | $0.356$
$6$ | Polbooks | Strong | $0.503$ | $0.045$ | $0.143$
$7$ | Blog | Strong | $0.6$ | $0.162$ | $0.085$
$8$ | Simmons | Weak | $0.08$ | $0.1$ | $0.058$
$9$ | Ukfaculty | Strong | $0.314$ | $0.117$ | $0.118$
$10$ | Github | Strong | $0.256$ | $0.112$ | $0.063$
$11$ | Facebook | Strong | $0.128$ | $0.279$ | $0.106$

Table 9: Type of networks from the high-order matrix and the eigenvalue ratios

No. | Dataset | Type | $\delta_{k+1}$ | $\delta_{k+2}$ | $\delta_{k+3}$
---|---|---|---|---|---
$1$ | Les Misérable | Strong | $0.172$ | $0.04$ | $0.231$
$2$ | Caltech | Weak | $0.079$ | $0.025$ | $0.075$
$3$ | Dolphins | Strong | $0.486$ | $0.187$ | $0.076$
$4$ | Football | Weak | $0.019$ | $0.098$ | $0.101$
$5$ | Karate | Strong | $0.257$ | $0.426$ | $0.164$
$6$ | Polbooks | Strong | $0.818$ | $0.092$ | $0.148$
$7$ | Blog | Strong | $0.369$ | $0.198$ | $0.041$
$8$ | Simmons | Strong | $0.242$ | $0.328$ | $0.205$
$9$ | Ukfaculty | Strong | $0.397$ | $0.109$ | $0.143$
$10$ | Github | Strong | $0.224$ | $0.124$ | $0.031$
$11$ | Facebook | Strong | $0.115$ | $0.365$ | $0.216$

###  B.2 Extensive Experiments on Weak Signal Networks

Table 10: Extensive Experiments on Weak Signal Networks

Dataset | Metric | $k$ | $k+1$ | $k+2$ | $k+3$
---|---|---|---|---|---
| NMI | $0.63$ | $0.646$ | $0.647$ | $0.646$
Caltech | Q | $0.36$ | $0.4$ | $0.394$ | $0.391$
| NMI | $0.934$ | $0.958$ | $0.957$ | $0.957$
Football | Q | $0.623$ | $0.62$ | $0.62$ | $0.62$

##  C Comparisons of Running Time on Real-World Networks

Table 11: Comparisons of running time(s) on real-world networks

No. | Dataset | ASE | Louvain | Fast-Greedy | SC | SCORE | SCORE+ | SCOREH+
---|---|---|---|---|---|---|---|---
$1$ | Les Miserable | 0.034 | $0.03$ | $0.012$ | $0.03$ | $0.048$ | $0.024$ | $0.033$
$2$ | Caltech | 0.208 | $0.096$ | $1.225$ | $0.087$ | $0.097$ | $0.096$ | $0.178$
$3$ | Dolphins | 0.024 | $0.012$ | $0.006$ | $0.013$ | $0.01$ | $0.017$ | $0.013$
$4$ | Football | 0.028 | $0.015$ | $0.025$ | $0.024$ | $0.011$ | $0.019$ | $0.026$
$5$ | Karate | 0.011 | $0.011$ | $0.013$ | $0.01$ | $0.01$ | $0.011$ | $0.011$
$6$ | Polbooks | 0.015 | $0.012$ | $0.018$ | $0.016$ | $0.008$ | $0.01$ | $0.014$
$7$ | Blog | 0.408 | $0.231$ | $0.995$ | $0.057$ | $0.037$ | $0.113$ | $0.448$
$8$ | Simmons | 0.256 | $0.212$ | $0.243$ | $0.109$ | $0.121$ | $0.144$ | $0.365$
$9$ | UKfaculty | 0.017 | $0.015$ | $0.018$ | $0.013$ | $0.01$ | $0.011$ | $0.018$
$10$ | github | 22.6 | $12.45$ | $18.6$ | $15.2$ | $15.4$ | $20.7$ | $28.8$
$11$ | facebook | 21.78 | $13.19$ | $29.9$ | $22.5$ | $22.3$ | $29.2$ | $33.7$

##  D Additional Analyses for Section 5.2

###  D.1 Analysis of Dolphins Network

The Dolphins network contained an undirected social network in a community
living off Doubtful Sound, New Zealand. This network is constructed from
frequent associations between $62$ nodes (dolphins) (Lusseau et al., 2003). It
has two communities.

Figure 8: The topological displays for the Dolphins network from SCORE,
SCORE+, and our SCOREH+ algorithms (8 is from the ground-truth of the
network).

For the Dolphins network, the results demonstrate that SCORE misclassified the
numbers $2$, $8$, $20$, $27$, $28$, and $40$ nodes, and SCORE+ made mistakes
on the numbers $8$ and $40$ nodes. Refer to Fig. 8, and our SCOREH+ perfectly
acquired the community structure.

###  D.2 Analysis of Polbooks Network

The Polbooks network contained books on American politics, published around
the 2004 presidential election and sold by Amazon.com. This data set was not
published, but we can access it on V. Krebs’ website
333http://www.orgnet.com/divided.html. In this network, the edges between
books represent that they were sold together. Typically, this network has two
communities. However, the network structure is difficult to discover since
“neutral” or “moderate” people can buy books promoting both parties. The
experiments by detecting communities from the constructed network also
demonstrate this viewpoint.

Figure 9: The topological displays for the Polbooks network from SCORE,
SCORE+, and our SCOREH+ algorithms (9 is from the ground-truth of the
network). The Polbooks network, like Dolphins and Karate, has two communities.

As shown in Fig. 9, both of the SCORE+ and SCOREH+ algorithms made mistakes on
the $50$ and $67$ nodes, whereas the SCORE misclassified only one node: the
$66$ node. However, it is this small one-node difference that improved the NMI
of the SCORE algorithm on this network, from $0.87$ to $0.924$.

##  E Additional Results for Section 5.3

###  E.1 Modularity Tables

Table 12: Numerical results on synthetic networks with N=2,000 and N=5,000
(Modularity)

No. | $\mu$ |  | N=2,000 |  |  | N=5,000 |  |  |
---|---|---|---|---|---|---|---|---|---
ASE | Louvain | Fast-Greedy | SC | SCORE | SCORE+ | SCOREH+ | ASE | Louvain | Fast-Greedy | SC | SCORE | SCORE+ | SCOREH+
$1$ | $0.15$ | $0.694$ | 0.698 | $0.675$ | $0.049(0.006)$ | $0.001(0.0)$ | 0.698(0.0) | 0.698(0.0) | $0.605$ | 0.712 | $0.681$ | $0.056(0.001)$ | $0.0(0.0)$ | 0.712(0.0) | 0.712(0.0)
$2$ | $0.25$ | $0.546$ | $0.55$ | $0.503$ | $0.013(0.002)$ | $0.0(0.0)$ | 0.55(0.0) | 0.55(0.0) | $0.457$ | 0.551 | $0.505$ | $0.025(0.001)$ | $0.0(0.0)$ | 0.551(0.0) | 0.551(0.0)
$3$ | $0.35$ | $0.372$ | 0.411 | $0.341$ | $-0.009(0.003)$ | $0.0(0.0)$ | 0.411(0.0) | 0.411(0.0) | $0.342$ | $0.418$ | $0.361$ | $0.006(0.001)$ | $0.0(0.0)$ | 0.422(0.0) | 0.422(0.0)
$4$ | $0.45$ | $0.215$ | 0.284 | $0.21$ | $-0.019(0.001)$ | $0.0(0.0)$ | $0.269(0.0)$ | $0.279(0.0)$ | $0.237$ | 0.293 | $0.227$ | $-0.009(0.001)$ | $0.0(0.0)$ | $0.284(0.0)$ | $0.287(0.002)$
$5$ | $0.55$ | $0.1$ | 0.18 | $0.141$ | $-0.026(0.001)$ | $0.0(0.0)$ | $0.126(0.008)$ | $0.156(0.001)$ | $0.12$ | 0.191 | $0.148$ | $-0.011(0.001)$ | $0.0(0.0)$ | $0.113(0.008)$ | $0.17(0.001)$
$6$ | $0.65$ | $0.045$ | 0.129 | $0.109$ | $-0.027(0.0)$ | $-0.0(0.0)$ | $0.044(0.003)$ | $0.095(0.001)$ | $0.047$ | 0.123 | $0.09$ | $-0.018(0.0)$ | $0.0(0.0)$ | $0.055(0.005)$ | $0.085(0.002)$
$7$ | $0.75$ | $0.011$ | 0.108 | $0.095$ | $-0.03(0.0)$ | $-0.0(0.0)$ | $0.016(0.003)$ | $0.069(0.001)$ | $0.01$ | 0.091 | $0.08$ | $-0.018(0.0)$ | $0.0(0.0)$ | $0.023(0.001)$ | $0.054(0.0)$
$8$ | $0.85$ | $0.001$ | 0.105 | $0.096$ | $-0.026(0.0)$ | $0.0(0.0)$ | $-0.004(0.002)$ | $0.059(0.001)$ | $-0.002$ | 0.084 | $0.075$ | $-0.02(0.0)$ | $-0.0(0.0)$ | $-0.002(0.001)$ | $0.041(0.0)$

Table 13: Numerical results on synthetic networks with N=8,000 and N=10,000
(Modularity)

No. | $\mu$ |  | N=8,000 |  |  | N=10,000 |  |  |
---|---|---|---|---|---|---|---|---|---
ASE | Louvain | Fast-Greedy | SC | SCORE | SCORE+ | SCOREH+ | ASE | Louvain | Fast-Greedy | SC | SCORE | SCORE+ | SCOREH+
$1$ | $0.15$ | $0.608$ | 0.71 | $0.686$ | $0.046(0.002)$ | $0.0(0.0)$ | 0.71(0.0) | 0.71(0.0) | $0.601$ | 0.718 | $0.694$ | $0.05(0.001)$ | $0.0(0.0)$ | 0.718(0.0) | 0.718(0.0)
$2$ | $0.25$ | $0.445$ | $0.562$ | $0.531$ | $0.031(0.0)$ | $0.0(0.0)$ | $0.495(0.0)$ | 0.563(0.0) | $0.459$ | 0.571 | $0.528$ | $0.03(0.001)$ | $0.0(0.0)$ | 0.571(0.0) | 0.571(0.0)
$3$ | $0.35$ | $0.324$ | $0.416$ | $0.365$ | $0.016(0.001)$ | $0.0(0.0)$ | $0.388(0.0)$ | 0.428(0.0) | $0.313$ | $0.424$ | $0.368$ | $0.017(0.001)$ | $0.0(0.0)$ | $0.329(0.0)$ | 0.425(0.0)
$4$ | $0.45$ | $0.233$ | 0.303 | $0.24$ | $0.004(0.0)$ | $0.0(0.0)$ | $0.249(0.001)$ | $0.302(0.003)$ | $0.23$ | 0.304 | $0.242$ | $0.003(0.001)$ | $0.0(0.0)$ | $0.228(0.0)$ | $0.297(0.0)$
$5$ | $0.55$ | $0.137$ | 0.194 | $0.142$ | $-0.009(0.0)$ | $-0.0(0.0)$ | $0.135(0.0)$ | $0.185(0.002)$ | $0.136$ | 0.204 | $0.144$ | $-0.007(0.0)$ | $0.0(0.0)$ | $0.105(0.003)$ | $0.185(0.003)$
$6$ | $0.65$ | $0.047$ | 0.118 | $0.09$ | $-0.014(0.0)$ | $0.0(0.0)$ | $0.047(0.004)$ | $0.082(0.003)$ | $0.058$ | 0.128 | $0.091$ | $-0.011(0.0)$ | $0.0(0.0)$ | $0.053(0.003)$ | $0.09(0.001)$
$7$ | $0.75$ | $0.002$ | 0.081 | $0.071$ | $-0.02(0.0)$ | $0.0(0.0)$ | $0.018(0.001)$ | $0.045(0.0)$ | $0.007$ | 0.08 | $0.067$ | $-0.019(0.0)$ | $0.0(0.0)$ | $0.02(0.0)$ | $0.044(0.0)$
$8$ | $0.85$ | $0$ | 0.077 | $0.068$ | $-0.016(0.0)$ | $0.0(0.0)$ | $0.006(0.0)$ | $0.036(0.0)$ | $-0.002$ | 0.079 | $0.066$ | $-0.016(0.0)$ | $-0.0(0.0)$ | $0.002(0.0)$ | $0.029(0.0)$

###  E.2 NMI Tables

Table 14: Numerical results on synthetic networks with N=2,000 and N=5,000
(NMI)

No. | $\mu$ |  | N=2,000 |  |  | N=5,000 |  |  |
---|---|---|---|---|---|---|---|---|---
ASE | Louvain | Fast-Greedy | SC | SCORE | SCORE+ | SCOREH+ | ASE | Louvain | Fast-Greedy | SC | SCORE | SCORE+ | SCOREH+
$1$ | $0.15$ | 1.0 | 1.0 | $0.903$ | $0.407(0.013)$ | $0.029(0.001)$ | 1.0(0.0) | 1.0(0.0) | $0.98$ | 1.0 | $0.883$ | $0.423(0.005)$ | $0.019(0.002)$ | 1.0(0.0) | 1.0(0.0)
$2$ | $0.25$ | 1.0 | 1.0 | $0.79$ | $0.296(0.005)$ | $0.024(0.001)$ | 1.0(0.0) | 1.0(0.0) | $0.973$ | $0.998$ | $0.754$ | $0.424(0.007)$ | $0.018(0.001)$ | 1.0(0.0) | 1.0(0.0)
$3$ | $0.35$ | $0.974$ | $0.972$ | $0.621$ | $0.207(0.005)$ | $0.023(0.001)$ | 0.996(0.0) | $0.993(0.0)$ | $0.955$ | $0.978$ | $0.66$ | $0.43(0.006)$ | $0.015(0.001)$ | 0.998(0.0) | $0.997(0.0)$
$4$ | $0.45$ | $0.879$ | $0.892$ | $0.41$ | $0.169(0.006)$ | $0.028(0.001)$ | $0.952(0.001)$ | 0.953(0.0) | $0.894$ | $0.915$ | $0.48$ | $0.314(0.008)$ | $0.012(0.001)$ | 0.969(0.0) | $0.966(0.003)$
$5$ | $0.55$ | 0.71 | $0.529$ | $0.228$ | $0.067(0.004)$ | $0.025(0.001)$ | $0.65(0.002)$ | $0.67(0.004)$ | $0.805$ | $0.622$ | $0.311$ | $0.234(0.006)$ | $0.018(0.001)$ | 0.848(0.003) | $0.842(0.006)$
$6$ | $0.65$ | 0.42 | $0.195$ | $0.088$ | $0.056(0.002)$ | $0.025(0.0)$ | $0.294(0.009)$ | $0.36(0.003)$ | $0.48$ | $0.316$ | $0.104$ | $0.057(0.002)$ | $0.015(0.001)$ | $0.482(0.002)$ | 0.502(0.007)
$7$ | $0.75$ | 0.132 | $0.035$ | $0.013$ | $0.044(0.002)$ | $0.026(0.002)$ | $0.104(0.006)$ | $0.127(0.005)$ | $0.18$ | $0.043$ | $0.03$ | $0.046(0.001)$ | $0.015(0.0)$ | $0.21(0.004)$ | 0.243(0.002)
$8$ | $0.85$ | $0.052$ | $0.017$ | $0.013$ | $0.07(0.004)$ | $0.032(0.001)$ | 0.072(0.002) | $0.064(0.003)$ | $0.033$ | $0.011$ | $0.005$ | $0.044(0.002)$ | $0.014(0.001)$ | 0.045(0.002) | $0.041(0.003)$

Table 15: Numerical results on synthetic networks with N=8,000 and N=10,000
(NMI)

No. | $\mu$ |  | N=8,000 |  |  | N=10,000 |  |  |
---|---|---|---|---|---|---|---|---|---
ASE | Louvain | Fast-Greedy | SC | SCORE | SCORE+ | SCOREH+ | ASE | Louvain | Fast-Greedy | SC | SCORE | SCORE+ | SCOREH+
$1$ | $0.15$ | $0.978$ | 1.0 | $0.872$ | $0.462(0.007)$ | $0.011(0.001)$ | 1.0(0.0) | 1.0(0.0) | $0.976$ | 1.0 | $0.851$ | $0.468(0.002)$ | $0.014(0.001)$ | 1.0(0.0) | 1.0(0.0)
$2$ | $0.25$ | $0.971$ | $0.985$ | $0.794$ | $0.439(0.008)$ | $0.011(0.0)$ | $0.979(0.0)$ | 0.999(0.0) | $0.969$ | $0.999$ | $0.77$ | $0.477(0.005)$ | $0.009(0.0)$ | 1.0(0.0) | $0.999(0.0)$
$3$ | $0.35$ | $0.955$ | $0.956$ | $0.635$ | $0.469(0.002)$ | $0.014(0.001)$ | $0.98(0.0)$ | 0.998(0.0) | $0.959$ | $0.978$ | $0.631$ | $0.448(0.003)$ | $0.013(0.001)$ | $0.965(0.0)$ | 0.995(0.0)
$4$ | $0.45$ | $0.943$ | $0.898$ | $0.508$ | $0.477(0.002)$ | $0.013(0.001)$ | $0.959(0.001)$ | 0.978(0.002) | $0.931$ | $0.936$ | $0.526$ | $0.479(0.001)$ | $0.01(0.0)$ | $0.947(0.001)$ | 0.975(0.001)
$5$ | $0.55$ | $0.866$ | $0.775$ | $0.344$ | $0.375(0.002)$ | $0.012(0.001)$ | $0.911(0.0)$ | 0.925(0.001) | $0.847$ | $0.739$ | $0.312$ | $0.402(0.001)$ | $0.012(0.0)$ | $0.874(0.001)$ | 0.905(0.001)
$6$ | $0.65$ | $0.483$ | $0.333$ | $0.118$ | $0.125(0.004)$ | $0.013(0.001)$ | 0.613(0.001) | $0.605(0.006)$ | $0.566$ | $0.379$ | $0.132$ | $0.208(0.011)$ | $0.012(0.0)$ | 0.699(0.001) | $0.657(0.005)$
$7$ | $0.75$ | $0.123$ | $0.025$ | $0.035$ | $0.026(0.001)$ | $0.01(0.0)$ | $0.186(0.002)$ | 0.22(0.001) | $0.176$ | $0.052$ | $0.02$ | $0.029(0.001)$ | $0.007(0.0)$ | $0.254(0.001)$ | 0.282(0.002)
$8$ | $0.85$ | $0.055$ | $0.015$ | $0.016$ | $0.047(0.001)$ | $0.012(0.001)$ | $0.122(0.002)$ | 0.129(0.002) | $0.056$ | $0.005$ | $0.005$ | $0.036(0.001)$ | $0.01(0.001)$ | $0.053(0.001)$ | 0.074(0.002)

###  E.3 Additional Figures for Section 5.3

Figure 10: The comparison plots of Modularity on LFR datasets with different
N.

Figure 11: The comparison plots of NMI on LFR datasets with different N.

Figure 12: The comparison plots of Modularity on LFR datasets with different
$\mu$.

Figure 13: The comparison plots of NMI on LFR datasets with different $\mu$.