text:
# Local Search in Unstructured Networks

## I Introduction

Recently, studies of networks in a wide variety of fields, from biology to social science to computer science, have revealed some commonalities . It has become clear that the simplest classical model of random networks, the Erdos-Renyi model , is inadequate for describing the topology of many naturally occurring networks. These diverse networks are more accurately described by power-law or scale-free link distributions. In these highly skewed distributions, the probability that a node has $`k`$ links is approximately proportional to $`1/k^\tau `$. The link graph of the World Wide Web , the Internet router backbone , certain representations of biological pathways , and some social networks , each have approximately power-law distributions, in contrast to the Poisson distribution consistent with the Erdos-Renyi random graph model.

In addition to the characterization of the topological structure of these networks, other important questions concerning the growth, robustness, and dynamics on such networks have been addressed. For example, the question of what dynamical models of graph growth tend to generate power-law networks has been investigated , as well as their robustness with respect to error and attack .

Another important dynamical question is the behavior of local search strategies on networks. Much of the recent work on networks has been motivated by the ”small world” phenomenon, in which even very large networks (possibly possessing local clustering or structure) have very short diameters. Here the diameter is defined as the average shortest path length between the nodes in the network. The existence of this phenomenon has been demonstrated in different kinds of networks , and the property of short paths is obviously important for dynamic models such as disease spreading  and message passing between arbitrary nodes in a network.

The classic social experiment of Milgram  found that people could find a short chain of acquaintances in order to pass a message to each other, a phenomenon often referred to as ”six degrees of separation”. This result was surprising given that most people’s interactions tend to be tied to their local communities, with relatively few longer range connections. Watts and Strogatz  revitalized interest in the small-world problem by showing that even in highly structured and clustered graphs, a few long range connections dramatically reduce the average shortest path length between nodes.

It is however another question how exactly participants in a Milgram-style experiment might find these short paths, since they do not have global knowledge of the whole graph. That is, even if short paths exist, how can one (approximately) find them using local information? Kleinberg  considered this question for a lattice topology with distance dependent shortcuts and found an elegant characterization of the conditions under which it is possible to pass messages efficiently. Kleinberg assumed a very structured topology and considered algorithms which use the target’s position on a regular 2-D lattice to direct the search.

While the question of local search in real social networks is an intriguing one, it also relates in an interesting way to recent developments in information technology. The internet and the World Wide Web have certainly had an impact on the way that millions of people all over the world communicate, affecting the structure and dynamics of what we think of as traditional social networks . These ever more ubiquitous technologies, wired and wireless, tend to make geography and distance less relevant for communication between people.

But the relationship is also bi-directional. A social network is also a metaphor that is relevant for understanding popular internet technologies such as peer-to-peer (p2p) file-sharing networks. These networks share some of the topological features of social networks. The Gnutella system connects users computers directly with others to share files, without a central point of coordination. In such networks, the name of the target file may be known, but due to the network’s ad hoc nature, until a real-time search is performed the node holding the file is not known. In order to find files on the system, peers pass messages along to the other peers that they know of. In contrast to the scenario considered by Kleinberg, there is no global information about the position of the target, and hence it is not possible to determine whether a step is a move towards or away from the target.

These networks, while not centrally planned in structure, grow according to a simple self-organizing process. Recent measurements of Gnutella  and simulated Freenet networks  show that they have power-law degree distributions. The resulting highly unstructured networks need efficient search algorithms in order to function well. These algorithms should rely on local information in order to avoid a dependence on a central point of failure, and to accommodate their dynamic nature.

In this chapter, we will discuss a number of message-passing algorithms that can be efficiently used to search through power-law networks. We will discuss relevant work from both the statistical physics community as well as the computer science community. Most of these algorithms are meant to be improvements for peer-to-peer file sharing systems, and some may also shed some light on how unstructured social networks with certain topologies might function relatively efficiently with local information. Like the networks that they are designed for, these algorithms are completely decentralized, and they exploit the power-law link distribution in the node degree. The algorithms use local information such as the identities and connectedness of their neighbors, and their neighbors’ neighbors, but not the target’s global position. We demonstrate that some of these search algorithms can work well on real Gnutella networks, scale sub-linearly with the number of nodes, and may help reduce the network search traffic that tends to cripple such networks.

The chapter is organized as follows. Sections II, III, IV, and V review results from Adamic et al. regarding localized search. Sections II and III present analytical and simulation results, section IV compares search in Poisson random graphs and section V describes the application of the algorithms to Gnutella. Section VI examines the length of the paths found in search, section VII looks into shortest paths in power-law graphs, while section VIII examines search strategies based on information learned about the network, and section IX concludes.

## II Search in power-law random graphs

### A Intuition

The local search strategies we will be discussing use the intuition that connections tend to be disproportionately distributed among nodes and that the well-connected nodes should provide access to a greater portion of the network. In figures 1 and 2 we compare a sample walk on a standard random graph with a Poisson degree distribution and a power-law graph with the same number of nodes and edges. We plot the number of nodes accessible as a message is passed through two graphs, starting at a random node and proceeding toward the next most highly connected neighbor. Since each node has knowledge of its neighbors, we count reaching a node as finding all of its previously undiscovered neighbors.

The search on the power-law graph finds 30 nodes in 4 steps, while the same approach on the Poisson graph finds only 14 nodes in spite of the initial node having higher degree. Even though the two graphs have the same total number of edges, the distribution of edges allows one to search the power-law graph more rapidly, using only local information.

In following section we will follow up on this intuition and use the generating function formalism introduced by Newman et al.  for graphs with arbitrary degree distributions to analytically characterize search-cost scaling in graphs.

### B Random walk search

First we examine the number of nodes encountered in a random walk on the graph. Let $`G_0(x)`$ be the generating function for the distribution of the vertex degree $`k`$. Then

$$G_0(x)=\underset{0}{\overset{\mathrm{}}{}}p_kx^k$$
(1)
where $`p_k`$ is the probability that a randomly chosen vertex on the graph has degree $`k`$.

For a graph with a power-law distribution with exponent $`\tau `$, minimum degree $`k=1`$ and an abrupt cutoff at $`m=k_{max}`$, the generating function is given by

$$G_0(x)=c\underset{1}{\overset{m}{}}k^\tau x^k$$
(2)
with $`c`$ a normalization constant which depends on $`m`$ and $`\tau `$ to satisfy the normalization requirement

$$G_0(1)=c\underset{1}{\overset{m}{}}k^\tau =1$$
(3)
The average degree of a randomly chosen vertex is given by

$$z_1=<k>=\underset{1}{\overset{m}{}}kp_k=G_0^{}(1)$$
(4)
Note that the average degree of a vertex chosen at random and one arrived at by following a random edge are different. A random edge arrives at a vertex with probability proportional to the degree of the vertex, i.e. $`p^{}(k)kp_k`$. The correctly normalized distribution is given by

$$\frac{_kkp_kx^k}{_kkp_k}=x\frac{G_0^{}(x)}{G_0^{}(1)}$$
(5)
If we want to count the number of outgoing edges from the vertex we arrived at, but not include the edge we just came on, we need to divide by one power of $`x`$. Hence the number of new neighbors encountered on each step of a random walk is given by the generating function

$$G_1(x)=\frac{G_0^{}(x)}{G_0^{}(1)}$$
(6)
where $`G_0^{}(1)`$ is the average degree of a randomly chosen vertex as mentioned previously.

Since we are concerned with local search algorithms, we make the reasonable assumption that nodes may have at least some knowledge of their neighboring nodes’ neighbors. Hence, we now compute the distribution of second neighbors. The probability that any of the 2nd neighbors connects to any of the first neighbors or to one another goes as $`N^1`$ and can be ignored in the limit of large $`N`$. Therefore, the distribution of the second neighbors of the original randomly chosen vertex is determined by

$$\underset{k}{}p_k[G_1(x)]^k=G_0(G_1(x))$$
(7)
It follows that the average number of second neighbors is given by

$$z_{2A}=[\frac{}{x}G_0(G_1(x))]_{x=1}=G_0^{}(1)G_1^{}(1)$$
(8)
Similarly, if the original vertex was not chosen at random, but arrived at by following a random edge, then the number of second neighbors would be given by

$$z_{2B}=[\frac{}{x}G_1(G_1(x))]_{x=1}=[G_1^{}(1)]^2$$
(9)
In both Equation 8 and Equation 9, the fact that $`G_1(1)=1`$ was used. Both these expressions depend on the values $`G_0^{}(1)`$ and $`G_1^{}(1)`$ so we calculate those for given $`\tau `$ and $`m`$. For simplicity and relevance to most real-world networks of interest we assume $`2<\tau <3`$.

$$G_0^{}(1)=\underset{1}{\overset{m}{}}ck^{1\tau }_1^mx^{\tau 1}𝑑x=\frac{1}{\tau 2}(1m^{2\tau })$$
(10)
$`G_1^{}(1)`$ $`=`$ $`{\displaystyle \frac{1}{G_0^{}(1)}}{\displaystyle \frac{}{x}}{\displaystyle \underset{1}{\overset{m}{}}}ck^{1\tau }x^{k1}`$ (11)
$`=`$ $`{\displaystyle \frac{1}{G_0^{}(1)}}{\displaystyle \underset{2}{\overset{m}{}}}ck^{1\tau }(k1)x^{k2}`$ (12)
$``$ $`{\displaystyle \frac{1}{G_0^{}(1)}}{\displaystyle \frac{m^{3\tau }(\tau 2)2^{2\tau }(\tau 1)+m^{2\tau }(3\tau )}{(\tau 2)(3\tau )}}`$ (13)
for large cutoff values $`m`$. Now we impose the cutoff of Aiello et al.  at $`mN^{1/\tau }`$. The cutoff is chosen so that in an non-truncated distribution the expected number of nodes among $`N`$ having exactly the cutoff degree is 1. No nodes of degree higher than the cutoff are present in the graph. In real world graphs one does frequently observe nodes of degree higher than this imposed cutoff, so that our calculations describe a worse case scenario. Since $`m`$ scales with the size of the graph $`N`$ and for $`2<\tau <3`$ the exponent $`2\tau `$ is negative, we can neglect terms constant in $`m`$. This leaves

$$G_1^{}(1)=\frac{1}{G_0^{}(1)}\frac{m^{3\tau }}{(3\tau )}$$
(14)
Substituting into Equation 8 (the starting node is chosen at random) we obtain

$$z_{2A}=G_0^{}(1)G_1^{}(1)m^{3\tau }$$
(15)
We can also derive $`z_{2B}`$, the number of 2nd neighbors encountered as one is doing a random walk on the graph.

$$z_{2B}=[G_1^{}(1)]^2=[\frac{\tau 2}{1m^{2\tau }}\frac{m^{3\tau }}{3\tau }]^2$$
(16)
Letting $`mN^{1/\tau }`$ as above, we obtain

$$z_{2B}N^{2(\frac{3}{\tau }1)}$$
(17)
Thus, as the random walk along edges proceeds node to node, each node reveals more of the graph since it has information not only about itself, but also of its neighborhood. The search cost $`s`$ is defined as the number of steps until approximately the whole graph is revealed so that $`sN/z_{2B}`$, or

$$sN^{3(12/\tau )}$$
(18)
In the limit $`\tau 2`$, equation 16 becomes

$$z_{2B}\frac{N}{ln^2(N)}$$
(19)
and the scaling of the number of steps required is

$$sln^2(N)$$
(20)
### C Search utilizing high degree nodes

Random walks in power-law networks naturally gravitate towards the high degree nodes, but an even better scaling is achieved by intentionally selecting high degree nodes. For $`\tau `$ sufficiently close to $`2`$ one can approximately walk down the degree sequence, visiting the node with the highest degree, followed by a node of the next highest degree, etc. Let $`ma`$ be the degree of the last node we need to visit in order to scan a certain fraction of the graph. We make the self-consistent assumption that $`a<<m`$, i.e. the degree of the node has not dropped too much by the time we have scanned a fraction of the graph. Then the number of first neighbors scanned is given by

$$z_{1D}=_{ma}^mNk^{1\tau }𝑑kNam^{1\tau }$$
(21)
The number of nodes having degree between $`ma`$ and $`m`$, or equivalently, the number of steps taken is given by $`_{ma}^mk^\tau a`$. The number of second neighbors when one follows the degree sequence is given by:

$$z_{1D}G_1^{}(1)Nam^{2(2\tau )}$$
(22)
which gives the number of steps required as

$$sm^{2(\tau 2)}N^{2\frac{4}{\tau }}$$
(23)
We now consider when and why it is possible to go down the degree sequence. We start with the fact that the original degree distribution is a power-law:

$$p(x)=(\underset{1}{\overset{m}{}}x^\tau )^1x^\tau $$
(24)
where $`m=N^{1/\tau }`$ is the maximum degree. A node chosen by following a random link in the graph will have its remaining outgoing edges distributed according to

$$p^{}(x)=\left[\underset{0}{\overset{m1}{}}(x+1)^{(1\tau )}\right]^1(x+1)^{(1\tau )}$$
(25)
At each step one can choose the highest degree node among the $`n`$ neighbors. The expected number of the outgoing edges of that node can be computed as follows. In general, the cumulative distribution (CDF) $`P_{max}(x,n)`$ of the maximum of $`n`$ random variables can be expressed in terms of the CDF $`P(x)=_0^xp(x)\mathrm{d}x`$ of those random variables: $`P_{max}(x,n)=P(x)^n`$. This yields

