Community Finding of Scale-Free Network: Algorithm and Evaluation Criterion - Mining Complex Data - page 210

13

Community Finding of Scale-Free Network:
Algorithm and Evaluation Criterion

Sen Qin 1 and Guanzhong Dai 2

1

School of Science, Hangzhou Dianzi University, No.1, Street No.2, Xiasha Higher
Education Zone, Hangzhou, Zhejiang, P.R. China, 310018
[e-mail]

2

College of Automation, Northwestern Polytechnical University, No.127, Youyi West
Road, Xi'an, Shaanxi, P.R. China, 710072
[e-mail]

Abstract. Recently, topology structures of many social, biological and technological
networks have been discovered to display a scale-free property. For a network, a com-
munity is a natural division of network nodes into groups in which there are more
links between nodes within the groups than to nodes outside of it. Many methods of
community finding have been proposed to seek a fast, feasible and reasonable partition
algorithm for the whole network nodes. In this chapter, we introduce the topology of
the network to evaluate the feasibility and correctness of a community finding algo-
rithm. A relationship between the rough number of communities and the magnitude of
the number of hub nodes in the network is given in detail firstly. Then, an algorithm
based on Laplace matrix spectral decomposition is proposed and its key technology,
threshold selection of Euclidean distance between nodes, is discussed. Based on the
scale-free topology of complex network, the evaluation criterion of community finding
algorithm including three conditions is obtained. Numerical results show that the algo-
rithm of community finding is an effective one and the evaluation criterion is feasible,
fast and easy to operate.

Keywords: Complex network; Community finding; Scale-free network; Algorithm;
Evaluation criterion.

13.1 Introduction

In the last several decades, although our capabilities of collecting and processing
data have been increasing rapidly, we are deluged and baed by various and
massive data, such as scientific data, financial data, etc. These complex data
are a great challenge to traditional methods of data mining [1]. However, we
should not be pessimistic since there are many new approaches to find the useful
information from these complex data. A new approach is to use complex network
theories to seek the common characteristic of these data [2]. For example, in the
WWW database, each webpage can be considered a node of network, and the
hyperlinks between webpages are the links of the network. Then we can obtain
the set of those very important nodes according to analysis of the network's