An attribute-based community search method with graph refining
- PDF / 2,449,202 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 3 Downloads / 177 Views
An attribute-based community search method with graph refining Jingwen Shang1 · Chaokun Wang1 · Changping Wang1 · Gaoyang Guo1 · Jun Qian1
© Springer Science+Business Media New York 2017
Abstract In many complex networks, there exist diverse network topologies as well as node attributes. However, the state-of-the-art community search methods which aim to find out communities containing the query nodes only consider the network topology, but ignore the effect of node attributes. This may lead to the inaccuracy of the predicted communities. In this paper, we propose an attribute-based community search method with graph refining technique, called AGAR. First, we present the concepts of topology-based similarity and attribute-based similarity to construct a TA-graph. The TA-graph can reflect both the relations between nodes from the respect of the network topology and that of the node attributes. Then, we construct AttrTCP-index based on the structure of TA-graph. Finally, by querying the AttrTCP-index, we can find out the communities for the query nodes. Experimental results on real-world networks demonstrate AGAR is an effective and efficient community search method by considering both the network topology and node attributes. Keywords Community search · Graph refining · Node attributes · Network topology
B
Chaokun Wang [email protected] Jingwen Shang [email protected] Changping Wang [email protected] Gaoyang Guo [email protected] Jun Qian [email protected]
1
School of Software, Tsinghua University, Beijing 100084, China
123
J. Shang et al. Fig. 1 A graph containing three communities
b
f
a
c
e
g
d i
h
l
j k
1 Introduction The community structure is one of the most important characteristics of complex networks. Topologically, a community is a cohesive subgraph where nodes are densely connected, while nodes in different communities are sparsely connected. Generally, nodes in the same community tend to have common attributes or similar functions [12]. Community detection aims to find out all communities within an input network. It is an important research problem in the fields such as computer science, physics, biology and communication and has been studied a lot in last decades [12,23,25,28,36,39,40]. As an interesting counterpart, community search seeks to find the communities containing given objects, which has attracted much attention recently [8,31,32]. The main difference between these two tasks is that community detection targets all communities in the entire network according to a global criterion [12], while community search only focuses on the personalized communities for a query node or a group of query nodes [32]. In a network, as the communities for different nodes may have great differences, it is more meaningful to explore and study the user-centered personalized community search problem [16]. For example, by utilizing the general community detection method, the network in Fig. 1 can be divided into three communities surrounded b
Data Loading...