$$p_{max}^{}(x,n)=n(1+x)^{1\tau }(\tau 2)\left[1(x+1)^{2\tau }\right]^{n1}(1N^{2/\tau 1})^n$$
(26)
for the distribution of the number of links the richest neighbor among $`n`$ neighbors has.

Finally, the expected degree of the richest node among n is given by

$$E[x_{max}(n)]=\underset{0}{\overset{m1}{}}xp_{max}^{}(x,n)$$
(27)
Numerically integrating the above equation yields the ratio between the degree of a node and the expected degree of its richest neighbor, plotted in Figure 3. For a range of exponents and node degrees, the expected degree of the richest neighbor is higher than the degree of the node itself. However, as one moves to nodes of higher and higher degree, the probability of finding a neighbor with an even higher degree starts falling (the precise point depends strongly on the power-law exponent).

What this means is that one can approximately follow the degree sequence across the entire graph for a sufficiently small graph or one with a power-law exponent close to 2 ($`2.0<\tau <2.3`$). At each step one chooses a node with degree higher than the current node, quickly finding the one with the highest degree. Once the highest degree node has been visited, it will be avoided, and a node of approximately second highest degree will be chosen. Effectively, after a short initial climb, one goes down the degree sequence. This is the most efficient way to do this kind of sequential search.

## III Simulation

We used simulations on a random network with a $`\tau =2.1`$ power-law link distribution and a simple cutoff at $`mN^{1/\tau }`$ to validate our analytical results. The graph is generated by assigning links at random between nodes of pre-assigned degree drawn from the power-law distribution. For $`2<\tau <3.48`$, a graph contains a giant connected component (GCC), the largest group of nodes such that any node can be reached from any other node following links . All our measurements were performed on the GCC which contained the majority of the nodes of the original graph and most of the links as well. The link distribution of the GCC is nearly identical to that of the original graph with a slightly smaller number of nodes of degree 1 and 2.

Next we apply our message passing algorithm to the network. Two nodes, the source and the target, are selected at random. At each time step the node which has the message passes it on to one of its neighbors. The process ends when the message is passed on to a neighbor of the target, that, knowing the identity of its neighbors, passes the message to the target directly. The process is analogous to performing a random walk on a graph, where each node is ’visited’ as it receives the message.

There are several variants of the algorithm, depending on the strategy and the amount of local information available.

1. The node passes the message on to one of its neighbors at random, optionally avoiding a node which has already seen the message.
2. The node knows the degrees of its neighboring nodes and chooses to pass the message onto the neighbor with the most neighbors.
3. The node knows who its neighbors’ neighbors are and passes the message onto a neighbor of the target if possible.

In order to avoid passing the message to a node that has already seen the message, the message itself must be signed by the nodes as they receive the message. Further, if a node has passed the message, and finds that all of its neighbors are already on the list, it puts a special mark next to its name, which means that it is unable to pass the message onto any new node. This is equivalent to marking nodes as follows:

Node has not been visited.

Node has been visited, but all its neighbors have not.

Node and all its neighbors have been visited already.

Here we compare two strategies. The first performs a random walk, where only retracing the last step is disallowed. In the message passing scenario, this means that if Bob just received a message from Jane, he wouldn’t return the message to Jane if he could pass it to someone else. The second strategy is a self avoiding walk which avoids passing the message to previously visited nodes and prefers high degree nodes to low degree ones. In both strategies the first and second neighbors are scanned at each step.

Figure 4(a) shows the scaling of the average search time with the size of the graph for the two strategies. The scaling (exponent 0.79 for the random walk and 0.70 for the high degree strategy) is not as favorable as in the analytic results derived above ($`0.14`$ for the random walk and $`0.1`$ for the high degree strategy when $`\tau =2.1`$) .

Consider, on the other hand, the number of steps it takes to cover half the graph. That is, instead of asking how long it would take on average to find any node in the graph, we ask how long it would take to find the first $`50\%`$ of the nodes. Such a measure is reasonable in a network where more than one node is likely to be able to satisfy a request. In a social context, there might be more than one person who has a particular item or can share expertise on a subject. In the context of a file sharing network, there might be more than one node having the requested file.

For this measure we observe a scaling which is much closer to the ideal. As shown in Figure 4(b), the cover time scales as $`N^{0.37}`$ for the random walk strategy vs. $`N^{0.15}`$ from Equation 18. Similarly, the high degree strategy cover time scales as $`N^{0.24}`$ vs. $`N^{0.1}`$ in Equation 23.

The difference in the value of the scaling exponents of the cover time and average search time implies that a majority of nodes can be found fairly efficiently, but others demand high search costs. As Figure 4(c) shows, a large portion of the 10,000 node graph is covered within the first few steps, but some nodes take as many steps or more to find as there are nodes in total. For example, the high degree seeking strategy finds about 50% of the nodes within the first 10 steps (meaning that it would take about $`10+2=12`$ hops to reach 50% of the graph). However, the skewness of the search time distribution bring the average number of steps needed to 217.

Some nodes take a long time to find because the random walk, after a brief initial period of exploring fresh nodes, tends to revisit nodes. It is a well-known result that the stationary distribution of a random walk on an undirected graph is simply proportional to the distribution of links emanating from a node. Thus, nodes with high-degree are often revisited in a walk.

A high-degree seeking self-avoiding walk is an improvement over the random walk taking 13 times fewer steps, but still cannot avoid retracing its steps. Figure 4(d) shows the color of nodes visited on such a walk for a $`N=1000`$ node power-law graph with exponent 2.1 and an abrupt cutoff at $`N^{1/2.1}`$. The number of nodes of each color encountered in 50 step segments is recorded in the bar for that time period, showing that some grey and black nodes were encountered before the all of the nodes were found.

Although revisiting nodes slows down search, it is the form of the link distribution that is responsible for changes in the search cost scaling. In a graph with a uniform link distribution the number of new nodes discovered at every step would be proportional to the number of unexplored nodes in the graph. The factor by which the search is slowed down through revisits would be independent of the size of the graph.

In contrast, in a power-law graph, a large number of links point to only a small subset of high degree nodes. When a new node is visited, its links do not let us uniformly sample the graph, they preferentially lead to high degree nodes, which have likely been seen or visited in a previous step. Ironically, the presence of high degree nodes, so useful to our search strategies, also worsens the search cost scaling from the ideal scaling found in sections II B and II C. This would not be true of a Poisson graph, where all the links are randomly distributed and hence all nodes have approximately the same degree. We will explore and contrast the search algorithm on a Poisson graph in the following section.

## IV Comparison with Poisson distributed graphs

In a Poisson random graph with $`N`$ nodes and $`z`$ edges, the probability $`p=z/N`$ of an edge between any two nodes is the same for all nodes. The generating function $`G_0(x)`$ is given by :

$$G_0(x)=e^{z(x1)}$$
(28)
In this special case $`G_0(x)=G_1(x)`$, so that the distribution of outgoing edges of a node is the same whether one arrives at the vertex by following a link or picks the node at random. This makes the analysis of search in a Poisson random graph particularly simple. The expected number of new links encountered at each step is a constant $`p`$, so that the number of steps needed to cover a fraction $`c`$ of the graph is $`s=cN/p`$. If $`p`$ remains constant as the size of the graph increases, the cover time scales linearly with the size of the graph. This has been verified via simulation of the random walk search as shown in Figure 5.

In our simulations, in order to keep the total number of edges equal between power-law and Poisson graphs of the same size, the probability $`p`$ increases with the size. It grows slowly towards its asymptotic value because of the particular choice of cutoff at $`mN^{(1/\tau )}`$ for the power-law link distribution. We generated Poisson graphs with the same number of nodes and links for comparison. Within this range of graph sizes, growth in the average number of links per node appears as $`N^{0.6}`$, making the average number of 2nd neighbors scale as $`N^{0.15}`$. This means that the scaling of the cover time scales as $`N^{0.85}`$, as shown in Figure 5.

Note how well the simulation results match the analytical expression. This is because nodes can be sampled in an approximately even fashion by following links as is illustrated in Figure 5(inset). If links are evenly distributed among the nodes, then when the search has covered 50% of the graph, one would expect to revisit previously seen nodes about 50% of the time. This is indeed the case for the Poisson graph.

However, for the power-law graph, when 50% of the graph has been visited, nodes are revisited about 80% of the time, which implies that the same high degree nodes are being revisited before new low-degree ones. This bias introduces a discrepancy between the analytic scaling and the simulated results in the power-law case.

However, even the simulated $`N^{0.35}`$ scaling for a random, minimally self-avoiding strategy on the power-law graph out-performs the ideal $`N^{0.85}`$ scaling for the Poisson graph. It’s also important to note that the the high degree node seeking strategy has a much greater success in the power-law graph because it relies heavily on the fact that the number of links per node varies considerably from node to node. In the Poisson graph, the variance in the number of links is much smaller, making the high degree node seeking strategy comparatively ineffective as shown in.

Figure 6 shows an illustration of this point. We repeat the experiment in Figures 1 and 2 on larger power-law and Poisson graphs with $`N=10,000`$. In the power-law graph we start from a randomly chosen node. In this case the starting node has only one link, but two steps later we find ourselves at a node with the highest degree. From there, one approximately follows the degree sequence, that is, the node richest in links, followed by the second richest node, etc. The strategy has allowed us to scan the maximum number of nodes in the minimum number of steps. In comparison, the maximum degree node of the exponential graph is 11, and it is reached only on the 81st step. Even though the two graphs have a comparable number of nodes and edges, the exponential graph does not lend itself to quick search.

## V Gnutella

Gnutella is a peer-to-peer filesharing system which treats all client nodes as functionally equivalent and lacks a central server which can store file location information. This is advantageous because it presents no central point of failure. The obvious disadvantage is that the location of files is unknown. When a user wants to download a file, she sends a query to all the nodes within a neighborhood of size $`ttl`$, the time to live assigned to the query. Every node passes on the query to all of its neighbors and decrements the $`ttl`$ by one. In this way, all nodes within a given radius of the requesting node will be queried for the file, and those who have matching files will send back positive answers.

This broadcast method will find the target file quickly, given that it is located within a radius of $`ttl`$. However, broadcasting is extremely costly in terms of bandwidth. Every node must process queries of all the nodes within a given $`ttl`$ radius. In essence, if one wants to query a constant fraction of the network, say 50%, as the network grows, each node and network edge will be handling query traffic which is proportional to the total number of nodes in the network.

Such a search strategy does not scale well. As query traffic increases linearly with the size of Gnutella graph, nodes become overloaded as was shown in a study by Clip2 . 56k modems are unable to handle more than 20 queries a second, a threshold easily exceeded by a network of about 1,000 nodes. With the 56k nodes failing, the network becomes fragmented, allowing users to query only small section of the network.

The search algorithms described in the previous sections may help ameliorate this problem. Instead of broadcasting a query to a large fraction of the network, a query is only passed onto one node at each step. The search algorithms are likely to be effective because the Gnutella network has a power-law connectivity distribution as shown in the inset of Figure 7.

Typically, a Gnutella client wishing to join the network must find the IP address of an initial node to connect to. Currently, ad hoc lists of ”good” Gnutella clients exist . It is reasonable to suppose that this ad hoc method of growth would bias new nodes to connect preferentially to nodes which are already fairly well-connected, since these nodes are more likely to be ”well-known”. Based on models of graph growth  where the ”rich get richer”, the power-law connectivity of ad hoc peer-to-peer networks may be a fairly general topological feature.

By passing the query to every single node in the network, the Gnutella algorithm fails to take advantage of its connectivity distribution. To implement our algorithm the Gnutella clients must be modified to keep lists of the files stored by their first and second degree neighbors have. This information must be passed at least once when a new node joins the network, and it may be necessary to periodically update the information depending on the typical lifetime of nodes in the network. The importance of localized indexing to scalability has been illustrated by the growth of the FastTrack  network whose size has reached hundreds of thousands of nodes. FastTrack is a network similar to Gnutella, with no central server, but using local indexing. A fraction of FastTrack clients with high bandwidth and reliability are selected to be supernodes. Supernodes index the files of other nodes and route queries on their behalf. We note that unlike FastTrack, our algorithm requires each node to store a local index.

Keeping track of the filenames of its neighbors’ files places an additional cost on every node. Since network connections saturated by query traffic are a major weakness in Gnutella, and since computational and storage resources are likely to remain much less expensive than bandwidth, such a tradeoff is readily made. However, now instead of every node having to handle every query, queries are routed only through high connectivity nodes, a situation similar to that of supernodes in the FastTrack network. Since nodes can select the number of connections that they allow, high degree nodes are presumably high bandwidth nodes that can handle the query traffic. The network has in effect created local directories valid within a two link radius. It is resilient to attack because of the lack of a central server. As for power-law networks in general , the network is more resilient than random graphs to random node failure, but less resilient to attacks on the high degree nodes.

Further adjustments to the present Gnutella clients to implement our algorithm involve switching from broadcasting queries to passing them only to the highest degree nodes. To execute a self-avoiding search, nodes need to append their IDs to the query as they process it.

