Article Preview
Top1. Introduction
In the real world, many living systems can be represented by a complex network. It is very important to understand the living systems so as to design an artificial system. Some tools to analyze the complex network are useful to understand the living system.
A directed network is one of representation for the complex network, whose links have a flow and it can represent living systems such as a relation between neurons and synapses (White, Southgate, Thomson, & Brenner, 1986) in a neural network, predators and prays in food-web, pages and hyper-links in WWW (Albert, Jeong, & Barabasi, 1999), and users and followers in a social network service (Wakita & Tsurumi, 2007). Figure 1 shows a neural network as a sample of directed network. In the directed network, a degree distribution is divided into in-degree distribution and out-degree distribution. The connection of links complexly tangle very much, but once we have a mesoscopic point of view, they can be divided into some sets of nodes which are related deeply in itself and sparsely with others. Such a relation of the network is called “community structure” in network. According to recent researches, most of the living systems have such a structure in themselves and each community has a function (Arenas, Fernández, & Gómez, 2008). Finding the community structure is important to understand their roles and to find problems in them. To find the community structure in the network, there are two difficulties: (1) defining goodness of the community structure, and (2) exploring solution in a wide space. Modularity (Newman & Girvan, 2003) and its extensions (Reichardt & White, 2007; Lázár, Ábel, & Vicsek, 2010), are measures to solve first difficulty. Modularities are useful to find the natural number of communities. Because they depend on link density rather than the number of communities. To attack the second difficulty, there are many methods to extract the approximately optimized community structure (Newman & Girvan, 2003; Clauset, Newman, & Moore, 2004; Duch & Arenas, 2005; Arenas, Duch, Fernandez, & Gomez, 2007; Blondel, Guillaume, Lambiotte, & Lefebvre, 2008; Barber & Clark, 2009). In a directed network, if a node has some in-links, information comes from some modes linked with it, but if the node has some out-links, information coming out from it must be used in a different way. Thus, this asymmetric structure causes sending and receiving information functions. To understand the system function, it becomes necessary to classify nodes from two aspects. However, most of conventional modularities and community extraction methods can only apply to undirected networks. Conventional methods ignore their direction. They convert directed networks into undirected networks. The conventional methods do not extract the community structure as the set of nodes having many common successors or predecessors, but extract that as the set of nodes having many links in each community.
Figure 1. A neural network of a nematode C.elegans. Node represents neuron and link represents synapse between neurons. Arrow of link indicates the direction of signal.
In this paper, to discover sending and receiving functional modules, we propose a method to extract two community structures based on the direction of links in directed networks. To demonstrate the method, we apply the proposed method to the neural network of C.elegans (White, Southgate, Thomson, & Brenner, 1986).