부산대학교 도서관

In real-world networks, nodes are usually organized into modules or communities of densely connected nodes. In situations where nodes can belong to multiple communities we say that the communities overlap, and the nodes shared by more than one community are called the overlapping nodes. This occurs especially in social networks where an individual belongs to various social groups and organizations such as working circles, family, friendship or virtual groups on the Internet. Complex networks are known to have a heavy tail degree distribution. Indeed, they are organized with a vast majority of nodes with few interactions and a small set of highly connected nodes called hubs. In this paper, our goal is to study the relationship between the overlapping nodes and the hubs. Indeed, we suspect that the hubs are in the vicinity of the overlapping nodes. If this assumption is confirmed, it gives a new perspective on how the communities are organized and of the crucial importance of the overlapping nodes. In an attempt to investigate the ubiquity of this property, we perform series of experiments on various real-world networks with overlapping community structure. Results show that the hubs represent always a large proportion of the one-step neighbors of overlapping nodes. These results may have implications in various contexts. For example, searching for the hubs in large networks can be done starting from the overlapping nodes. Furthermore, this study may also provide new directions for designing new community detection algorithms.