Figure 7 shows the success of the high degree seeking algorithm on the Gnutella network. We simulated the search algorithm on a crawl by Clip2 of the actual Gnutella network of approximately 700 nodes. Assuming that every file is stored on only one node, 50% of the files can be found in 8 steps or less. Furthermore, if the file one is seeking is present on multiple nodes, the search will be even faster.

To summarize, we have argued that truly peer-to-peer networks like Gnutella are likely to have a power-law structure, and that the local search algorithms we have described can be effective. As the number of nodes increases, the (already small) number of nodes that will need to be queried increases sub-linearly. As long as the high degree nodes are able to carry the traffic, the Gnutella network’s performance and scalability may improve by using these search strategies.

## VI Path finding

So far we have only discussed the amount of time it takes to locate a node a single time. But in the process of searching for a node, one is also mapping out a path which could be used to contact that node in the future. Removing loops and backtracking steps from the search path leaves a route to the desired node. This route could be reused should one desire to communicate with the node again.

Kim et al.  have shown that following a high-degree seeking strategy on power-law graphs produces paths which scale on average as the logarithm of the size of the network. While the paths found are not always the shortest paths themselves, they share in the logarithmic scaling of the average shortest path. In contrast, random walker strategies, or strategies on non-power-law graphs such as Poisson random graphs of small world graphs defined by Watts and Strogatz , produce paths which whose scaling is power-law.

Following the methods of Kim et al, we constructed a scale-free network of Barabasi and Albert (BA)  type. Starting with a small number ($`m_0=2`$) of vertices, a new vertex with $`m=2`$ edges is added at each time step such that the probability of an edge connecting to a vertex is proportional to the degree of the vertex. This method yields a power-law network which has an exponent $`\tau =3`$ but is not truly random because correlations between node degrees do exist. Although $`\tau =3`$ lies outside the regime favorable to the previously discussed search strategies, requiring many steps to locate a node, the paths obtained with the loops removed scale logarithmically with the size of the network.

Figure 8 shows a comparison between the actual shortest paths and the shortest paths found using various search strategies on BA power-law graphs and Poisson graphs with the same total number of vertices and edges. Figure 8a shows the that shortest paths scale logarithmically in the size of the graph in both power-law and Poisson graphs, but the average shortest path in a power-law graph grows more slowly as the number of nodes increases. In effect, high degree nodes are drawing the graph closer together. This will be discussed further in section VII.

In order to find the exact shortest path, a broadcast method equivalent to a breadth first search (BFS) must be used. As mentioned in our discussion of Gnutella, broadcasting can overwhelm the bandwidth resources of the network. Kim et al. propose instead a search similar to the strategies discussed in sections II B and II C. The message is passed from only one node at each step, either randomly, or to the highest degree neighbor, using knowledge only of the first degree neighbors and their degree. When following the high-degree strategy, a node passes the message to the highest degree node it personally has not passed the message to previously.

This strategy is not truly self-avoiding in the sense that a node does not try to avoid passing the message onto a node that others have already contacted. Curiously, we find that a truly self-avoiding strategy, while locating nodes more quickly, does not yield short paths in the end. Kim et al. also note that if the strategy chooses nodes probabilistically, with the probability of a node being chosen proportional to its degree, the logarithmic scaling is lost. It is possible that both the self-avoiding and probabilistic methods fare worse because they return to the higher degree nodes less frequently. Because the majority of paths pass through high-degree nodes, the deterministic strategy which routinely revisits high degree nodes before moving forward is more likely to find a shorter path.

For comparison, we also plot in Figure 8c the length of the shortest paths found in the BA graph by choosing nodes at random rather than based on their connectivity. The paths found have a much less favorable power-law scaling of approximately $`N^{0.5}`$, compared to the logarithmic scaling of the shortest path. A similar result is obtained when using a high degree strategy on an equivalent Poisson graph, where extremely high degree nodes are absent.

Even in the case where short paths can be found using a high degree strategy on a power-law graph, the approach may be too costly. While the length of the average path found grows slowly as the size of the network increases, the average cost in the amount of time necessary to find the path, shown in Figure 8d, scales nearly linearly. The median number of steps required to find a node grows into the thousands while targets remain less than 10 steps away.

Although the above discussion of path finding strategies demonstrates how nodes could in principle find shortest paths between each other, the extremely high cost of this procedure suggests that additional clues as to the location of the target or knowledge of second degree neighbors would be necessary to make such an approach worthwhile.

## VII Shortening the shortest path

The previous sections described the role high degree nodes play in locating nodes and constructing a short path to a target. A further twist however, is the fact that the presence of high degree nodes shortens the shortest paths themselves. The average shortest path grows more slowly as the size of the network increases in a power-law graph than in an equivalent Poisson random graph.

Figure 9 shows the number of neighbors who are $`r`$ steps away from a randomly chosen vertex given by the formula of Newman et al. :

$$z_r=[\frac{z_{2A}}{z_1}]^{r1}z_1$$
(29)
with $`z_1`$ and $`z_{2A}`$ given by Equations 4 and 8. By choice, the Poisson graph has the same average number $`z_1`$ of first degree neighbors. Using the above result that the expected number of outgoing edges following a link is equal to the average vertex degree, the number of second degree neighbors is simply $`z_1^2`$.

The number of nodes at distance $`r`$ scales as $`\mathrm{exp}(\alpha r)`$, $`\alpha =z_{2A}/z_1`$. The actual number of neighbors of course cannot continue to increase exponentially with $`r`$ due to the finite size of the graph. For a Poisson graph $`\alpha =z_1`$, where $`z_1`$ is determined by the degree distribution of the power-law graph and asymptotes as the size of the graph increases. The ratio of the number of second degree to first degree neighbors grows more rapidly for a power-law graph as shown in the inset of Figure 9.

### A Iterative deepening

The fact that the number of hops between nodes is shorter in a power-law graph implies that the broadcasting method of locating nodes and resources will return results more quickly. This is because, as shown in Figure 9, compared to other graph topologies, many more nodes are available at the same radius. Yang and Garcia-Molina  and Lv et al.  have experimented with a local search method that benefits from this fact in order to improve upon the standard fixed-radius broadcast that the default Gnutella protocol uses.

Yang and Garcia-Molina’s method, which they call iterative deepening, begins by sending out standard Gnutella queries in a sequence. Queries in the sequence differ only in that they have increasing $`ttl`$ settings. For example, the first query may be a broadcast that is $`2`$ levels deep. Then the sending client might wait a pre-specified time for a response, and if no results are returned, may send out another query with a $`ttl`$ of $`3`$. The method is therefore parameterized by a sequence of $`ttl`$ values and a waiting value.

The method is an improvement over the default protocol when the queries can be satisfied by nodes closer than the maximum radius defined by the $`ttl`$ of the default. In that case, bandwidth and processing cost are saved. Their experiments on a live Gnutella client showed very good improvements. The bandwidth used and processing cost was $`19\%`$ and $`41\%`$ of the default policy, and they argue that the entire network’s performance would increase significantly if each client adopted the iterative deepening policy. Some similar results of simulations on different graph topologies are reported in .

## VIII Adaptive search

The above sections have examined strategies for finding a node on a network knowing nothing other than the identities of one’s first and second neighbors. However, a node can learn about the network over time and adapt its search strategies. Yang and Garcia-Molina  performed experiments on the Gnutella network in which a modified Gnutella node selectively passed a query onto one of its neighbors. The neighbors thereafter would follow the standard Gnutella protocol and broadcast the query to all of their neighbors. To make the experiment realistic, the queries were sampled from a collection gathered by passively listening in on Gnutella traffic.

Yang et al. found that selecting the node which had previously delivered a specified number of results in the least amount of time outperformed a strategy which selects a random or a high-degree neighbor in the first step. The result showed that adapting the search algorithm to incorporate information learned about the network can deliver results comparable to BFS (broadcast) search while using considerably less processing power and bandwidth.

While nodes can adapt their search strategies based on the changing performance of nodes in the network, the network itself can grow and restructure in order to facilitate search. Freenet  is an example of a network which dynamically changes connections and distributes data files as a result of queries passing through it. Although decentralized, the Freenet network allows for nodes to specialize in locating subsets of files and for nodes to direct queries to nodes most likely to be able to route or satisfy the query.

Each node stores a routing table of files identified by a unique key and the node which is storing the file. When a node receives a request for a file listed in its routing table, it forwards the request to the node listed as having the file. If the there is no file matching the key, it will forward the request to the location of a file with the ’closest’ key to the key requested. If the query is eventually satisfied, the file will be passed back along the same route as the query, and the node will mark the node’s location. In this way nodes learn of the locations of files with keys similar to the ones already listed in their routing tables and can specialize in a particular region of the key space, expediting the search further.

Nodes that reliably answer queries will be added to more routing tables and hence will be contacted more often than nodes that do not. In simulations of the network this leads to high degree nodes acquiring even more connections, and, unsurprisingly, to a power-law distribution.

Figure 10 shows the number of hops required to satisfy a request as a simulated Freenet network grows from 20 to 200,000 nodes. The median path length scales as $`N^{0.28}`$, and is a mere 8 hops for a network of 10,000 nodes. The result shows that using a focused search in combination with an adaptive network can improve scalability of a p2p network.

## IX Conclusion

In this chapter we have shown that local search strategies in power-law graphs have search costs which scale sub-linearly with the size of the graph, a fact that makes them very appealing when dealing with large networks. The most favorable scaling was obtained by using strategies which preferentially utilize the high connectivity nodes in these power-law networks. We also established the utility of these strategies for searching on the Gnutella peer-to-peer network. Furthermore, we reviewed the effectiveness of other improvements to simple broadcast on Gnutella such as iterative deepening and adaptive search.

Our results on high-degree seeking local search strategies may extend to social networks. However, in social networks, it is clear that people have a wide variety of additional cues to help them find who and what they need. Nevertheless, our results suggest that even strategies that neglect those cues may perform reasonably well on large power-law networks when they take advantage of the connectedness of nodes. These strategies have intuitive appeal, since people naturally ask those they perceive to be well-connected when trying to locate others in a social network.

It may not be coincidental that several large networks are structured in a way that naturally facilitates search. For example, large social networks, such as the AT&T call graph  and the collaboration graph of film actors, have exponents in the range ($`\tau =2.12.3`$) which according to our analysis makes them especially suitable for searching using simple, local algorithms. Being able to reach remote nodes by following intermediate links allows communication systems and people to get to the resources they need and distribute information within these informal networks. At the social level, our analysis supports the hypothesis that highly connected individuals do a great deal to improve the effectiveness of social networks in terms of access to relevant resources .

Furthermore, it has been shown that the Internet backbone has a power-law distribution with exponent values between 2.15 and 2.2 , and web page hyperlinks have an exponent of 2.1 . While in the Internet search is more structured, using routing tables for directing packets and search engines for finding web pages, high degree nodes still play a very significant role. Packets are usually routed through high degree hubs, and people searching for information on the Web turn to highly connected nodes, such as directories and search engines, which can bring them to their desired destinations. On the other hand, a system such as the power grid of the western United States, which does not serve as a message passing network, has an exponential degree distribution.

Networks for which locating and distributing information play a vital role, even without perfect global information, tend to be power-law with exponents favorable to local search. Actually, we find it likely that these networks could have evolved so as to facilitate search and information distribution.

Acknowledgements

We would like to thank Clip2 for the use of their Gnutella crawl data.


format: text

text:
# 1 Introduction

## 1 Introduction

The discovery in the early days of string theory that string amplitudes in low energy regimes maybe reproduced by Yang-Milles field theory for open strings and gravitational field theory for closed strings, was the beginning of a long, fruitful study into the relation of string theory and field theory in general and in low energy in particular .

The lowest order in momentum expansion of the low energy string theory confirmed the interpretation of the massless string modes as the gauge bosons and gravitons of the respective theories, and the next order was a prediction for the corrections to the gauge theory and to the gravity.

The realization of the significance of D-branes in string theory, correspondingly led to the study of the low energy effective dynamics of these objects in addition to the bulk dynamics . The lowest order in the momentum expansion turned out to be the DBI action with higher order corrections involving nontrivial terms, both in the bosonic string and the superstring theory.

Discovery of noncommutativity in string theory in the presence of a nontrivial background  resulted in the dramatic resurgence of noncommutative gauge theories with their highly nontrivial novel properties emerging as deformation of the low energy action of open strings in the presence of a background. Higher order corrections to the noncommutative gauge theory have also been derived.

It is then natural to ask what kind of deformation the low energy effective action of closed strings suffers in the presence of constant back ground antisymmetric field.
Noncommutative deformations of gravity have been proposed and studied recently . However they have not been derived from string theory and are ad hoc in this sense. One of the motivations of the present study is to throw light on these deformations.

In this work we begin to address this problem by looking at the low energy amplitude of two closed strings with a D-brane in the presence of a constant background $`B`$ field. We find that as expected the bulk action is not modified, however, the effective action describing the dynamics of the D-brane is modified due to the presence of the constant B field on the D-brane. However the effective action is not obtainable, as a naive T-duality might indicate, from the action of vanishing $`B`$, by replacing the metric $`g`$ by $`g+B`$.

This might be understood on the basis of the fact that T-duality, at this order, mixes graviton scattering with antisymmetric field scattering and is highly nontrivial.

In section two we write down the amplitude of scattering of two gravitons with a D-brane in the presence of a B field and find its low energy behaviour. In section three we find the low energy effective action describing those amplitude to order $`\alpha ^{}`$. Section four is devoted to discussion, in particular on the issue of covariance of the effective action.

