extfieldsofstudy:
Computer Science
Mathematics

text:
Good Illumination of Minimum Range

A point p is 1-well illuminated by a set F of n point lights if p lies in the interior of the convex hull of F. This concept corresponds to triangle-guarding or well-covering. In this paper we consider the illumination range of the light sources as a parameter to be optimized. First, we solve the problem of minimizing the light sources' illumination range to 1-well illuminate a given point p. We also compute a minimal set of light sources that 1-well illuminates p with minimum illumination range. Second, we solve the problem of minimizing the light sources' illumination range to 1-well illuminate all the points of a line segment with an O(n^2) algorithm. Finally, we give an O(n^2 log n) algorithm for preprocessing the data so that one can obtain the illumination range needed to 1-well illuminate a point of a line segment in O(log n) time. These results can be applied to solve problems of 1-well illuminating a trajectory by approaching it to a polygonal path.

Introduction and definitions
Visibility or illumination has been the main topic for a lot of different works but most of them cannot be applied to real life, since they deal with ideal concepts. For instance, light sources have some restrictions since they cannot illuminate an infinite region as their light naturally fades as the distance grows. As well as cameras or robot vision systems, both have severe visibility range restrictions because they cannot observe with sufficient detail far away objects. We present some of these illumination problems adding several restrictions to make them more realistic, each light source has a limited illumination range so their illuminated regions are delimited. We use a limited visibility definition due to Ntafos [13] as well as a new concept related to this type of problems, the t-good illumination due to Canales et. al [1,6]. This last concept tests the light sources' distribution in the plane. If they are somehow surrounding the object we want to illuminate, there is a big chance it is 1-well illuminated (1-good illumination is also known as △-guarding [14] or well-covering [9]). This paper is solely focused in an optimization problem related to limited 1-good illumination. We propose the linear algorithm MER-Point to calculate the Minimum Embracing Range (MER) of a point in the plane and it also solves the decision problem. We move on to the computation of the MER of a line segment. In order to do this, we propose an algorithm that takes advantage of the Parametric Search [10,11] and runs in O(n 2 ) time. Our last algorithm is the main result in this paper as it computes the E-Voronoi diagram [3] restricted to a line segment which allows us to obtain the illumination range needed to 1-well illuminate a query point of the line segment in O(log n) time.
Let F be a set of n light sources in the plane that we call sites. Each light source fi ∈ F has limited illumination range r > 0, this is, they can only illuminate objects that are within the circle centered at fi with radius r. As we only consider 1-good illumination, throughout this paper we will refer to it just as illumination. The first two problems minimize the light sources' range while illuminating certain objects (points and line segments). On the third one, we also try to answer efficiently which light source embraces any given point in a line segment, this is, we want to compute the E-Voronoi Diagram restricted to a line segment. The next definitions follow from the notation introduced by Chiu and Molchanov [8], where CH(F ) denotes the convex hull of the set F . Definition 1.1 A set of points F is called an embracing set for a point p in the plane if p lies in the interior of the CH(F ). Definition 1.2 A site fi ∈ F is an embracing site for p if p is an interior point of the convex hull formed by fi and by all the sites of F closer to p than fi.
Following this definition, there may be more than one embracing site for a point p. Since we are trying to minimize the light sources' illumination range, in fact, we are trying to compute the closest embracing site for point p (see Figure 1). The NNE-graph [8] consists of a set of vertices V where each vertex v ∈ V is connected to its first nearest neighbour, its second nearest neighbour, ..., until v is in the convex hull of its nearest neighbours. Chan et al. [7] present several algorithms to construct the NNE-graph. Figure 1: The light sources f 1 and f 5 are embracing sites for point p. The light source f 5 is the closest embracing site for p with illumination range r = d(p, f 5 ). Definition 1.3 Let F be a set of n light sources in the plane. We call Closest Embracing Triangle for a point p, CET(F, p), to a set of three light sources of F containing p in the interior of the triangle they define and where one of the three light sources is the closest embracing site for p.
Since the set of light sources is always F , CET(F, p) is shortened to CET(p) in this paper. Definition 1.4 ([6]) Let F be a set of n light sources in the plane. We say that a point p in the plane is t-well illuminated by F if every open half-plane containing p in its interior, contains at least t light sources of F illuminating p.
This definition tests the light sources' distribution in the plane so that the greater the number of light sources in every open half-plane containing the point p, the better the illumination of p. This concept can also be found under the name of △-guarding [14] or well-covering [9]. The motivation behind this definition is the fact that, in some applications, it is not sufficient to have one point illuminated but some neighbourhood of it [9].
is the shaded open area, so every point that lies inside it is 1-well illuminated by the light sources f 1 , f 2 and f 3 . (b) All the interior points of the CH(f 1 , Definition 1. 5 We say that a point p is 1-well illuminated by the light sources f1, f2 and f3 if p ∈ A E r (f1, f2, f3) for some range r > 0. Definition 1.6 Given a set F of n light sources, we call Minimum Embracing Range to the minimum range needed to 1-well illuminate a point p or a set of points S in the plane, respectively MER(F, p) or MER(F, S).
Since the set F is clear from the context, we will use "MER of a point p" instead of MER(F, p) and "MER of a set S" instead of MER(F, S). Once we have found the closest embracing site for a point, its MER is given by the distance between the point and its closest embracing site. So we know that a point is 1-well illuminated if all the light sources' illumination range is, at leat, the same value as MER. In the next section we focus on our solution to obtain the closest embracing site of F for a point p as well as one CET(p).

Minimum Embracing Range of a Point
Let F be a set of n light sources in the plane and p a point we want to 1-well illuminate. The objective of this section is to compute the value of the MER of p, rm, as well as one CET(p). The closest embracing site for p can be obtained in linear time using the NNE-graph by Chan et. al [7]. The algorithm we present in this section also has the same time complexity.
The MER-Point Algorithm First of all, we compute the distances from p to all the light sources. Afterwards, we compute the median of all the distances in linear time [4]. Depending on this value, we can split the light sources in two halves: the set Fc that contains the closest half to p and the set F f that contains the furthest half. We check whether p ∈ int(CH(Fc)), what is equivalent to test if Fc is an embracing set for p. If the answer is negative, we recurse adding the closest half in F f . Otherwise, we recurse halving Fc. This logarithmic search runs until we find the light source fp ∈ F and the subset F E ⊆ F such that p ∈ int(CH(F E )) but p / ∈ int(CH(F E \ {fp}). The light source fp is the closest embracing site for p and its MER is rm = d(fp, p).
On each recursion, we have to check whether p ∈ int(CH(F ′ )), F ′ ⊆ F . This can be done in linear time [12] if we choose carefully the set of points so that each point is studied only once. As soon as we have computed fp, we can find the two other vertices of a CET(p) in linear time as follows. Consider the circle centered at p of radius rm and the line pfp that splits the light sources inside the circle in two sets. Note that if fp is the closest embracing site for p then there is a semicircle empty of other light sources than fp. A CET(p) has fp and two other light sources in the circle as vertices. Actually, any pair of light sources f l , fr such that each lies on a different side of the line passing through p and fp verifies that p ∈ int(CH(f l , fp, fr)). Proof : Let F be a set of n light sources. The distances from p to all the light sources can be computed in linear time. Computing the median also takes linear time [4], as well as splitting F in two halves. Checking if p ∈ int(CH(F ′ )), F ′ ⊆ F , is linear on the number of light sources in F ′ . So the total time for this logarithmic search is O(n + n 2 + n 4 + n 8 + ...) = O(n). Therefore, we find the closest embracing site for p in linear time. So this algorithm computes the MER of p and a CET(p) in total O(n) time.
The decision problem is trivial after the MER of p is computed. Point p is 1-well illuminated if the given illumination range is greater or equal to the MER of p.

Minimum Embracing Range of a Line Segment
In this section we compute the MER, rm, of a line segment, this is, we compute the minimum illumination range needed to 1-well illuminate a line segment with a set of light sources. Without loss of generality, suppose that a line segment s = p l pr is an horizontal line segment and that p l and pr are respectively the leftmost and the rightmost points of s. Since our solution uses the Parametric Search technique due to Megiddo [10,11], we first concentrate on the following decision problem: given a range r > 0, is s 1-well illuminated by a set F of n light sources?
The algorithm in this section decides if a line segment s is 1-well illuminated knowing that the light sources of F have illumination range r. The idea behind this algorithm is to split s into several open segments and check if r is enough to 1-well illuminate all of them. We will show that, if two consecutive open segments are 1-well illuminated, the point in between also is. Hence, if all segments and both extreme points are 1-well illuminated, so is the segment s.
Let us first introduce some notation. We know that each light source fi ∈ F illuminates a circle centered at itself with radius r, C(fi, r), and that each circle can intersect s in at most two points. Since we have n light sources, there are n such circles and at most 2n intersection points between s and the circles. Let I be the set containing the points p l = i0 and pr = im and all the sorted intersection points according to their x-coordinate i1 . . . im−1.If i k is an intersection point between C(fi, r) and s, let f (i k ) be fi. If i k ∈ I is to the left (resp. right) of f (i k ), it is called the leftmost (rightmost) intersection point. Let also s k = (i k−1 , i k ), with i k−1 , i k ∈ I be the open segment between the intersection points i k−1 and i k , for k = 1, . . . , m. Note that the light sources illuminating s k are the same for all points in s k since its endpoints are consecutive intersections of I. The function F(s k ) returns the set of the light sources that illuminate s k ⊆ s with range r. Knowing that F(s1) = F(i0), the function is recursively defined for k = 1, . . . , m − 1 as follows.
In the Figure 3 there is an example of what happens when the intersection point i k ∈ I is the leftmost point or the rightmost point.
. Since both open segments are 1-well illuminated, i k must lie on the boundary of both convex hulls. Since, by definition of F(s k ), one of the two convex hulls is contained in the other, and both segments are inside the biggest one, i k is also contained. Hence, i k ∈ I is 1-well illuminated.
Proof : By definition of F(s k ), the segment s k is 1-well illuminated if it is interior to the convex hull of this set. Since this convex hull is obviously convex, the segment s k is 1-well illuminated when its endpoints are in the convex hull of F(s k ). Proof : Follows from Lemmas 3.1 and 3.2. An efficient algorithm to solve the Decision Problem is then the following: Check if i0 and im are 1-well illuminated using the MER-Point algorithm. For all k ∈ [1, . . . , m] we compute CH(F(s k )) by simply adding or deleting a point to CH(F(s k−1 )) and check whether s k is 1-well illuminated. If all checks are true, then s is 1-well illuminated; otherwise, it is not. Proposition 3.1 Given a real number r > 0, a set F of n light sources with limited illumination range r and a line segment s, the algorithm described above decides if s is 1-well illuminated by F in O(n log n) time.
Proof : Let F , be a set of n light sources with a limited illumination range r. Checking if p l and pr are 1-well illuminated is linear using the MER-Point algorithm. Sorting the points in I according to their x-coordinate takes O(n log n) time. Computing the set of light sources that illuminate p l is linear but constructing its convex hull takes O(n log n) time. Updating dynamically the convex hull every time we need to add or remove a light source can also be done in O(log n) (amortized) time [5], and checking if both i k−1 , i k are in the CH(F(s k )) takes O(log n) time. Since we have at most 2n intersection points and we spend O(log n) time on each one, this algorithm decides if s is 1-well illuminated by F with range r in O(n log n) time.
Note that this procedure still works when each light source has a different range. Instead of having n circles with the same radius, we have n circles with different radii. After computing the intersection points between the n circles and the line segment, the remaining procedure is exactly the same.

The Algorithm
We have an algorithm to decide if, given a range value, a line segment is 1-well illuminated. In order to compute the minimum range needed to 1-well illuminate the segment, we will apply the Parametric Search technique due to Megiddo [10,11].
Let F be a set of n light sources. Let g be a monotonic function (g(x) ≥ g(y) if x > y) with a root. We want to convert our problem in a monotonic root-finding problem since we have an efficient decision algorithm to solve it. Now we define the function g as follows: We know how to compute if s is 1-well illuminated using the decision algorithm just presented. Our goal to find the greatest root θ * = max{θ : g(θ) = 0} using the Parametric Search and once we have it, the MER of s is rm = 1 θ * . Since we solve the decision problem in O(n log n) time, we can find this root in O(n 2 log 2 n) time. An small improvement in performance can be achieved using the following parallel decision algorithm.  Proof : The sequential decision algorithm takes S(n) ∈ O(n log n) time while the one running in parallel requires T (n) ∈ O(log n) time when using P (n) ∈ O( n 2 log n ) processors. So the total time to evaluate the function g(θ) and finding its greatest root using the Parametric Search, as well as computing the MER of s, is O(S(n)T (n) log P (n)+T (n)P (n)) ∈ O(n log n×log n×log( n 2 log n )+log n× n 2 log n ) ∈ O(n 2 ) time.

The E-Voronoi Diagram Restricted to a Line Segment
In the previous section we have computed the minimum illumination range that a set of light sources must have in order to embrace all the points of a line segment. Now we go further and compute the closest embracing site for every point of the line segment which is equivalent to solve the problem of constructing the E-Voronoi diagram [3] restricted to a line segment s = p l pr. With this structure, it is possible to make a query in O(log n) time to know the minimum illumination range needed to embrace a point of s. As in the previous section, we will assume that s is an horizontal line segment and that p l and pr are respectively the leftmost and rightmost points of s. The next definition can be found under the previous name of MIR-Voronoi region (MIR-VR) [3]. The set of all the E-Voronoi regions is called the E-Voronoi diagram of F (formerly known as the MIR Voronoi Diagram [3]). An algorithm to compute the E-Voronoi diagram of F restricted to a segment s follows.
For each light source f ∈ F , we perform a sweep searching for the points of s that belong to the E-VR(f, F ). When the sweeping for f is done, we have computed all the components of the E-VR(f, F ) restricted to s (note that the E-Voronoi region of a light source is not always connected [3]). When the sweeping is done for all the light sources of F , we have computed the E-Voronoi diagram of F restricted to s.
Let us start computing the E-Voronoi region of a light source f ∈ F restricted to s. Let p f be the closest point on s to the source f . We will sweep from left to right (from p f to pr) and then from right to left (from p f to p l ). When we are moving along s, we change from one E-Voronoi region to another when the point has two closest embracing sites or the point reaches the border of the convex hull of its current closest embracing set. In the first case, this corresponds to the intersection between s and the perpendicular bisectors between the two closest embracing sites of the point. For that reason, we compute the intersection points between s and the perpendicular bisectors between the light sources in F \{f } and f . We keep these intersection points as well as p l , p f and pr sorted by the x-coordinate in two lists (one for each type of sweeping), L1 = {p f , . . . , pr} and L2 = {p f , . . . , p l }. The intersection points between s and the convex hull of the closest embracing set of a point will be added to this list during the sweeping. As the E-VR(f, F ) may not be connected, while sweeping s we might cross several of its components. So to catch up where each component starts or ends, we say that pi ∈ s is a starting (ending) point of the E-VR(f, F ) if it is the point where a component of the E-VR(f, F ) starts (ends). We will only explain the sweeping from left to right using the list L1 (the sweeping from right to left is a mirror of this one).
For each pi ∈ L1 starting on pi = p f , we compute the convex hull of all light sources inside the circle with radius d(f, pi). We use H(f, pi) for this hull. Note that f is on its boundary and call H * (f, pi) the obtained convex hull when deleting f (the two edges adjacent to f are called support lines). We will look for the points pi ∈ s such that pi ∈ int(H(f, pi)) but pi / ∈ int(H * (f, pi)), this is, the points pi ∈ s such that f is their closest embracing site. The following lemmas give the clues to the discretization of the sweeping.  Proof : Given a point pi ∈ L1 and the light source f ∈ F , let pi ∈ int(H * (f, pi)). At first, pi ∈ int(H * (f, pi)) might suggest that pi / ∈ E-VR(f, F ) but this may also suggest that we have just crossed a perpendicular bisector and now there is another light source in F that also 1-well illuminates pi. So if pi ∈ E-VR(f, F ) then pi has two closest embracing sites. This means that the last points on the left of pi are also in the same component of the E-VR(f, F ) as pi, but the points on its right are in a component of another E-Voronoi region. So pi is the ending point of a component of the E-VR(f, F ) restricted to s. Lemma 4.2 Given two consecutive points pi, pi+1 ∈ L1 and the light source f ∈ F , let pi ∈ int (H(f, pi)) but pi / ∈ int (H  *  (f, pi)). If one of the support lines intersects s between pi and pi+1 on si ∈ s, then [pi, si) is a segment contained in the E-VR(f, F ) restricted to s.
Proof : Given two consecutive points pi, pi+1 ∈ L1 and the light source f ∈ F , if pi ∈ int (H(f, pi)) and pi / ∈ int(H * (f, pi)) then it is clear that the point is 1-well illuminated by f so pi ∈ E-VR(f, F ). We know that between pi and pi+1 we do not cross any perpendicular bisector between f and the other light sources in F so if the E-VR(f, F ) ends before pi+1, that is because the set H(f, pi) is not an embracing set for all the points in the segment pipi+1. Let si ∈ s be the intersection point between s and one of the support lines, so the segment between pi and si is 1-well illuminated by the set H(f, pi) (see Figure 4(a)). On the other hand, sipi+1 / ∈ H(f, pi) so it is not 1-well illuminated by f . This means that [pi, si) is a segment contained in the E-Voronoi region of f restricted to s. Proof : Given two consecutive points pi, pi+1 ∈ L1 and the light source f ∈ F , if pi ∈ int (H(f, pi)) and pi / ∈ int(H * (f, pi)) then pi ∈ E-VR(f, F ). If H * (f, pi) intersects s between pi and pi+1 then H(f, pi) is not an embracing set for the whole segment pipi+1 (see Figure 4   time. This is also the (amortized) time spent on dynamically updating the convex hull [5]. So the sweeping for each light source takes O(n log n) time and it computes the restricted E-Voronoi region of the light source we are studying at the moment. Since we have n light sources, the algorithm computes the E-Voronoi diagram of F restricted to s in O(n 2 log n) time.
Using this algorithm, we compute E-Voronoi diagram of F restricted to s and we can also compute the MER of s using the following proposition. This technique takes O(n 2 log n) time but it is simpler than the one presented in the previous section.
Proposition 4.1 Let s be a line segment and F a set of n light sources. The MER of s is given by the biggest distance between a light source f ∈ F and one of the extremes of its E-Voronoi region restricted to s.
Proof : Given a line segment s, the MER of s is the biggest distance between a point of s and its closest embracing site. By definition, a point is in the E-Voronoi region of f ∈ F if f is its closest embracing site. If we compute the biggest distance between a light source f and a point of s in its E-Voronoi region, we get the minimum illumination range needed to 1-well illuminate all the points in the E-VR(f, F ) restricted to s. Let t be the intersection between s and the E-VR(f, F ) and pi be an interior point of t. Assume that p f ∈ t (see Figure 5(a)), since p f is the closest point of t to f , the distance between pi and f increases when we are moving away from p f along t. So the minimum illumination range needed to 1-well illuminate t is the biggest distance between one of its extreme points and f . Now suppose that p f / ∈ t (see Figure 5(b)), this means that the distance d(f, pi) increases if we move pi towards one of the extremes of t and decreases towards the other end. Again, the biggest distance between f and a point of t is the distance between one of its extremes and f . As each light source f ∈ F has a minimum illumination range that can be computed by the distance between f and one of the extremes of its E-Voronoi region restricted to s, the biggest of these minimum illumination ranges is the MER of s.
The most interesting consequence of this algorithm is the following. Proof : Let F be a set of n light sources and s a line segment. We can compute the E-Voronoi diagram of F restricted to s in O(n 2 log n) time using the algorithm described above. This preprocess allows us to have a structure that localizes a point q ∈ s in O(log n) time. Once the point is located, t l t r t l s s p f Figure 5: (a) The E-Voronoi region of f ∈ F is the gray area, d(f, t l ) is the biggest distance between f and a point of t, d(f, p i ) ≤ d(f, t l ), p i ∈ t l t r . (b) For a point p i ∈ t l t r , d(f, p i ) ≤ d(f, t r ) and the latter is the minimum illumination range needed to 1-well illuminate t.
we know what is the E-Voronoi region that it belongs to, this is, we know what is the closest embracing site for q. The MER of q is given by the distance between q and its closest embracing site.
This algorithm and the one in the previous section are also useful when we want to compute the MER to 1-well illuminate a trajectory or a polygonal line. We can decompose the trajectory in several line segments and apply one of the algorithms to each part. This way, we compute a range for each piece and the greatest range of them all is the MER of the whole polygonal line or trajectory. An algorithm that shows how to compute all the different Closest Embracing Triangles for a line segment and their ranges can be found in [2].

Conclusions
The visibility problems solved in this paper consider n light sources. We presented the linear algorithm MER-Point for computing a CET(p) and its MER. This algorithm can also be used to decide if a point in the plane is 1-well illuminated. We also presented a quadratic algorithm to compute the MER of a line segment in the plane using the Parametric Search. Concerning the main subject in this paper, we presented another algorithm that computes the E-Voronoi diagram restricted to a line segment, as well as its MER. Both algorithms can also be extended to compute the MER of either open or closed polygonal lines.


extfieldsofstudy: Medicine Biology Mathematics

text:
Dynamic behaviors in directed networks

Motivated by the abundance of directed synaptic couplings in a real biological neuronal network, we investigate the synchronization behavior of the Hodgkin-Huxley model in a directed network. We start from the standard model of the Watts-Strogatz undirected network and then change undirected edges to directed arcs with a given probability, still preserving the connectivity of the network. A generalized clustering coefficient for directed networks is defined and used to investigate the interplay between the synchronization behavior and underlying structural properties of directed networks. We observe that the directedness of complex networks plays an important role in emerging dynamical behaviors, which is also confirmed by a numerical study of the sociological game theoretic voter model on directed networks.

Motivated by the abundance of directed synaptic couplings in a real biological neuronal network, we investigate the synchronization behavior of the Hodgkin-Huxley model in a directed network. We start from the standard model of the Watts-Strogatz undirected network and then change undirected edges to directed arcs with a given probability, still preserving the connectivity of the network. A generalized clustering coefficient for directed networks is defined and used to investigate the interplay between the synchronization behavior and underlying structural properties of directed networks. We observe that the directedness of complex networks plays an important role in emerging dynamical behaviors, which is also confirmed by a numerical study of the sociological game theoretic voter model on directed networks. Research of complex systems which brings complex networks into focus has been an intensive and successful area in physics and other disciplines [1,2]. Within the complex network research community, dynamic behaviors in complex networks have been drawn much attention. Among a variety of collective dynamic behaviors, synchronization is the one of the most popular research topics [3][4][5], and it has been shown that the connection topology of complex networks greatly influences the degree of synchronization [2,6]. Recently, the question of how to increase the synchronizability via weighted and asymmetric couplings has been pursued intensively [7]. Especially, it has been shown that the synchronization is enhanced significantly when the couplings from old to young vertices are more abundant than from young to old, indicating the importance of the directedness of complex networks [8]. As a good and real example of synchronization, the synchronous firing of action potential in neuronal networks has been studied [9]. In [10], the Hodgkin-Huxley (HH) model [11] has been simulated on the Watts-Strogatz network [12], which has revealed that the underlying smallworld network structure enhances synchronization substantially. Different from real biological neuronal networks, where synaptic couplings connecting two neurons are naturally directed, it has been assumed that the synaptic couplings are undirected. In contrast, the neuronal network of the nematode Caenorhabditis elegans (C. elegans) has been analyzed and 90% of synaptic couplings have been shown to be directed [13]. In other words, only 10% of synaptic couplings are bidirectional.
In the present paper, we fully consider the directions of edges and investigate in a systematic way how the directedness of complex networks changes collective dynamical behaviors. Both the HH model in biology and the sociological voter model are studied on directed model networks, and it is unanimously found that as the more bidirectional edges are changed to unidirectional ones the system as a whole exhibits a worse ordering behavior. We believe that the conclusion should hold in a variety of different natural and social systems since the sparser bidirectional edges are the less efficient the information flow becomes.
The directed small-world network in the present study is constructed as follows: (1) The Watts-Strogatz undirected network is first built in the same way as in [12]. In detail, starting from the locally connected network of one-dimensional lattice with the connection range 15 corresponding to the average degree K = 30, each edge is picked and then randomly rewired with the probability P to other randomly chosen vertex. The size N of the network is defined as the total number of vertices and we use N = 400 below. (2) Each edge built above has both directions, one incoming and the other outgoing, and thus we substitute each undirected edge as two arcs with opposite directions (we in this work call a directed edge as an arc). Each pair of arcs is visited one by one, and then with the probability α, the direction of randomly chosen one arc in the given pair is reversed. It should be noted that the network resulting from the above procedure is a directed network and double links connecting the same two vertices are also allowed. We believe that double edges exist not only in a biological neuronal network, where two neurons can have two synaptic couplings, but also in a sociological network, where two individuals can have two different ways of information transfer. In the viewpoint of dynamics in this work, the two arcs connecting the same two vertices are equivalent to one arc with double weights. Consequently, the resulting network from the above procedure is a directed network with double arcs allowed (or double weights allowed), characterized by two parameters P and α. When α = 0, the network is identical to the WS undirected network, whereas for the other limiting case of α = 1, all edges in the network become directed. By changing the parameter α from zero to unity, one can systematically change the density of directed edges, while still preserving the average degree K (both the number of arcs per vertex and the number of directly attached vertices per vertex are conserved). It should be noted that if directions of arcs are not taken into account the directed network at any α has the exactly the same structure as the undirected one.
We first investigate structural properties of our directed network and measure the characteristic path length and the clustering coefficient. The former, denoted as l and defined by Definition of the influence σ of a triad. We define n i for the vertex i as the number of vertices which can get a message from is also counted. In (a), i can send its message both to j and k and we assign the number n i = 2 for i; n j = 1, n k = 0 are similarly assigned. In (b), n i = n j = n k = 2, since, e.g., j can send message to k and then can get it back from k. In (c), n i = n j = n k = 3 since everyone gets a message from everyone. The influence σ for a given triad (i, j, k) is defined as σ = (n i + n j + n k )/9.
necting vertices i and j, is computed in the same way as for an undirected network [14]. The shortest paths should be computed with the direction taken into account, and accordingly, d i j d ji for a directed network. The clustering coefficient for an undirected network has usually been defined as [12] where E i is the number of edges in the set of neighbors of the vertex i. If all neighbor vertices of i (with the degree k i ) are connected to each other, E i = k i (k i − 1)/2 and thus C (0) i = 1. For a directed network, however, the above definition of the clustering coefficient needs to be changed. In this paper, a quantity σ a (we call it the influence) is defined for the triad a composed of three vertices a = (i, j, k) as follows: (1) Count the number n i of vertices (including itself) who can get a message from i. For example, in Fig. 1(a), i can send its message to j and k, and thus we assign n i = 2. In the same way, n j = 1 and n k = 0 are obtained in Fig. 1(a). On the other hand, in Fig. 1(b), n j = 2 is assigned since j can send a message to k and then get it back from k. In Fig. 1(c), n i = n j = n k = 3 since a message from anyone will be eventually delivered to everyone. (2) Since n i ≤ 3, we normalize to obtain σ a=(i, j,k) ≡ (n i + n j + n k )/9 so that 0 ≤ σ a=(i, j,k) ≤ 1. In Fig. 1, (a) σ = (2+1+0)/9 = 1/3, (b) σ = (2+2+2)/9 = 2/3, and (c) σ = (3+3+3)/9 = 1, are found, respectively. Although the examples of triad connections in Fig. 1 have an identical number of arcs (six arcs), it is clear that the standard definition of the clustering coefficient cannot capture the difference. We define the clustering coefficient C (d) for a directed network as Note that P is in a log scale while α is not in (b). As P is increased, both l and C (d) are found to decrease consistent with [12]. When P = 10 −2 ∼ 10 −1 , the network has short path length together with large degree of clustering, manifesting the small-world behavior. As more edges become directed arcs, i.e., as α is increased, l becomes larger while C (d) becomes smaller, weakening the small-world behavior. The network of the size N = 400 at the average degree K = 30 has been used.
where a = 1, 2, · · · , E i is the index for triads connected to the vertex i, and σ a is the influence defined above and shown in Fig. 1. Since 0 ≤ σ a ≤ 1, we get a σ a ≤ E i and consequently Figure 2 displays (a) l(P, α) and C (d) (P, α) as density plots. At a fixed value of α, the increase of P results in smaller l and C (d) , consistent with the result for the undirected network in [12] corresponding to α = 0. The intermediate region of P has short characteristic path length but with a relatively high degree of clustering, manifesting the so called small-world behavior [12]. In contrast, as the network has more directed arcs (i.e., as α is increased), the small-world behavior becomes weaker: The path length is increased and the clustering coefficient becomes smaller. The structural changes related with the changing bidirectional edges to unidirectional arcs are naturally expected to be reflected in dynamic properties of the system on networks. As more edges are changed to directed arcs, the path connecting two vertices become longer, and the spread of information within local neighbors become less efficient. We believe that our generalization of the clustering coefficient to capture the difference between directed and undirected networks can be very useful in similar studies. In Ref. [15], a vector called the triad census has been proposed to measure the frequencies of 16 isomorphism classes of all possible directed coupling structures of three vertices. Among them seven correspond to complete 3-graphs like in Fig. 1. Although it should be possible to use the concept of the triad census [15] to characterize the clustering property of directed networks, we believe that our suggestion of the clustering coefficient is practically much more useful and convenient.
In order to study the effect of directedness of networks on dynamic cooperative behaviors in detail, we first study the Hodgkin-Huxley (HH) model in neuroscience on the directed network structure built as described above. The HH model is the one of the most representative models describing dynamics of a neuronal system. Originally, based on the result of physiological experiments of neural system of a squid, the HH model equations have been proposed to describe the membrane action potential [11,16,17]. In the present work, we use the HH coupled differential equations in [10] but with parameters obtained from physiological experiments of neurons in the part CA3 in hippocampus which plays an important role in learning and memory [18]. In detail, the membrane capacitance per unit area C m =1.0µF/cm 2 and the external current density I e =0.9µA/cm 2 are used, and maximum conductances for the leakage channel, the sodium, and the potassium ionic channels, are g L =0.15Ω −1 /cm 2 , g Na =50.0Ω −1 /cm 2 , g K =10.0Ω −1 /cm 2 , respectively (see [10] for HH coupled equations). The synaptic current between presynaptic and postsynaptic neurons is treated in the same way as in [10]. In this work, a direct current is injected into 40(= N/10) contiguous neurons between the onset (100msec) and the offset (1000msec) times, and the 6th-order Runge-Kutta method with the time step ∆t = 0.01msec is used to integrate HH equations. In order to get better statistics, 500 independent runs are performed and then averaged over different network realizations.
We below use the synchronization order parameter in [3,5] to study the interplay between the dynamic synchronization behavior and the underlying directed network structure. We denote t i,n as the nth firing time of the neuron i, and define the corresponding phase variable θ i (t) as via the simplification that θ(t) (t i,n−1 ≤ t ≤ t i,n ) increases linearly from 0 to 2π between the two successive firings at t i,n−1 and t i,n . The synchronization order parameter is then defined as where · · · represents the time average after achieving a steady state, and N fire is the number of neurons which fired at least twice [otherwise θ(t) is not defined]. For convenience, we have not included winding number term in Eq. (3); it does not change the value of ∆. In Fig. 3, we compare (a) the structural small-world property and (b) the dynamic synchronization behavior. In order to measure the former in Fig. 3(a), we normalize the clustering coefficient and the characteristic path length and then compute the difference, i.e., β ≡ C (d) (P, α)/C (d) (0, 0) − l(P, α)/l(0, 0). If β has a sufficiently large value, the network has a relatively large clustering coefficient and a relatively short path length, corresponding to the small-world region in [12]. It is clearly displayed in Fig. 3(a), that as either P or α is increased, the network begins to exhibit the small-world property, which is destroyed eventually when P or α is increased further. The structural importance of the directedness of networks is easily seen here: As more and more edges are changed to directed arcs, the network loses the small-world property. In Fig. 3(b),  we show the synchronization order parameter ∆ in Eq. (4) in the α-P plane. Although the region with large ∆ values is much smaller than the region with the small-world behavior in Fig. 3(a), it is unambiguously shown that the existence of directed arcs prohibits the system from being better synchronized. We believe that if one neglects the directedness of networks in the study of structural and dynamic properties of networks, the results should be taken cautiously. Especially, for a study of neuronal networks, in which much more synaptic couplings are directed than undirected, the conclusion reached by using an undirected network may change significantly if one takes the direction of synaptic couplings into full account. We next study a sociological game theoretic model called the voter model [19], defined on a directed network, to check the generality of our conclusion drawn above for a biological system. In the voter model, the ith player can have two different opinions σ i = ±1, and the time evolution of σ i (t) is described as follows: (1) Pick one voter (call her i) in the net-work randomly. (2) Pick another voter (call her j) randomly among i's incoming neighbors. (3) The voter i changes her opinion to the j's one, i.e., σ i (t + 1) = σ j (t). The directedness of a given network enters through the step (2) above: Each voter is influenced only by her neighbor voters connected by incoming arcs. We use the random initial condition to start with, and as time proceeds, the system approaches one of two absorbing states characterized by a perfect ordering, i.e., σ i = 1 or σ i = −1 for all i. In previous studies of voter models, the active bond is defined as the one connecting two voters with different opinions, and the key quantity to measure is the fraction ρ of active bonds given by where Λ (in) i is the set of incoming neighbors of i, and the in- The active bond has different signs of the opinion σ i σ j = −1, and consequently (1−σ i σ j )/2 takes the value either 1 or 0, depending on the activity of the bond.
In Fig. 4, the time evolution of ρ is shown for various values of α at the rewiring probability P = 0.1 for the directed network of the size N = 400 with the average degree K = 30. It is displayed that as α is increased the convergence of opinions, i.e., ρ → 0, takes longer time, and eventually becomes impossible for large enough values of α. This observation, in parallel to the above finding of the weaker synchronizability of the HH model on directed networks, implies that the existence of directed arcs inhibits an efficient flow of information, making global collective behaviors less plausible to occur.
In conclusion, we have studied dynamic behaviors of the biological neuron model and the sociological voter model on directed networks, built from the standard network model of Watts and Strogatz by changing undirected edges to directed arcs with the probability α. In the process of making directed networks numbers of connected vertices and arcs are not changed, and the characteristic path length does not change significantly in a broad range of α; this suggests that the connectivity is not altered much from the undirected counterpart. Unanimously found is that as the network becomes more directed by the increment of α, a global emergence of collective behaviors (the synchronization in the former and the opinion convergence in the latter models) becomes harder to develop. An extended definition of the clustering coefficient for directed networks has also been suggested, and the dynamic behaviors have been studied in relation with the network structures, captured by the characteristic path length and the clustering coefficient. However, we note that the region of the structural small-world behavior in Fig. 3 (a) and the region of the enhanced synchronizability in Fig. 3 (b) do not overlap completely. The origin of this discrepancy is not clear at present and needs further study in the future. We believe that our conclusion of decreased synchronizability of directed networks is very general beyond the model systems studied in this work and that the neglect of the directions of edges in network studies needs to be done very carefully. B.J.K. was supported by grant No. R01-2005-000-10199-0 from the Basic Research Program of the Korea Science and Engineering Foundation. S.M.P. acknowledges the support from Gu-Won research fund in Ajou University.