## 2 String scattering from D-branes

In this section we compute the tree level bosonic string scattering amplitude of two massless closed string off a noncommutative D-brane. We take D-brane as a disk and conformaly mapped on the upper half plane, with mixed boundary conditions and use the following notation for indices, on and off the D-brane

$$\mu ,\nu =0,..,25,a,b=0,..,p,i,j=p+1,..,25.$$
(1)
For a D-brane localized at $`x^{p+1},\mathrm{},x^{25}`$, the boundary conditions are

$$\eta _{ab}(\overline{})X^a+B_{ab}(+\overline{})X^a_{z=\overline{z}}=0.$$
(2)
The two points correlator of string coordinates $`X^\mu (z,\overline{z})`$ on the D-brane is

$`X_i^\mu X_j^\nu ={\displaystyle \frac{\alpha ^{}}{2}}\left[\eta ^{\mu \nu }log((z_iz_j)(\overline{z}_i\overline{z}_j))+D^{\mu \nu }log(z_i\overline{z}_j)+D^{\nu \mu }log(\overline{z}_iz_j)\right],`$ (3)
where

$$D^{ba}=2(\frac{1}{\eta +B})^{ab}\eta ^{ab},D^{ij}=\delta ^{ij},D_{}^{\mu }{}_{\alpha }{}^{}D^{\nu \alpha }=\eta ^{\mu \nu },$$
(4)
with $`g`$ the flat metric. Using these correlators we can compute the scattering amplitude of two closed strings off a D-brane,

$$A=g_c^2e^\lambda d^2z_1d^2z_2V(z_1,\overline{z}_1)V(z_2,\overline{z}_2),$$
(5)
with $`g_c`$ the closed string coupling constant and $`\lambda `$ the Euler number of the world sheet. The appropriate vertex operators for the closed strings are,

$$V(z_i,\overline{z}_i)=ϵ_{\mu \nu }:X^\mu (z_i)\mathrm{exp}(ik_i.X(z_i))::\overline{}\stackrel{~}{X}^\nu (\overline{z}_i)\mathrm{exp}(ik_i\stackrel{~}{X}(\overline{z}_i)):,$$
(6)
which the momenta $`k_i`$ and polarizations $`ϵ_{\mu \nu }`$ of the massless closed strings satisfying

$$ϵ_{\mu \nu }k^\mu =ϵ_{\mu \nu }k^\nu =0,k^2=0.$$
(7)
To go further we use the change of variable as follow,

$$\stackrel{~}{X}^\mu (\overline{z}_i)=D_{}^{\mu }{}_{\xi }{}^{}X^\xi (\overline{z}_i),$$
(8)
so that the closed string vertices change to

$$V(z_i,\overline{z}_i)=ϵ_{\mu \lambda }D_{}^{\lambda }{}_{\nu }{}^{}:X^\mu (z_i)\mathrm{exp}(ik_i.X(z_i))::\overline{}X^\nu (\overline{z}_i)\mathrm{exp}(ik_i.D.X(\overline{z}_i)):.$$
(9)
Now inserting these vertices into (5) and going through the calculation of the correlation functions we find

$$A=g_c^2e^\lambda ϵ_{1\mu \lambda }D_{}^{\lambda }{}_{\nu }{}^{}ϵ_{2\alpha \rho }D_{}^{\rho }{}_{\beta }{}^{}d^2z_1d^2z_2𝒜^{\mu \nu \alpha \beta },$$
(10)
where

$`𝒜^{\mu \nu \alpha \beta }`$ $`=`$ $`iC_{D_2}^X(2\pi )^{p+1}\delta ^{p+1}(k_1+k_1.D+k_2+k_2.D)\mathrm{exp}\{{\displaystyle \frac{\alpha ^{}}{2}}[k_1.D.k_1log(z_1\overline{z}_1)`$ (11)
$`+`$ $`k_2.D.k_2log(z_2\overline{z}_2)+k_1.k_2log(z_1z_2)+k_1.k_2log(\overline{z}_1\overline{z}_2)`$ (13)
$`+`$ $`k_2.D.k_1log(z_1\overline{z}_2)+k_1.D.k_2log(\overline{z}_1z_2)]\}`$ (15)
$`\times `$ $`\{q_{1\overline{1}}^{\mu \nu }q_{2\overline{2}}^{\alpha \beta }+q_{12}^{\mu \alpha }q_{\overline{1}\overline{2}}^{\nu \beta }+q_{1\overline{2}}^{\mu \beta }q_{\overline{1}2}^{\nu \alpha }+q_{1\overline{1}}^{\mu \nu }f_2^\alpha f_{\overline{2}}^\beta +q_{12}^{\mu \alpha }f_{\overline{1}}^\nu f_{\overline{2}}^\beta +q_{1\overline{2}}^{\mu \beta }f_{\overline{1}}^\nu f_2^\alpha `$ (17)
$`+`$ $`q_{\overline{1}2}^{\nu \alpha }f_1^\mu f_{\overline{2}}^\beta +q_{\overline{1}\overline{2}}^{\nu \beta }f_1^\mu f_2^\alpha +q_{2\overline{2}}^{\alpha \beta }f_1^\mu f_{\overline{1}}^\nu +f_1^\mu f_{\overline{1}}^\nu f_2^\alpha f_{\overline{2}}^\beta \},`$ (19)
in which $`C_{D_2}^X`$ is the functional determinant for the string fields and the delta function ensures conservation of momentum parallel to the D-brane. Here $`f`$’s are terms that come from correlation function between derivative and exponential terms while the $`q`$’s are between the derivative terms, and are

$$q_{ij}^{\mu \nu }=\frac{\alpha ^{}}{2}\frac{\eta ^{\mu \nu }}{(z_iz_j)^2},f_i^\mu =i\frac{\alpha ^{}}{2}\underset{ji}{}(\frac{k_j^\mu }{z_iz_j}),$$
(20)
with the indices as

$$i,j=1,\overline{1},2,\overline{2},z_{\overline{1}}=\overline{z}_1,z_{\overline{2}}=\overline{z}_2.$$
(21)
It is straight forward to see that the amplitude is SL(2,R) invariant. To fix this invariance we let $`z_1=iy`$ and $`z_2=i`$

$$d^2z_1d^2z_22(1y^2)dy.$$
(22)
The $`f`$ and $`q`$ terms then become

$`f_1^\mu ={\displaystyle \frac{1}{2iy}}({\displaystyle \frac{y+1}{y1}}k_2^\mu +{\displaystyle \frac{y1}{y+1}}k_2.D^\mu ),f_{\overline{1}}^\nu ={\displaystyle \frac{1}{2iy}}({\displaystyle \frac{y1}{y+1}}k_2^\nu +{\displaystyle \frac{y+1}{y1}}k_2.D^\nu )`$ (23)
(24)
$`f_2^\alpha ={\displaystyle \frac{1}{2i}}({\displaystyle \frac{y+1}{y1}}k_1^\alpha +{\displaystyle \frac{y1}{y+1}}k_1.D^\alpha ),f_{\overline{2}}^\beta ={\displaystyle \frac{1}{2i}}({\displaystyle \frac{y1}{y+1}}k_1^\beta +{\displaystyle \frac{y+1}{y1}}k_1.D^\beta )`$ (25)
(26)
$`q_{1\overline{1}}^{\mu \nu }={\displaystyle \frac{\eta ^{\mu \nu }}{4y^2}},q_{12}^{\mu \alpha }={\displaystyle \frac{\eta ^{\mu \alpha }}{(y1)^2}},q_{1\overline{2}}^{\mu \beta }={\displaystyle \frac{\eta ^{\mu \beta }}{(y+1)^2}}`$ (27)
(28)
$`q_{\overline{1}2}^{\nu \alpha }={\displaystyle \frac{\eta ^{\nu \alpha }}{(y+1)^2}},q_{\overline{1}\overline{2}}^{\nu \beta }={\displaystyle \frac{\eta ^{\nu \beta }}{(y1)^2}},q_{2\overline{2}}^{\alpha \beta }={\displaystyle \frac{\eta ^{\alpha \beta }}{4}}.`$ (29)
We have dropped terms which will be canceled when inserted in (10) using the physical conditions for closed strings. Inserting (29) into (19) we get

$`A`$ $`=`$ $`2i𝒞2^{\frac{\alpha ^{}}{2}(k_1.D_S.k_1+k_2.D_S.k_2)}{\displaystyle _0^1}𝑑y(1y^2)y^{\frac{\alpha }{2}^{}k_1.D_S.k_1}(y1)^{\alpha ^{}k_1.k_2}(y+1)^{\alpha ^{}k_1.D_S.k_2}`$ (30)
$`\{`$ $`({\displaystyle \frac{\alpha ^{}}{2}})^2[{\displaystyle \frac{a_1}{16y^2}}+{\displaystyle \frac{a_2}{(y1)^4}}+{\displaystyle \frac{a_3}{(y+1)^4}}]+({\displaystyle \frac{\alpha ^{}}{2}})^3[{\displaystyle \frac{a_4}{16y^2}}+{\displaystyle \frac{a_5}{4y(y+1)^2}}`$ (32)
$``$ $`{\displaystyle \frac{a_6}{4y(y1)^2}}{\displaystyle \frac{a_7(y+1)^2}{16y^2(y1)^2}}{\displaystyle \frac{a_8(y1)^2}{16y^2(y+1)^2}}+{\displaystyle \frac{a_9(y1)^2}{4y(y+1)^4}}{\displaystyle \frac{a_{10}(y+1)^2}{4y(y1)^4}}]`$ (34)
$`+`$ $`({\displaystyle \frac{\alpha ^{}}{2}})^4[{\displaystyle \frac{a_{11}}{16y^2}}+{\displaystyle \frac{a_{12}(y+1)^2}{16y^2(y1)^2}}+{\displaystyle \frac{a_{13}(y1)^2}{16y^2(y+1)^2}}+{\displaystyle \frac{a_{14}(y+1)^4}{16y^2(y1)^4}}+{\displaystyle \frac{a_{15}(y1)^4}{16y^2(y+1)^4}}]\},`$ (36)
where

$$𝒞=C_{D_2}^Xg_c^2e^\lambda (2\pi )^{p+1}\delta ^{p+1}(k_1+k_1.D+k_2+k_2.D).$$
(38)
$`D_A`$ and $`D_S`$ are the antisymmetric and symmetric parts of $`D`$ matrix. Notice that because of momentum conservation parallel to the D-brane we have $`k_1.D_A.k_2=0`$. The constants $`a_n`$’s depend on momentum and polarization of external states and are given in the appendix A. We choose the Mandelstam variables,

$`s=({\displaystyle \frac{1}{2}}(\eta +D).k_1)^2={\displaystyle \frac{1}{2}}k_1.D_S.k_1={\displaystyle \frac{1}{2}}k_2.D_S.k_2,`$ (39)
(40)
$`t=(k_1+k_2)^2=2k_1.k_2.`$ (41)
Finally making the change of variable $`y=\frac{1\sqrt{x}}{1+\sqrt{x}}`$ we find

$`A`$ $`=`$ $`2i𝒞({\displaystyle \frac{\alpha ^{}}{2}})^2\{a_1B({\displaystyle \frac{\alpha ^{}t}{4}}+1,\alpha ^{}s1)+a_2B({\displaystyle \frac{\alpha ^{}t}{4}}1,\alpha ^{}s+1)`$ (42)
$`+`$ $`a_3B({\displaystyle \frac{\alpha ^{}t}{4}}+1,\alpha ^{}s+1)({\displaystyle \frac{\alpha ^{}}{2}})[a_4B({\displaystyle \frac{\alpha ^{}t}{4}}+1,\alpha ^{}s1)`$ (44)
$``$ $`a_5B({\displaystyle \frac{\alpha ^{}t}{4}}+1,\alpha ^{}s)+a_6B({\displaystyle \frac{\alpha ^{}t}{4}},\alpha ^{}s)+a_7B({\displaystyle \frac{\alpha ^{}t}{4}},\alpha ^{}s1)`$ (46)
$`+`$ $`a_8B({\displaystyle \frac{\alpha ^{}t}{4}}+2,\alpha ^{}s1)a_9B({\displaystyle \frac{\alpha ^{}t}{4}}+2,\alpha ^{}s)`$ (48)
$`+`$ $`a_{10}B({\displaystyle \frac{\alpha ^{}t}{4}}1,\alpha ^{}s)]+({\displaystyle \frac{\alpha ^{}}{2}})^2[a_{11}B({\displaystyle \frac{\alpha ^{}t}{4}}+1,\alpha ^{}s1)`$ (50)
$`+`$ $`a_{12}B({\displaystyle \frac{\alpha ^{}t}{4}},\alpha ^{}s1)+a_{13}B({\displaystyle \frac{\alpha ^{}t}{4}}+2,\alpha ^{}s1)`$ (52)
$`+`$ $`a_{14}B({\displaystyle \frac{\alpha ^{}t}{4}}1,\alpha ^{}s1)+a_{15}B({\displaystyle \frac{\alpha ^{}t}{4}}+3,\alpha ^{}s1)]\},`$ (54)
where $`B`$’s are beta functions. Note that as a test of our calculations replacing every polarization of closed strings by momentum $`ϵ_{\mu \nu }k_\mu k_\nu `$ gives zero value for the amplitude. We recover the results of scattering amplitude for commutative D-branes found in  by turning the $`B`$ field off (see Appendix B). As we will be interested in the low energy effective theory of the string, we must analyze the pole structure of the amplitude (54). There are two types of singularities in this amplitude that come from the Beta functions. In fact the amplitude (54) is singular at

$$\frac{\alpha ^{}}{4}t1=n,\alpha ^{}s1=n^{},n,n^{}=0,1,\mathrm{}$$
(55)
which in terms of $`t`$ and $`s`$ of (41) are

$`t=m_{closed}^2={\displaystyle \frac{4}{\alpha ^{}}}(n+1)`$ (56)
(57)
$`s=m_{open}^2={\displaystyle \frac{1}{\alpha ^{}}}(n^{}+1),`$ (58)
exhibiting the mass spectrum of the intermediate closed string propagators in the t-channel and the mass spectrum of the open strings in the s-channel. Note that not all the Beta functions in (54) have pole for $`n=0,1,2,3`$ and $`n^{}=0,1`$. Now we may study the low energy limit of the amplitude i.e. $`s`$ , $`t`$ $`0`$. There are then three types of terms to consider
$`𝐭\mathrm{𝐜𝐡𝐚𝐧𝐧𝐞𝐥}:`$

$$A_t=\frac{i𝒞\alpha ^2}{t}\left\{2a_2s+a_6+a_7+a_{10}\alpha ^{}(a_{10}s+\frac{1}{2}a_{12}+a_{14})+𝒪(\alpha ^2)\right\},$$
(59)
$`𝐬\mathrm{𝐜𝐡𝐚𝐧𝐧𝐞𝐥}:`$

$`A_s`$ $`=`$ $`{\displaystyle \frac{i𝒞\alpha ^2}{4s}}\{{\displaystyle \frac{1}{2}}a_1t+a_5a_6a_7+a_8+a_9a_{10}({\displaystyle \frac{\alpha ^{}}{4}})[(a_4+a_7+a_8)t`$ (60)
$``$ $`2a_{12}+2a_{13}4a_{14}+4a_{15}]+𝒪(\alpha ^2)\},`$ (62)
$`\mathrm{𝐜𝐨𝐧𝐭𝐚𝐜𝐭}\mathrm{𝐭𝐞𝐫𝐦𝐬}:`$

$`A_c`$ $`=`$ $`{\displaystyle \frac{i𝒞\alpha ^2}{2}}\{(a_1+a_2a_3)+({\displaystyle \frac{\alpha ^{}}{2}})[a_4+a_7+a_8a_9+a_{10}`$ (63)
$``$ $`(2s{\displaystyle \frac{1}{2}}t)(a_1+a_2+a_3)]+𝒪(\alpha ^2)\}.`$ (65)
## 3 Low energy effective action

In this section we will derive the low energy action for the above amplitude to the first two leading orders of $`\alpha ^{}`$. For scattering of two gravitons we use the physical condition for them as,

$$ϵ_{\mu \nu }=ϵ_{\nu \mu },ϵ_{}^{\mu }{}_{\mu }{}^{}=0.$$
(66)
In the t-channel we have two gravitons which interact in the bulk space and produce another graviton or dilaton field which in turn is absorbed by the D-brane. It is easily seen that the massless antisymmetric field does not contribute to the amplitude. The t-channel amplitude to be reproduced by inserting for the coefficients $`a_i`$ of appendix A,

$`A_t`$ $`=`$ $`{\displaystyle \frac{i𝒞\alpha ^2}{t}}\{(k_1.D_S.k_1)Tr(ϵ_1.ϵ_2)+Tr(ϵ_1.D_S)(k_1.ϵ_2.k_1)+Tr(ϵ_2.D_S)(k_2.ϵ_1.k_2)`$ (67)
$``$ $`2k_2.ϵ_1.D_S.ϵ_2.k_12k_1.ϵ_2.ϵ_1.k_22k_1.D_S.ϵ_1.ϵ_2.k_12k_2.D_S.ϵ_2.ϵ_1.k_2`$ (69)
$``$ $`\alpha ^{}[(k_1.ϵ_2.ϵ_1.k_2)(k_1.D_S.k_1)+(k_1.ϵ_2.k_1)(k_2.ϵ_1.k_2)+(k_1.ϵ_2.k_1)(k_2.ϵ_1.D_S.k_2)`$ (71)
$`+`$ $`(k_2.ϵ_1.k_2)(k_1.ϵ_2.D_S.k_1)]\}=A_t^0+A_t^1,`$ (73)
where $`A_t^0(A_t^1)`$ contains terms in the curly bracket which are zeroth (first) order at $`\alpha ^{}`$. It is not difficult to see that the action which describes this amplitude to order of $`\alpha ^0`$ is nothing but the DBI and Einstein-Hilbert action. The DBI action in the Einstein frame is ,555For simplicity in writing we have dropped the coefficient of $`f`$ i.e. $`2\pi \alpha ^{}ff.`$

$$𝒮_{Dbrane}^0=T_pd^{p+1}xe^\mathrm{\Phi }\sqrt{det(e^{\gamma \mathrm{\Phi }}g++f)_{ab}},$$
(74)
where $`g`$ is the induced metric on the D-brane and $`_{ab}=B_{ab}2\kappa b_{ab}`$ is the pull back of the antisymmetric field along the D-brane with $`B`$ constant and $`f_{ab}`$ is the gauge field strength on the D-brane and $`\gamma =\frac{4}{d2}`$. Expanding $`g_{ab}`$ around the Minkowski metric, $`g_{ab}=\eta _{ab}+2\kappa h_{ab}`$ we get for the action to the first order of $`h`$,666Note that we have expanded the action (74) around the background $`\eta _{ab}+B_{ab}`$ using $`\sqrt{det(M_0+M)}=\sqrt{detM_0}(1+\frac{1}{2}Tr(M_0^1M)+\mathrm{}).`$

$$𝒮_{Dbrane}^0=\kappa T_pcd^{p+1}xh_{ab}V^{ab},$$
(75)
where

$$V^{ab}=\frac{1}{2}(\eta +D)^{ba},c=\sqrt{det(\eta +B)_{ab}}.$$
(76)
Equation (75) exhibits a source term for gravity on the D-brane,

$$(S_h)^{ab}=\frac{1}{2}T_p\kappa c(\eta ^{ab}+D_S^{ab}).$$
(77)
The Einstein-Hilbert action in the bulk is

$$S_{bulk}^{(0)}=\frac{1}{2\kappa ^2}d^{26}x\sqrt{G}R.$$
(78)
Using 26-dimensional propagator $`(G^{hh})_{\mu \nu \lambda \rho }`$ and the three point interaction vertex $`(V_{hϵ_1ϵ_2})^{\lambda \rho }`$ for gravitons coming from this action , and the above source term, we find

$$i(S_h)^{\mu \nu }(G^{hh})_{\mu \nu \lambda \rho }(V_{hϵ_1ϵ_2})^{\lambda \rho }=A_t^0+C_t^0,$$
(79)
where $`A_t^0`$ is exactly the zeroth order term of the amplitude (73), and $`C_t^0`$ is a contact term with no poles,

$$C_t^0=icT_p\kappa ^2(Tr(ϵ_1.ϵ_2)+Tr(ϵ_1.D_S.ϵ_2)).$$
(80)
Here the tension of the D-branes, $`T_p`$ from (74) is written in terms of the coefficients of (73) i.e.

$$T_p=\frac{𝒞\alpha ^2}{c\kappa ^2}.$$
(81)
We note that to this order of $`\alpha ^{}`$ the above results are exactly the same as in the superstring theory . To get the next order terms in the string amplitude (73), we include the next order of $`\alpha ^{}`$ gravitational action in the bulk,

$$S_{bulk}^{(1)}=\frac{\alpha ^{}}{8\kappa ^2}d^{26}xe^{\gamma \mathrm{\Phi }}\sqrt{G}(R^{\mu \nu \kappa \lambda }R_{\mu \nu \kappa \lambda }4R^{\mu \nu }R_{\mu \nu }+R^2).$$
(82)
There is a new three point interaction for gravitons $`V_{hϵ_1ϵ_2}^{}`$ in this Lagrangian. In addition it contains the interaction between one dilaton and two gravitons $`V_{\mathrm{\Phi }ϵ_1ϵ_2}`$. So there are two source terms, gravitational source $`S_h`$ and dilatonic source $`S_\mathrm{\Phi }`$ and we find

$$iS_hG^{hh}V_{hϵ_1ϵ_2}^{}+iS_\mathrm{\Phi }G^{\mathrm{\Phi }\mathrm{\Phi }}V_{\mathrm{\Phi }ϵ_1ϵ_2}=A_t^1+C_t^1,$$
(83)
where $`A_t^1`$ is the first order term of the amplitude (73) and

$`C_t^1`$ $`=`$ $`{\displaystyle \frac{icT_p\kappa ^2\alpha ^{}}{2}}\{k_1.D_S.k_1Tr(ϵ_1.ϵ_2)+k_1.k_2Tr(ϵ_1.D_S.ϵ_2)k_1.ϵ_2.ϵ_1.D_S.k_2`$ (84)
$`+`$ $`k_2.D_S.ϵ_2.ϵ_1.k_2k_1.ϵ_2.D_S.ϵ_1.k_2)\},`$ (86)
is a contact term. This calculation exhibits similar gravitational source term as in the order of $`\alpha ^0`$.

Next we consider the s-channel amplitude up to the first two powers of $`\alpha ^{}`$. We may write this amplitude, (60), as

$`A_s`$ $`=`$ $`{\displaystyle \frac{ic\kappa ^2T_p}{4s}}\{Tr(ϵ_1.D_S)(k_1.ϵ_2.D_S.k_2k_1.D_S.ϵ_2.D_S.k_2k_1.D_A.ϵ_2.D_A.k_2)`$ (87)
$`+`$ $`k_2.D_A.ϵ_2.D_S.ϵ_1.D_A.k_1+k_2.D_S.ϵ_2.D_S.ϵ_1.D_S.k_1+2k_2.D_A.ϵ_2.D_A.ϵ_1.D_S.k_1`$ (89)
$``$ $`k_2.D_S.ϵ_2.ϵ_1.D_S.k_1+k_2.D_A.ϵ_2.ϵ_1.D_A.k_1{\displaystyle \frac{1}{2}}k_1.k_2Tr(ϵ_1.D_S)Tr(ϵ_2.D_S)`$ (91)
$`+`$ $`({\displaystyle \frac{\alpha ^{}}{2}})[k_1.k_2Tr(ϵ_1.D_S)(k_2.D.ϵ_2.D.k_2)+(k_2.ϵ_1.D_S.k_1)(k_1.ϵ_2.D_S.k_2)`$ (93)
$``$ $`(k_1.D_S.ϵ_1.D_S.k_2)(k_2.D_S.ϵ_2.D_S.k_1)+2(k_1.D_A.ϵ_2.D_A.k_1)(k_1.D_S.ϵ_1.D_S.k_2)`$ (95)
$``$ $`(k_1.D_A.ϵ_2.D_A.k_1)(k_2.D_A.ϵ_1.D_A.k_2)]\}+(12)=A_s^0+A_s^1.`$ (97)
In this channel we expect the two gravitons scatter from the D-brane and exchange a gauge or scalar field which propagates on the D-brane. These propagating fields are in fact the low energy limits of the massless open strings on the D-brane, scalars $`(X^i)`$ and gauge bosons $`(a_a)`$. We would like to write down a Lagrangian for these fields on the D-brane which produces the vertices for interactions between gravitons and these fields and finally gives the scattering amplitude of the string theory. For zeroth order of $`\alpha ^{}`$ we again take the DBI action on D-brane (74) with gauge field strength defined as $`f_{ab}=_aa_b_ba_a`$ then expand the induced metric $`g_{ab}=_aX^\mu _bX^\nu g_{\mu \nu }`$ on the D-brane around the flat space and choose the static gauge $`(X^a=x^a)`$ to get

$$g_{ab}=\eta _{ab}+2\kappa h_{ab}+2\kappa (h_{ia}_bX^i+h_{bi}_aX^i)+_aX^i_bX_i+2\kappa h_{ij}_aX^i_bX^j.$$
(98)
Redefining the gauge and scalar fields by $`A_a=2\pi \alpha ^{}\sqrt{T_p}a_a`$ and $`\lambda ^i=\sqrt{T_p}X^i`$ and expanding DBI action around the background field $`\eta _{ab}+B_{ab}`$, for the zeroth order of $`\alpha ^{}`$ we find the following vertices,

$`(V_{ϵ_1A})^a=\sqrt{T_p}\kappa c(Tr(ϵ_1.V_S)k_1.V_A^a2k_1.V_S.ϵ_1.V_A^a2k_1.V_A.ϵ_1.V_S^a),`$ (99)
(100)
$`(V_{ϵ_1\lambda })_i=\sqrt{T_p}\kappa c(Tr(ϵ_1.V_S)k_{1i}2k_1.V_S.ϵ_{1i}),`$ (101)
and propagators,

$$(G^{\lambda \lambda })^{ij}=\frac{i}{cs}\eta ^{ij},(G^{AA})_{ab}=\frac{i}{cs}(V_S^1)_{ab},$$
(102)
where $`V_A`$ and $`V_S`$ are the antisymmetric and symmetric parts of the matrix $`V`$. Note that in deriving the above vertices we have used the fact that the closed string fields in the DBI action appear as functionals of the transverse scalar fields $`X^i`$ which should be Taylor expanded. Knowing these vertices and propagators we can compute the amplitude from the effective field theory on D-brane and show that to order of $`\alpha ^0`$,

$$V_{ϵ_1\lambda }G^{\lambda \lambda }V_{\lambda ϵ_2}+V_{ϵ_1A}G^{AA}V_{Aϵ_2}=A_s^0+C_s^0,$$
(103)
where $`A_s^0`$ is the zeroth order term in (97) and $`C_s^0`$ is a contact term,

$$C_s^0=\frac{i\kappa ^2T_pc}{4}Tr(ϵ_1.D_S)Tr(ϵ_2.D_S).$$
(104)
We have used the following useful relations in the derivation

$$(V_AV_S^1V_A)^{ab}=\frac{1}{2}(\eta D_S)^{ab},\eta ^{ij}=\frac{1}{2}(\eta D_S)^{ij}.$$
(105)
It turns out that in order to describe the amplitude to the first order in $`\alpha ^{}`$ we need to add new terms to the DBI action as follow

$`𝒮^1`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}T_p}{2}}{\displaystyle }d^{p+1}x\{\sqrt{det(\eta +B+f)}R_{abcd}({\displaystyle \frac{1}{\eta +B+f}})^{ad}({\displaystyle \frac{1}{g+B+f}})^{bc}`$ (106)
$``$ $`\sqrt{det(g+B+f)}(\mathrm{\Omega }_{}^{i}{}_{ac}{}^{}\mathrm{\Omega }_{i}^{}{}_{bd}{}^{}\mathrm{\Omega }_{}^{i}{}_{ad}{}^{}\mathrm{\Omega }_{i}^{}{}_{bc}{}^{})({\displaystyle \frac{1}{g+B+f}})^{ad}({\displaystyle \frac{1}{g+B+f}})^{bc}\},`$ (108)
where $`R_{abcd}=g_{ae}R_{}^{e}{}_{bcd}{}^{}`$ and $`R_{}^{e}{}_{bcd}{}^{}`$ is Riemann tensor constructed out of induced metric on the D-brane and $`\mathrm{\Omega }`$’s are second fundamental forms,

$`R_{}^{a}{}_{bcd}{}^{}`$ $`=`$ $`\mathrm{\Gamma }_{}^{a}{}_{bd,c}{}^{}\mathrm{\Gamma }_{}^{a}{}_{bc,d}{}^{}+\mathrm{\Gamma }_{}^{e}{}_{bd}{}^{}\mathrm{\Gamma }_{}^{a}{}_{ce}{}^{}\mathrm{\Gamma }_{}^{e}{}_{bc}{}^{}\mathrm{\Gamma }_{}^{a}{}_{de}{}^{},`$ (110)
$`\mathrm{\Omega }_{ab}^i`$ $`=`$ $`\kappa (^ih_{ab}+_ah_{}^{i}{}_{b}{}^{}+_bh_{}^{i}{}_{a}{}^{})+_a_bX^i,`$ (112)
which $`a,b,c,d,e=0,\mathrm{},p`$ and $`i,j=p+1,\mathrm{}d`$. The $`\mathrm{\Gamma }`$’s are the Christoffel symbols constructed out of the induced metric $`g`$. This action contains every vertex that we need for producing the next order of $`\alpha ^{}`$ in (97), in addition to certain contact terms which we will describe later. To reproduce the s-channel amplitude of string theory from such an action we need to find the graviton-scalar and graviton-gauge field vertices. We find the first one from the second fundamental form linear in terms of $`X`$ and $`h`$, 777We must Taylor expand the linear terms in $`h`$ of the above action, but because of momentum conservation relation these terms do not contribute to the vertex.and the second one from the expansion the above Lagrangian linear in terms of $`f`$ and $`h`$. By summing these vertices corresponding to the above action with the previous terms which we found from DBI action to zeroth order of $`\alpha ^{}`$, we find that

$`(V_{ϵ_1A})^a`$ $`=`$ $`{\displaystyle \frac{\kappa c\sqrt{T_p}}{4}}\{2Tr(ϵ_1.D_S)k_1.V_A^a4k_1.D_S.ϵ_1.V_A^a+4k_1.D_A.ϵ_1.V_S^a`$ (113)
$``$ $`\alpha ^{}[(k_1.D_S.ϵ_1.D_S.k_1+k_1.D_A.ϵ_1.D_A.k_1)k_1.V_A^ak_1.D_S.k_1Tr(ϵ_1.D_S)k_1.V_A^a]\}`$ (115)
$`(V_{ϵ_1\lambda })_i`$ $`=`$ $`{\displaystyle \frac{\kappa c\sqrt{T_p}}{4}}\{2Tr(ϵ_1.D_S)k_{1i}4k_1.D_S.ϵ_{1i}`$ (117)
$``$ $`\alpha ^{}[(k_1.D_S.ϵ_1.D_S.k_1+k_1.D_A.ϵ_1.D_A.k_1)k_{1i}k_1.D_S.k_1Tr(ϵ_1.D_S)k_{1i}]\}.`$ (119)
To check that these vertices are in fact correct we have calculated one closed and one open string scattering from D-brane and we have found similar vertices (see Appendix C). Now using these vertices we can find the first order of $`\alpha ^{}`$ terms in s-channel from string theory. We have used the previous propagators for gauge and scalar fields, as (LABEL:act) does not introduce any corrections to the propagators. We then find

$$V_{ϵ_1\lambda }G^{\lambda \lambda }V_{\lambda ϵ_2}+V_{ϵ_1A}G^{AA}V_{Aϵ_2}=A_s^0+C_s^0+A_s^1+C_s^1,$$
(120)
in which $`A_s^0(A_s^1)`$ is exactly the zeroth (first) order of $`\alpha ^{}`$ terms of (97), $`C_s^0`$ is the zeroth order term in (104) and $`C_s^1`$ is the first order in $`\alpha ^{}`$ terms with no poles and can be written as

$`C_s^1`$ $`=`$ $`{\displaystyle \frac{ic\kappa ^2T_p\alpha ^{}}{4}}\{{\displaystyle \frac{1}{2}}Tr(ϵ_1.D_S)Tr(ϵ_2.D_S)(k_1.D_S.k_2k_1.k_2)+`$ (121)
$`+`$ $`Tr(ϵ_1.D_S)[2k_2.D_S.ϵ_2.k_1+{\displaystyle \frac{3}{2}}k_2.D.ϵ_2.D.k_2]\}+(12).`$ (123)
It remains to verify that all the above contact terms (80), (104) and contact terms from (74) at $`\alpha ^0`$ and (86) , (123) and contact terms from (LABEL:act) at $`\alpha ^{}`$ add up to the contact terms of the string amplitude (63). We can write (63) as

$`A_c`$ $`=`$ $`{\displaystyle \frac{ic\kappa ^2T_p}{4}}\{Tr(ϵ_1.D)Tr(ϵ_2.D)Tr(ϵ_1.ϵ_2)+Tr(D.ϵ_1.D.ϵ_2)`$ (124)
$`+`$ $`\alpha ^{}[Tr(ϵ_1.D)(k_2.D.ϵ_2.D.k_2)k_1.D.ϵ_2.D.ϵ_1.D.k_2+k_1.ϵ_2.ϵ_1.k_2`$ (126)
$`+`$ $`{\displaystyle \frac{1}{2}}(k_1.D.k_2)(Tr(ϵ_1.D)Tr(ϵ_2.D)+Tr(ϵ_1.ϵ_2)+Tr(D.ϵ_1.D.ϵ_2)]\}`$ (128)
$`+`$ $`(12).`$ (130)
If we expand DBI action (74), we find graviton-graviton contact terms from this expansion,

$$A_{hh}^0=2i\kappa ^2cT_p\{\frac{1}{2}Tr(ϵ_1.V)Tr(ϵ_2.V)Tr(ϵ_1.V.ϵ_2.V)\}.$$
(131)
We can show that by adding (80) and (104) to the above equation

$$A_{hh}^0+C_t^0+C_s^0=\frac{i\kappa ^2cT_p}{2}\{Tr(ϵ_1.D)Tr(ϵ_2.D)+Tr(ϵ_1.ϵ_2)Tr(ϵ_1.D.ϵ_2.D)\},$$
(132)
we find exactly the $`\alpha ^0`$ term in (130). Again as before if we expand Lagrangian in (LABEL:act), we find for graviton-graviton contact terms,

$`A_{hh}^1`$ $`=`$ $`2i\alpha ^{}\kappa ^2cT_p\{k_1.V.ϵ_2.ϵ_1.V.k_2k_1.V.ϵ_2.V.ϵ_1.k_2k_1.ϵ_2.V.ϵ_1.V.k_2`$ (133)
$`+`$ $`k_1.V.ϵ_2.V.ϵ_1.V.k_2{\displaystyle \frac{1}{4}}k_1.k_2Tr(ϵ_1.V)Tr(ϵ_2.V)+{\displaystyle \frac{1}{2}}k_1.V.k_2Tr(ϵ_1.V.ϵ_2)`$ (135)
$`+`$ $`{\displaystyle \frac{1}{4}}k_1.k_2Tr(V.ϵ_1.V.ϵ_2)+{\displaystyle \frac{1}{2}}k_1.V.k_1Tr(V.ϵ_1.V.ϵ_2)`$ (137)
$`+`$ $`(k_1.V.ϵ_1.k_2+{\displaystyle \frac{1}{2}}k_1.V.ϵ_1.V.k_1)Tr(ϵ_2.V)\}+(12),`$ (139)
we can show that by adding (86) and (123) to above equation,

$`A_{hh}^1+C_t^1+C_s^1`$ $`=`$ $`{\displaystyle \frac{i\alpha ^{}\kappa ^2cT_p}{4}}\{Tr(ϵ_1.D)k_2.D.ϵ_2.D.k_2k_1.D.ϵ_2.D.ϵ_1.D.k_2+k_1.ϵ_2.ϵ_1.k_2`$ (140)
$`+`$ $`{\displaystyle \frac{1}{2}}(k_1.D.k_2)[Tr(ϵ_1.D)Tr(ϵ_2.D)+Tr(ϵ_1.ϵ_2)+Tr(D.ϵ_1.D.ϵ_2)]\}`$ (142)
$`+`$ $`(12),`$ (144)
we recover exactly the $`\alpha ^{}`$ term in (130). It is noticeable that in evaluating the t-channel poles in field theory we use the linear coupling of graviton to the D-brane using the DBI action (74) which is of zero order of $`\alpha ^{}`$ whereas linear coupling of graviton to D-brane coming from action (LABEL:act) is of first order of $`\alpha ^{}`$ however using conservation of momentum this coupling has no effect in the t-channel.

It should be noted that when we turn off the $`B`$ field on the D-brane we find the Einstein-Hilbert action as we expected . To see this, note that as we turn off the $`B`$ field on the D-brane we see, $`V^{ab}=\eta ^{ab}`$ where upon (LABEL:act) changes up to some total derivatives to

$`𝒮_{Dbrane}^1`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}T_p}{2}}{\displaystyle d^{p+1}x\sqrt{detg_{ab}}(R+\mathrm{\Omega }_{}^{i}{}_{a}{}^{}{}_{}{}^{a}\mathrm{\Omega }_{i}^{}{}_{b}{}^{}{}_{}{}^{b}\mathrm{\Omega }_{}^{i}{}_{ab}{}^{}\mathrm{\Omega }_{i}^{}{}_{}{}^{ab})},`$ (145)
$`R`$ $`=`$ $`R_{abcd}g^{ac}g^{bd},`$ (147)
which $`a,b,c,d=0,\mathrm{},p`$ and $`i,j=p+1,\mathrm{}d`$. Where we have ignored gauge fields because they do not have any contraction with gravitons because of the antisymmetry of $`f_{ab}`$. In deriving the above equation we have used the following relation at $`𝒪(h^2)`$,

$$\sqrt{det\eta }R_{abcd}\eta ^{ad}g^{bc}=\sqrt{detg}R_{abcd}g^{ac}g^{bd}+(T.D),$$
(148)
which by momentum conservation relation, total derivative terms have no effect in scattering amplitude.

## 4 Discussion

In this work we have found the corrections to the DBI action to order of $`\alpha ^{}`$, (LABEL:act), for the description of the graviton- graviton-D-brane scattering in bosonic string theory in the presence of a constant $`B`$ field.

We have also calculated the corrections to the DBI action for dilaton and antisymmetric field scattering with a D-brane. The results are not qualitatively different and will be reported separately.

It is known that D-branes in the presence of background $`B`$ field become noncommutative and the DBI action can be written in terms of commutative gauge fields or in terms of the noncommutative open string fields involve the $``$ product and a Wilson line operator. We write the action (LABEL:act) in terms of commutative fields.

One may write the result in eq(LABEL:act) in the following form,

$`𝒮^1`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}T_p}{2}}{\displaystyle d^{p+1}x\sqrt{det(\eta +B+f)}(\frac{1}{\eta +B+f})^{ad}(\frac{1}{g+B+f})^{bc}}`$ (149)
$`\times `$ $`\left\{R_{abcd}\mathrm{\Omega }_{}^{i}{}_{ac}{}^{}\mathrm{\Omega }_{i}^{}{}_{bd}{}^{}+\mathrm{\Omega }_{}^{i}{}_{ad}{}^{}\mathrm{\Omega }_{i}^{}{}_{bc}{}^{}\right\},`$ (151)
which is reminiscent of the corresponding result for the case $`B=0`$, eq (147). This action as well as the action in (LABEL:act) are not in covariant form. One may try to write it in a covariant form;

$`𝒮_{cov}^1`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}T_p}{2}}{\displaystyle d^{p+1}x\sqrt{det(g+B+f)}(\frac{1}{g+B+f})^{ad}(\frac{1}{g+B+f})^{bc}}`$ (152)
$`\times `$ $`\left\{R_{abcd}\mathrm{\Omega }_{}^{i}{}_{ac}{}^{}\mathrm{\Omega }_{i}^{}{}_{bd}{}^{}+\mathrm{\Omega }_{}^{i}{}_{ad}{}^{}\mathrm{\Omega }_{i}^{}{}_{bc}{}^{}\right\};`$ (154)
but, this will give rise to new contact terms which are not present in the string theory amplitude, eq. (130). However, on general grounds one expects a covariant form for the action. It is conceivable that addition of terms involving covariant derivatives of the gauge field f contracted with the metric g or g+B may conspire to cancel these unwanted terms and reproduce the string amplitude.

In view of the large variety of such possible terms and the complication of these calculations, we have not been able to find a simple covariant variation of the action (151). The same difficulties arise for application of T duality on the action which would be a check of our result.

## Acknowledgments

We would like to thank M. Alishahiha and S. F. Hassan for useful conversations. F.A acknowledges discussion with L. Alvarez-Gaume.

Appendix A
Coefficients for Noncommutative D-brane

Here we presented the coefficient for scattering of two closed string from D-brane in the presence of $`B`$ field.

$`a_1`$ $`=`$ $`Tr(ϵ_1.D)Tr(ϵ_2.D)`$ (155)
$`a_2`$ $`=`$ $`Tr(ϵ_1^T.ϵ_2)`$ (157)
$`a_3`$ $`=`$ $`Tr(D.ϵ_1.D.ϵ_2)`$ (159)
$`a_4`$ $`=`$ $`Tr(ϵ_1.D)(k_1.ϵ_2.D.k_1+k_1.D.ϵ_2.k_1)+(12)`$ (161)
$`a_5`$ $`=`$ $`k_1.ϵ_2.D.ϵ_1D.k_2+k_2.ϵ_1.D.ϵ_2.D.k_1+k_1.D.ϵ_2.D.ϵ_1.k_2+k_2.D.ϵ_1.D.ϵ_2.k_1`$ (163)
$``$ $`k_2.D^T.ϵ_1^T.ϵ_2.D.k_1k_2.D.ϵ_1.ϵ_2^T.D^T.k_1`$ (165)
$`a_6`$ $`=`$ $`k_2.D^T.ϵ_1^T.ϵ_2.k_1+k_2.ϵ_1^T.ϵ_2.D.k_1k_1.ϵ_2.D.ϵ_1.k_2k_2.ϵ_1.D.ϵ_2.k_1`$ (167)
$`+`$ $`k_2.ϵ_1.ϵ_2^T.D^T.k_1+k_2.D.ϵ_1.ϵ_2^T.k_1`$ (169)
$`a_7`$ $`=`$ $`Tr(ϵ_1.D)(k_1.ϵ_2.k_1)+(12)`$ (171)
$`a_8`$ $`=`$ $`Tr(ϵ_1.D)(k_1.D.ϵ_2.D.k_1)+(12)`$ (173)
$`a_9`$ $`=`$ $`k_1.D.ϵ_2.D.ϵ_1.D.k_2+(12)`$ (175)
$`a_{10}`$ $`=`$ $`k_2.ϵ_1^T.ϵ_2.k_1+k_2.ϵ_1.ϵ_2^T.k_1`$ (177)
$`a_{11}`$ $`=`$ $`(k_1.ϵ_2.D.k_1+k_1.D.ϵ_2.k_1)(k_2.ϵ_1.D.k_2+k_2.D.ϵ_1.k_2)`$ (179)
$`+`$ $`(k_1.ϵ_2.k_1)(k_2.D.ϵ_1.D.k_2)+(k_1.D.ϵ_2.D.k_1)(k_2.ϵ_1.k_2)`$ (181)
$`a_{12}`$ $`=`$ $`(k_1.ϵ_2.k_1)(k_2.ϵ_1.D.k_2+k_2.D.ϵ_1.k_2)+(12)`$ (183)
$`a_{13}`$ $`=`$ $`(k_1.D.ϵ_2.D.k_1)(k_2.ϵ_1.D.k_2+k_2.D.ϵ_1.k_2)+(12)`$ (185)
$`a_{14}`$ $`=`$ $`(k_1.ϵ_2.k_1)(k_2.ϵ_1.k_2)`$ (187)
$`a_{15}`$ $`=`$ $`(k_1.D.ϵ_2.D.k_1)(k_2.D.ϵ_1.D.k_2).`$ (189)
Appendix B
Coefficients for commutative D-brane

When we turn the $`B`$ field off we must only change $`D_S^{ab}=D_0^{ab}=\eta ^{ab}`$ and $`D_S^{ij}=D_0^{ij}=\delta ^{ij}`$ and $`D_A=0`$ again we find the same amplitude as (54) by including these changes and replacing $`a_n`$ coefficients with $`b_n`$, where

$`b_1`$ $`=`$ $`Tr(ϵ_1.D_0)Tr(ϵ_2.D_0)`$ (190)
$`b_2`$ $`=`$ $`Tr(ϵ_1^T.ϵ_2)`$ (192)
$`b_3`$ $`=`$ $`Tr(D_0.ϵ_1.D_0.ϵ_2)`$ (194)
$`b_4`$ $`=`$ $`Tr(ϵ_1.D_0)(k_1.ϵ_2.D_0.k_1+k_1.D_0.ϵ_2.k_1)+(12)`$ (196)
$`b_5`$ $`=`$ $`k_1.ϵ_2.D_0.ϵ_1.D_0.k_2+k_2.ϵ_1.D_0.ϵ_2.D_0.k_1+k_1.D_0.ϵ_2.D_0.ϵ_1.k_2+k_2.D_0.ϵ_1.D_0.ϵ_2.k_1`$ (198)
$``$ $`k_2.D_0.ϵ_1^T.ϵ_2.D_0.k_1k_2.D_0.ϵ_1.ϵ_2^T.D_0.k_1`$ (200)
$`b_6`$ $`=`$ $`k_2.D_0.ϵ_1^T.ϵ_2.k_1+k_2.ϵ_1^T.ϵ_2.D_0.k_1k_1.ϵ_2.D_0.ϵ_1.k_2k_2.ϵ_1.D_0.ϵ_2.k_1`$ (202)
$`+`$ $`k_2.ϵ_1.ϵ_2^T.D_0.k_1+k_2.D_0.ϵ_1.ϵ_2^T.k_1`$ (204)
$`b_7`$ $`=`$ $`Tr(ϵ_1.D_0)(k_1.ϵ_2.k_1)+(12)`$ (206)
$`b_8`$ $`=`$ $`Tr(ϵ_1.D_0)(k_1.D_0.ϵ_2.D_0.k_1)+(12)`$ (208)
$`b_9`$ $`=`$ $`k_1.D_0.ϵ_2.D_0.ϵ_1.D_0.k_2+(12)`$ (210)
$`b_{10}`$ $`=`$ $`k_2.ϵ_1^T.ϵ_2.k_1+k_2.ϵ_1.ϵ_2^T.k_1`$ (212)
$`b_{11}`$ $`=`$ $`(k_1.ϵ_2.D_0.k_1+k_1.D_0.ϵ_2.k_1)(k_2.ϵ_1.D_0.k_2+k_2.D_0.ϵ_1.k_2)`$ (214)
$`+`$ $`(k_1.ϵ_2.k_1)(k_2.D_0.ϵ_1.D_0.k_2)+(k_1.D_0.ϵ_2.D_0.k_1)(k_2.ϵ_1.k_2)`$ (216)
$`b_{12}`$ $`=`$ $`(k_1.ϵ_2.k_1)(k_2.ϵ_1.D_0.k_2+k_2.D_0.ϵ_1.k_2)+(12)`$ (218)
$`b_{13}`$ $`=`$ $`(k_1.D_0.ϵ_2.D_0.k_1)(k_2.ϵ_1.D_0.k_2+k_2.D_0.ϵ_1.k_2)+(12)`$ (220)
$`b_{14}`$ $`=`$ $`(k_1.ϵ_2.k_1)(k_2.ϵ_1.k_2)`$ (222)
$`b_{15}`$ $`=`$ $`(k_1.D_0.ϵ_2.D_0.k_1)(k_2.D_0.ϵ_1.D_0.k_2).`$ (224)
Appendix C
One open and one closed bosonic string scattering

In this appendix we want to calculate scattering of one massless open string with one massless closed graviton string. In the bosonic case vertices for open and closed string are

$`V_c`$ $`=`$ $`ϵ_{\mu \lambda }D_{}^{\lambda }{}_{\nu }{}^{}:X^\mu (z_1)e^{ik_1.X(z_1)}::\overline{}X^\nu (\overline{z}_1)e^{ik_1.D.X(\overline{z}_1)}:,`$ (225)
$`V_o`$ $`=`$ $`\xi _\alpha (V^T)_{}^{\alpha }{}_{\rho }{}^{}:X^\rho (y)e^{2ik_2.V^T.X(y)}:,`$ (227)
where again we have used doubling trick for writing them. For momentum conservation relation we have

$$k_1^\mu +k_1.D^\mu +2k_2.V^{T\mu }=0,$$
(228)
and physical conditions for momentum and polarizations are

$`k_1.ϵ^\mu `$ $`=`$ $`0,k_1^2=0,ϵ_{}^{\mu }{}_{\mu }{}^{}=0`$ (229)
$`k_2.V^T.\xi `$ $`=`$ $`0,m_{open}^2=(2k_2.V^T)^2=0.`$ (231)
By using these two last equations and $`V^TV=\frac{1}{2}(\eta +D_S)`$ we find

$$k_1.D_S.k_1=\frac{1}{2}m_{open}^2=0.$$
(232)
By fixing SL(2,R) invariant we find for amplitude of open-closed scattering from D-brane

$`A_{OCD}=g_cg_oe^\lambda {\displaystyle d^2z_1𝑑yV_cV_o}|_{z=i,y=0}`$ (233)
(234)
$`d^2z_1dy(z_1y)(\overline{z}_1y)(z_1\overline{z}_1),`$ (235)
with $`(D.V)^{ab}=(V^T)^{ab}`$ and $`(D.V)^{ij}=\eta ^{ij}`$ after a little computation we find graviton-gauge field and graviton-scalar scattering. From this amplitude we read vertices as

$`(V_{ϵ_1A})^a`$ $``$ $`{\displaystyle \frac{\kappa c\sqrt{T_p}}{4}}\{2Tr(ϵ_1.D_S)k_1.V_A^a4k_1.D_S.ϵ_1.V_A^a+4k_1.D_A.ϵ_1.V_S^a`$ (236)
$``$ $`\alpha ^{}(k_1.D_S.ϵ_1.D_S.k_1+k_1.D_A.ϵ_1.D_A.k_1)k_1.V_A^a\}`$ (238)
$`(V_{ϵ_1\lambda })_i`$ $``$ $`{\displaystyle \frac{\kappa c\sqrt{T_p}}{4}}\{2Tr(ϵ_1.D_S)k_{1i}4k_1.D_S.ϵ_{1i}`$ (240)
$``$ $`\alpha ^{}(k_1.D_S.ϵ_1.D_S.k_1+k_1.D_A.ϵ_1.D_A.k_1)k_{1i}\},`$ (242)
which are exactly the same as (119) if one uses the on shell condition for the states in (119). The last terms in the vertices in (119) vanish upon using the massless condition for open strings, i.e., (232).

Note that the open string vertex operator in our calculation corresponds to noncommutative fields whereas we write the effective action in terms of commutative fields. The difference between them is the Siberg-Witten map. However for the linear open string field there is no difference between commutative and noncommutative fields.


text:
# A Young Very Low-Mass Object surrounded by warm dust

## 1 Introduction

The discovery of Brown Dwarfs (BDs) and objects with masses comparable to those of giant planets, well below the deuterium burning limit (M$`<`$13 MJ), “free-floating” in young stellar clusters (Zapatero-Osorio et al., 2000; Lucas & Roche, 2000) has opened an interesting debate on their origin. Do they form like ordinary stars from the collapse of molecular cores (Shu et al., 1987)? If so, the very existence of very low-mass objects and their mass function put strong constraints on star formation theories. Alternatively, BDs and isolated planetary mass objects may be stellar “embryos” ejected from multiple forming systems before reaching a stellar mass (Reipurth & Clarke, 2001), or they may form like planets by coagulation of dust particles and subsequent gas accretion within circumstellar protoplanetary disks (Lin et al., 1998). Young (proto)-planets could then be extracted or ejected by dynamical interactions from the forming planetary systems. In this scenario, isolated BDs and planetary mass objects are intrinsically different from stars; their study sheds no light on star formation theories, but provides instead a chance of studying the early evolution of giant planets where they can be observed in isolation, rather than very close to a much brighter star.

One way to shed light on the origin of very low mass objects is to ascertain their association with circumstellar disks, which are characteritics of stellar formation from the contraction of a molecular core. Deep images in the L band Muench et al. (2001) and in the mid-infrared (Persi et al., 2000; Bontemps et al., 2001) have shown that many very low luminosity objects have excess emission at these wavelengths, and detailed studies of some of them have proven that the central objects are bona-fide BDs. Their infrared excess is consistent with the presence of a surrounding disk similar to those found around more massive pre-main sequence stars (Comerón et al., 1998, 2000; Natta & Testi, 2001). These initial findings, albeit limited, seem to suggest that indeed BDs form like ordinary stars.

We report here the first results of a project aimed on one hand to improve our understanding of disks around BD, following the approach of in Natta & Testi (2001), and on the other hand to find evidence of a circumstellar disk around bona fide isolated planetary mass objects. We have used the Near-Infrared Camera and Spectrograph (NICS) on the 3.56m Telescopio Nazionale Galileo to acquire low-resolution (NIR) spectra of a sample of mid-infrared sources located within the $`\rho `$-Ophiuchi cloud Bontemps et al. (2001). Our target list included objects detected at 6.7 and 14.3 $`\mu `$m with the ISOCAM camera on board of ISO (Kessler et al., 1996; Cesarsky et al., 1996), having low effective temperature (Teff), luminosity (L) and extinction (AV) based on photometric or limited 2.2 $`\mu `$m spectroscopic estimates. The goal of our new observations was to obtain improved determinations of these parameters and to derive accurate values of masses and ages of the targets by comparison with theoretical evolutionary tracks. The results for the complete sample will be discussed elsewhere (Natta et al., 2002). In this Letter, we report on one of the sources, number 33 of the ISOCAM list of Bontemps et al. (2001), which is associated with the NIR source GY11 (Greene & Young, 1992). The substellar nature of this object was already proposed by Rieke & Rieke (1990) and confirmed by Comerón et al. (1998); Wilking et al. (1999). We derive a new, accurate spectral classification of GY11, and of its effective temperature and luminosity. Our data suggest that GY11 is a planetary mass object, with an infrared excess that can be roughly modeled as due to a circumstellar disk similar to those associated to T Tauri stars. These observations provide the first evidence that objects of such small mass actually form in a star-like manner, and thus that they are genetically different from “planets”.

## 2 Observations

A near-infrared low-resolution spectrum of GY11 was obtained with the Telescopio Nazionale Galileo on La Palma on July 9, 2001, using a 0$`\stackrel{}{\mathrm{.}}`$5 slit and the high-throughput low-resolution prism-based disperser unique to NICS (Baffa et al., 2001), the Amici device (Oliva, 2000); this setup offers a complete NIR spectrum, 0.85 to 2.35 $`\mu `$m, at R$``$100 accross the entire range, and it allows an accurate classification of faint and cool dwarfs (Testi et al., 2001). Instrumental and telluric correction was ensured by observations of A0 stars. The shape of the final spectrum was checked using near infrared photometric measurements from the 2MASS second incremental data release; synthetic magnitudes were computed using the appropriate transmission curves and compared with the source photometry, colors were found to be consistent with those of 2MASS to within 10%, as expected from typical uncertainties. To better constrain the values of the extinction, we also obtained optical i-band (0.77 $`\mu `$m) photometry at the ESO-La Silla 1.54m Danish Telescope using the DFOSC instrument. Photometric calibration was ensured by observations of a set of Landolt (1992) standard stars, converted into the Gunn system using the transformations given by Fukugita et al. (1996).

## 3 Central source parameters

Bontemps et al. (2001) associated the ISOCAM source 33 with a Class II object member of the $`\rho `$-Ophiuchi young stellar cluster known as GY11 (Greene & Young, 1992). The brown dwarf nature of GY11 has been suspected for some time (Rieke & Rieke, 1990). However, there is a large uncertainty in the literature as to the exact value of its photospheric parameters and mass. Bontemps et al. (2001) estimate bolometric luminosity and extinction to be L$`{}_{}{}^{}0.001`$ L, AV=2.7 mag from NIR photometry. Based on multiband infrared photometry and a 2.2$`\mu `$m low resolution spectrum, Wilking et al. (1999) estimate a spectral type M6.5, A$`{}_{\mathrm{V}}{}^{}`$5 mag, L$`{}_{}{}^{}`$0.002 L, and T$`{}_{eff}{}^{}`$2650 K. These authors noted that due to veiling caused by dust emission, the spectral type could easily be some 2–3 subclasses later, and the extinction significantly underestimated. In fact, Comerón et al. (1998) derive a higher value of AV=10 mag from broadband photometric measurements that include optical and infrared bands.

Our complete near infrared spectrum offers the possibility of a better estimate of the source parameters, as it allow us to use the global spectrum shape below 2 $`\mu `$m, a region which is less affected by the continuum veiling due to the dust emission. Given the expectation that the surface gravity of very young BDs shouls be similar to sub-giants, we derive the photospheric parameters by comparison with field dwarfs spectra and model atmospheres with appropriate surface gravity, as suggested by the evolutionary models (Comerón et al., 2000). We first derive extinction and spectral type by matching the observed GY11 spectrum with that of field dwarfs in the solar neighborhood (Testi et al., 2002), obtained with the same instrumental set-up and reddened using the Cardelli et al. (1989) extinction law most appropriate for Ophiucus (RV=4.2; Fig. 1a). We try to provide the best fit to the global shape of the spectrum, with particular attention to the shape of the H-band, the J-band features and the drop due to water vapor absorption at the red edge of the J-band. Overall, the best spectral match is found with the field dwarf with spectral type M8.5 and extinction A$`{}_{\mathrm{V}}{}^{}`$7.0 mag. Lower values of AV (by $`1`$ mag) offer a better match of the spectrum with later dwarf spectra (M9–L0), but are not consistent with the broad band optical measurements (see inset in Fig. 4). A higher value of the extinction causes a too steep rise of the spectrum below 1.2 $`\mu `$m. Field dwarfs with spectral types earlier than M7.5 show large deviations from the observed shape of the H-band and the drop at 1.3 $`\mu `$m. Given the uncertainties of a classification based on objects with very different surface gravity, we expect our classification to be accurate within one spectral class and the visual extinction estimate within one magnitude.

As a second step, in order to derive an estimate of the photospheric effective temperature (Fig. 1a), we compare the observed GY11 spectrum, with reddened, appropriate surface gravity, $`\mathrm{log}_{10}(g)`$=3.5, model atmospheres (Allard et al., 2000; Chabrier et al., 2000). The best estimate of the effective temperature is $``$2400$`\pm `$100 K. Higher temperature models offer a better match of the H-band shape, but underestimate the drop near 1.3 $`\mu `$m and the global shape of the spectrum at J-band. The derivation of the effective temperature of young dwarfs based on theoretical synthesis of the near infrared spectrum is very uncertain (Lodieu et al., 2002); however, our value of Teff for an object of spectral type M8.5 is consistent with the spectral type vs. effective temperature scale discussed by Wilking et al. (1999), and only marginally higher than the latest effective temperature scales derived for field dwarfs (Leggett et al., 2001).

To estimate the luminosity (L) of the object, we used the 2MASS J-band magnitude, dereddened by A$`{}_{\mathrm{V}}{}^{}7.0`$ mag, and the bolometric correction derived from the best fitting (2400 K) atmospheric model. The value of this “theoretical” bolometric correction is nearly identical to the empirical value adopted by Wilking et al. (1999). We derive a value of L$`{}_{}{}^{}`$0.008 L$`{}_{}{}^{}\pm `$30%.

Using the L and Teff values derived above, we can compare the position of GY11 in the Hertzprung-Russell diagram with the predictions of theoretical pre-main sequence evolutionary models. In Figure 2 we show this comparison for the latest release of evolutionary tracks from three leading groups in the theory of pre-main sequence evolution of substellar objects. In spite of the relatively large uncertainties on L and Teff, and on the limited accuracy of pre-main sequence evolutionary tracks at these ages and masses, we confirm that GY11 is a young ($`\tau <1`$ Myr), very low mass object, probably below or very close to the deuterium burning limit, with a best mass estimate in the range 7 to 12 MJupiter.

## 4 Infrared Excess and Disk Models

GY11 is the lowest mass object with a clearly detected infrared excess. It is detected by ISOCAM in the two broad-band filters LW2 and LW3 ($`\lambda _{eff}`$ 6.7 and 14.3 $`\mu `$m, respectively) used by (Bontemps et al., 2001) in their $`\rho `$ Oph survey, as well as in the three intermediate-band filters, SW1, LW1, LW4 ($`\lambda _{eff}`$=3.6, 4.5 and 6.0 $`\mu `$m, respectively), used by Comerón et al. (1998) in their pointed observations of optically identified candidate brown dwarfs. The ISOCAM measurements in the broad- and narrow-bands are in good agreement, within the flux calibration uncertainties, which we assume to be $`20`$%.

As usually with ISOCAM, the $``$6′′ beam includes multiple sources seen in higher resolution near-infrared images, which may contribute to the observed fluxes. Figure 3 compares a Ks image of the region around GY11 extracted from the VLT/ESO archive (originally observed as part of ESO proposal 63.I-0691) and the ISOCAM LW1 ($`\lambda _{eff}`$=4.5 $`\mu `$m) image from the ISO archive (Comerón et al., 1998). The mid-infrared emission peaks very close to the position of GY11. Although a small contamination from the NIR source $``$8′′ to the east is possible, we think that most of the mid-infrared observed flux comes from GY11; a similar conclusion was also reached by Comerón et al. (1998).

In Figure 4, we show the spectral energy distribution (SED) of GY 11 at all wavelengths and compare it to that of an irradiated, flared disk similar to those that reproduce the observed characteristics of TTauri systems (Chiang & Goldreich, 1997). The disk has a dust mass of 1 Earth mass ($``$3% of the mass of the central object, for an assumed gas-to-dust mass ratio of 100) and is heated by a a central source with the GY11 temperature, luminosity and mass. We show the predicted SED when the disk extends inward to the stellar surface (solid line) and when it has an inner hole of 3 stellar radii (dotted line). More details on the disk models can be found in Natta & Testi (2001) and Natta et al. (2002). The agreement between observed and predicted fluxes is rather good, especially for the disk with the large inner hole. In particular, both models predict total (star+disk) fluxes that in the J, H, K bands are smaller than the calibrated TNG fluxes by 15% at most.

As an independent check, we computed optical and NIR broad-band magnitudes from the model-predicted SED. They are compared in the inset of Figure 4 with the observed dereddened magnitudes in i (this paper), R,I,L (Comerón et al., 1998), J,H,K (2MASS). The agreement is again quite good.

The ISOCAM measurements, especially that at 14.3 $`\mu `$m, have large error bars, and one should not overinterpret them. However, is of some interest to point out that, if indeed the mid-infrared excess is due to disk emission, the disk must be flared. Therefore, dust and gas must be well mixed, as in the majority of pre-main–sequence stars, and no major settling of the dust onto the disk midplane has occurred during the lifetime of GY11. The disk must be optically thick to mid-infrared radiation; this however sets only a lower limit to the disk mass of roughly 10-5-10-6 M depending on the exact value of the dust mid-infrared opacity and surface density profile. Note that the disk mass has to be very small; if we assume the ratio of the disk mass to the mass of the central object typical of TTS ( 0.03), then the disk mass is about $`3\times 10^4`$ M, and the disk contains only 1 Earth mass of dust. As a consequence, the accretion rate (if any) is also likely to be low, with an average value over the lifetime of the object that cannot exceed 3$`\times `$10-10 M yr-1 (for an age of 1 Myr). The accretion luminosity is also small, about 40 times lower than the luminosity of the photosphere. A direct determination of the disk mass can be derived from (sub)millimeter wavelength observations. We predict for GY11 a 1.3mm flux of about 0.6 mJy, which is well below the upper limit set by the survey of Motte et al. (1998), but within the expected capabilities of the ALMA millimeter array.

## 5 Conclusions

The results presented in this letter show evidence that a young isolated planetary mass objects in $`\rho `$-Oph, with mass of about 10 MJ, is surrounded by warm dust, possibly distributed on a disk similar in properties to those around young brown dwarfs and T Tauri stars. The implications of this finding, that should be confirmed by higher spatial resolution mid-infrared observations, and should be extended to a large sample of similar objects, are profound, since it gives a clear indication that isolated BDs and even planetary mass objects form like stars and are not produced in a planet-like fashion within protoplanetary disks around more massive objects, and later ejected by dynamical interactions. Isolated BDs and planetary mass objects are thus an extension of the stellar and substellar sequence to very low masses and have different origins from “planets”.

This work is partly based on observations collected at the Italian Telescopio Nazionale Galileo, Canary Islands, Spain, at the European Southern Observatory telescopes on La Silla and Paranal observatories, Chile, and on data obtained by the European Space Agency Infrared Space Observatory. This publication makes use of data products from the Two Micron All Sky Survey, which is a joint project of the University of Massachusetts and the Infrared Processing and Analysis Center/California Institute of Technology, funded by the National Aeronautics and Space Administration and the National Science Foundation. This work was partly supported by ASI grant ARS 1/R/27/00 to the Osservatorio di Arcetri.