text:
# Extinction in the Galaxy from surface brightnesses of ESO-LV galaxies: testing ’standard’ extinction maps

## 1 Introduction

We have introduced in our previous paper (Chołoniewski & Valentijn 1999, hereafter CV) a new method for the determination of the extinction in our Galaxy. The method uses surface brightnesses of external galaxies in the B and R bands as listed in The Surface Photometry Catalogue of the ESO-Uppsala Galaxies (Lauberts & Valentijn, 1989, hereafter ESO-LV). The first draft of this method has been published in our earlier paper (Chołoniewski & Valentijn 1991).

The main purpose of the present paper is to compare our derived extinction values with recently published maps of extinction by Schlegel, Finkbeiner & Davis (1998), hereafter SFD, and with the frequently used map of Burstein & Heiles (1978), hereafter BH (see also Burstein & Heiles 1982).

## 2 The method

Our extinction determination (fully described in CV) employs the surface brightnesses of external galaxies in the B and R bands: $`\mu _B`$, $`\mu _R`$. Basically, our method produces the relative extinction compared to an overall mean - extinction with an unknown zero-point. The formula for the relative extinction (in B band) is simply a linear combination of $`\mu _B`$ and $`\mu _R`$:

$$A_B=\frac{\mu _Bs\mu _R}{1rs}c.$$
(1)
In order to use equation (1) one has to know three parameters: $`r`$, $`s`$ and $`c`$.

The parameter $`r`$ describes the ratio of extinction in the R and the B band ($`r=A_R/A_B`$) and is assumed to be constant. Its recent literature value is 0.61 (see CV for references) while we derived in CV two new estimates: 0.62 and 0.64. As a reasonable compromise we adopt throughout this paper $`r=0.62`$.

The inverse of the parameter $`s`$ describes the slope of the linear relation between surface brightnesses $`\mu _B`$ and $`\mu _R`$. The $`c`$ parameter is introduced in order to maintain zero-point issues. Both parameters $`s`$ and $`c`$ depend on morphological type $`T`$, so they have been computed (using equations 7 and 10 in CV) separately for every morphological type.

In this paper we will consider several different subsamples. Extinction within every such subsample has been computed using the set of values $`s(T)`$ and $`c(T)`$ obtained from the same set of data. The $`s(T)`$ and $`c(T)`$ coefficients for the most important two subsamples used in ths paper are in Table 1.

We use in this paper the extinction in B band as described in equation (1) and denote it as $`A_B(CV)`$.

## 3 The samples

For our analysis we use surface brightnesses at the radius of half total B light in B and R bands from ESO-LV. We exclude from the sample those galaxies which have morphological classifications suspected to be extinction dependent (marked in ESO-LV with $`T_{flag}`$ equal to 4). We also reject galaxies which have excessive (probably wrong) colours: $`\mu _B\mu _R`$ smaller than zero or greater than 2.1.

Since we focus in this paper on the comparison of our extinction with SFD and BH data, we reject additionally those galaxies for which BH or SFD extinction values are not available.

The largest complete subsample of galaxies of ESO-LV can be made by selecting galaxies which have visual apparent diameter $`D_{org}`$ greater or equal to 60 arcsec. It contains, after applying the rejections described above, 7974 galaxies (sample ”A”).

As mentioned in CV, the completeness limit of ESO-LV galaxies is morphological type dependent and a universal criterion, valid for every morphological type, is selecting galaxies with a visual diameter limit larger than 100 arcsec. We have used such more restricted sample for all the computations presented in CV. We use it also here as sample ”B” (after rejections described above).

Results described in Sections 4 and 5 show that more rigorousely defined sample ”B” produces slightly more accurate extinction per galaxy than the sample ”A”. However the sample ”A” is three times larger than the sample ”B” what, at least in part, compensate its slightly larger dispersion.

Table 2 contains a summary of the definitions of sample ”A” and sample ”B”.

Since the ESO-LV galaxy catalogue covers the Southern sky ($`\delta <17.5^o`$) our analysis refers to this part of the hemisphere.

## 4 The accuracy

Equation (1) represents an estimator of the foreground relative extinction for an individual external galaxy. It is important to know its uncertainty (standard error). In order to obtain this, we have divided the whole sky into squares with size $`\mathrm{\Delta }`$ degrees and computed the average variance of the extinction inside these squares using the formula given by the so called one-way analysis of the variance theory (see e. g. Fish 1962). This average variance reflects the variations of the true extinction inside the squares with size $`\mathrm{\Delta }`$ and the standard error of the extinction estimator expressed in equation (1). So, when the size of the squares $`\mathrm{\Delta }`$ tends to zero the average variance of the extinction should tend to the standard error of the extinction produced by our method.

Figure 1 shows the average variance of extinction as a function of $`\mathrm{\Delta }`$. The minimum value for $`\mathrm{\Delta }`$ which we applied was one degree. For smaller values of $`\mathrm{\Delta }`$ a too large fraction of studied squares contain only one galaxy (such squares can not be taken into account in the one-way analysis of variance).

As we expect, the average variance has minimum for the smallest applied value of $`\mathrm{\Delta }`$ (one degree). For sample ”A” the standard error of our extinction in $`A_B`$ is 0.43 magnitude, while for sample ”B” this is 0.40 magnitude, which corresponds to a standard error in $`E(BV)`$ of approximately 0.10 magnitude (for $`A_B/E(BV)=4.3`$). Sample ”B” produces relative extinction with slightly higher accuracy than sample ”A”.

BH used for the calibration of their extinction map B-V colours of 131 globular clusters and RR Lyrae stars. SFD used for the calibration of their extinction map B-R colours of 106 brightest cluster ellipticals and B-V colours of 389 elliptical galaxies with measured $`Mg_2`$ index (505 objects in total).

Both BH and SFD report that their calibrators show a residual scatter in B-V, with respect to calibration regression line, of approximately 0.03 magnitude.

Our extinction estimator, when applied to photographically measured surface brightnesses of galaxies in two bands as listed in the ESO-LV catalogue, has three times larger standard error than the calibrators used by BH and SFD. This is an important disadvantage (at least as long as we apply it to ESO-LV photometrical data). But there is one important advantage of our extinction estimator - it can be applied to many more objects since we can apply the method, at present, to 7974 galaxies (sample ”A”) from the ESO-LV catalogue.

## 5 The correlation

We have computed the Pearson, Spearman and Kendall correlation coefficients (see Press, Teukolsky, Vetterling & Flannery 1992 for definitions and software) between our extinction and extinction given by SFD and BH and for the cosecans law:

$$A_B=A_0\mathrm{csc}|b|,$$
(2)
where $`b`$ denotes Galactic latitude. The computation have been performed for sample ”A” and sample ”B” (see Table 3). The parameters $`s(T)`$ and $`c(T)`$ have been computed separately for every sample (see Table 1).

All three correlation coefficients for both samples are the largest for SFD extinction and the smallest for the cosecans law. The extinction of BH is always between these two extreme results.

The coefficients are generally higher for sample ”B” than for sample ”A” what suggests that sample ”B” produces more accurate extinction than sample ”A”.

Since the sample ”B” is a subsample of the sample ”A” the correlation coefficients for ”A” and ”B” are not statistically independent. In order to produce a set of statistically independent correlations we divide the sample ”A” into six subsamples:

1. $`60arcsecD_{org}<80arcsec`$ (N=3876)
2. $`80arcsecD_{org}<100arcsec`$ (N=1648)
3. $`100arcsecD_{org}<120arcsec`$ (N=718)
4. $`120arcsecD_{org}<140arcsec`$ (N=647)
5. $`140arcsecD_{org}<160arcsec`$ (N=298)
6. $`160arcsecD_{org}`$ (N=787) ,

and compute the parameters $`s(T)`$ and $`c(T)`$ separately for every subsample. As a result of this procedure we have six statistically independent correlation coefficients - see Figs 2, 3 and 4 for results. As before, the correlations are the largest for SFD, smaller for BH and the smallest for cosecans law.

## 6 Correction of the BH’s extinction zero point

The formulae of BH produces for some regions of the sky extinction less than zero (for the samples analyzed in this paper the minimum value of $`A_B(BH)`$ extinction is -0.12 magnitude). In spite of BH’s instructions to set these values to zero we have actually used these negative values and found that $`A_B(CV)`$ is for them significantly smaller than for $`A_B(BH)0`$ (see upper panel of Figs 7 and 8). This means that the BH extinction (in the B band) was underestimated by 0.12 magnitude - just the absolute value of the minimum value of $`A_B(BH)`$ extinction. This is in approximate agreement with SFD who discovered a similar offset of 0.09 magnitude. We use in the regression analysis presented in the next Section the corrected BH’s extinction: $`A_B(BH)_C=A_B(BH)+0.12`$ instead of $`A_B(BH)`$ itself.

## 7 The linear regression

In the ideal case there would be linear dependence with slope equal to one between our relative extinction estimate (CV) and the extinction of SFD and BH (corrected).

Since our extinction values are relative, with an arbitrary zero-point, the constant term of this linear dependence should not be equal to zero. The constant, multiplied by $`1`$, should be added to our relative extinction to transform it to the absolute extinction.

We have fitted the straight lines (using the least squares method) taking as independent variables extinction of SFD and BH and as dependent variable our estimate of relative extinction (CV). We have found the following regression coefficients for sample ”A”:

$$A_B(CV)=0.662(\pm 0.028)A_B(SFD)0.189(\pm 0.010)$$
(3)
$$A_B(CV)=0.555(\pm 0.026)A_B(BH)_C0.176(\pm 0.010)$$
(4)
and for sample ”B”:

$$A_B(CV)=0.741(\pm 0.043)A_B(SFD)0.225(\pm 0.016)$$
(5)
$$A_B(CV)=0.608(\pm 0.040)A_B(BH)_C0.206(\pm 0.017)$$
(6)
where in brackets $`1\sigma `$ errors are given. The differences between slopes and constant terms computed for sample ”A” and ”B” are only marginally larger than the combined errors. In the forthcoming we use their averages.

A graphical presentations of the regression lines are shown in Figs 5-8. In order to investigate whether the postulate about linear dependence is valid, the regression lines are shown together with row data (lower panels) and with averages of $`A_B(CV)`$ computed for 0.05 magnitude bins of $`A_B(SFD)`$ and $`A_B(BH)`$ (upper panels).

The slopes of the regression lines are definitely less than one: for SFD the slope is circa 0.7 while for BH it is circa 0.6. The constant terms for both SFD and BH are approximately the same: -0.20 magnitude. This defines the zero point of our results: adding 0.20 magnitude to our relative extinction transforms it to the absolute extinction.

When we introduce our absolute extinction into equations 3 - 6, the constant terms in all 4 equations gets close to zero, now setting the relation between our (absolute) extinction and SFD’s and BH’s extinction. Thus we conclude: SFD overestimate extinction by a factor of $`0.7^11.4`$ while BH by a factor of $`0.6^11.7`$.

Up to now five papers reported similar results, namely: that SFD extinction is about 1.4 times too large. Stanek (1998b) obtained, using colours of low galactic latitude globular clusters, that the overestimation factor is 1.35 (see also Stanek 1998a). Arce & Goodman (1999a, 1999b) analyzed extinction in the Taurus region using four independent methods and found that the factor is 1.3 - 1.5. Gonzalez, Fruchter & Dirsch (1999) obtain extinction in the small field around GRB 970228. They found using two methods $`A_V=0.55`$ while $`A_V(SFD)=0.78`$. The ratio of these two numbers give again a factor 1.4. Our finding that SFD overestimate extinction is also supported by Ivans et al. (1999) and von Braun & Mateo (2001).

Some kind of doubt about the correctness of the calibration is also in original SFD paper where we can find as the comment to their Fig. 6 the statement that ”A slight trend in the residuals is evident for both BH and DIRBE/IRAS corrections, in the sense that the highest reddening values appear to be overestimated”.

Inspecting Figs 5-8 demonstrate a general linear dependence between our relative extinction estimate and the extinction of SFD and BH. However, some minor, but statistically significant, deviations are clearly present, especially for $`A_B(SFD)`$ and $`A_B(BH)`$ less than 0.5 magnitude.

## 8 Galactic latitude dependence

Unfortunately, we can not use our method of extinction determination, as applied to the ESO-LV galaxy catalogue, to produce a new high resolution extinction map and to compare it with SFD and BH maps. This is because our data are too sparse (less than one galaxy per square degree) and their accuracy is too low ($`\sigma (E(BV))0.10`$ per galaxy) mainly because of instrinsic scatter of the surface brightness of galaxies.

But the quality of our data is good enough to evaluate their galactic latitude dependence. We show this dependence for our absolute extinction (equal to the relative extinction, as defined in equation 1, plus 0.20 magnitude) together with SFD, corrected BH and the cosecans low - see Fig. 9. All four solutions have been averaged inside 5 degrees galactic latitude bins in the points where ESO-LV galaxies are (sample ”A”). We use $`A_o=0.10`$ for the cosecans law (equation 3) to match as close as possible to our solution.

Fig. 9 shows that our absolute extinction is always greater than zero confirming the value of the zero-point computed in Section 7.

As one can see in Fig. 9 our solution as well as SFD and BH mimic quite well the classic cosecans law and indicate considerable extinction near the galactic pole. The differences between our results and SFD and BH are the largest near the galactic equator and at the northern hemisphere.

Since we find that both SFD and the (corrected) BH extinction standards overestimate Galactic extinction by a factor 1.4 and 1.7 respectively, we show the same data as in Fig.9 but with SFD and corrected BH extinction divided by these factors (or, equivalently, multiplied by 0.7 and 0.6 respectively) - see Fig. 10. The better agreement of our solution with the rescaled SFD and BH data is evident, especially near the Galactic equator ($`b0`$), confirming the need for rescaling SFD and BH extinction. But even for the rescaled data statistically significant differences between our results and SFD and BH, although smaller, still exist. Especially our data exhibit a South - North asymmetry near the galactic equator ($`|b|<40^o`$) with more extinction in the Southern Galactic hemisphere which is not visible in SFD and BH data.

## 9 Discussion

Our extinction estimator (introduced in CV) definitely indicates that the new extinction map of SFD is more realiable than the old one of BH. The historical cosecans law is in this competition on the last place. This result has been obtained using six separate, statistically independent, sets of data.

The superiority of the SFD extinction map over the BH map have been demonstrated by computing correlation coefficients with our extinction results. However, the correlation coefficients are not sensitive to the amplitude of variation of the input data nor its zero-point. In order allow for further, more specific, comparisons we have performed a linear regression analysis between our relative extinction and SFD’s and BH’s extinction. This analysis provides us the zero-point of our extinction (equal to 0.20 magnitude) which allows us to transform our relative extinction into absolute extinction. We have showed that, in comparison to our absolute extinction, SFD overestimate extinction by a factor of 1.4. This is in agreement with five other authors and considerably changes our view on the amplitude of the Galactic extinction.

Superiority of SFD over BH reddening map, as we report in this paper, does not mean that the first is an ideal result - we have discovered some significant differences between our extinction and SFD when analyzing their Galactic latitude dependence even after correcting SFD extinction by dividing it by 1.4 factor. One possible source of these differences is that SFD assume that the extinction is strictly proportional to the dust column density what need not be true - the extinction to dust ratio can vary across the sky and may also depend on the wavelength.

Our results are important for creating reliable extinction standards and demonstrate the correctness and usefulness of our extinction estimator. They can be also regarded as a stimulus for applying our extinction estimator to other, larger and more accurate galaxy catalogues, particularly thoose expected from new wide field imaging surveys,

Future applications of our method to other databases may produce maps with a courser resolution. At present the method applied to ESO-LV data is unable to generate the extinction map with both sufficient resolution and accuracy. Our present method should be rather taken as new extinction calibrator. But using the method to larger and more precise galaxy catalogues may result into stand-alone high resolution extinction maps.

## Acknowledgments

The part of this work was done during the stay of the authors at European Southern Observatory (Garching, Germany). The authors thanks Andris Lauberts for collaboration about the project.


format: text

text:
# Classical and quantum: some mutual clarifications

## 1 Introduction

The boundary between classical and quantum physics is a fascinating region, that in my opinion, in spite of several important explorations, has not delivered its deepest treasures. I will try to motivate this optimistic view on the future of research in physics by presenting some remarkable links between ”quantum” and ”classical” physics.

We have often read in old textbooks or popular books that quantum physics is the physics of the ”infinitely small”, while the ”everyday world” is governed by classical physics. This might be considered, and probably is, a very naive view. Bohr maintained that the distinction between the classical measurement device and the quantum measured system is arbitrary but is necessary for our understanding. The current view of the physicists working in the field, is that everything is quantum, the classicality emerging through interactions (the ”everyday world” appears then to be classical because of the huge amount of interacting particles involved). This last view, the emergence of classical behavior simply because of interaction, is nowadays unchallenged by observation: no phenomenon can be produced as an evidence of its falseness. Thus, it is a satisfactory description for any practical purpose, although one may question its validity as a Weltanschauung.

The links between ”classical” and ”quantum” that am I going to present here are of a different nature: they do not seem to arise simply from many interacting quantum objects that together exhibit classical behavior. The first link (Section 2) deals with quantum cryptography111This was the topic of my talk during the Workshop Multiscale Methods in Quantum Mechanics, Rome, 16-20 December, 2002.. The second link (Section 3) shows how typical ”quantum” notions (namely, the no-cloning theorem and the idea of weak measurements with post-selection) manifest themselves in phenomena that can be described using an entirely classical theory of light, and that can be revealed using the devices of ordinary telecommunication networks.

## 2 Classical bounds in quantum cryptography

Quantum cryptography is nowadays the most developed application of quantum information theory . A more exact name for quantum cryptography would be quantum key distribution (QKD): the goal of the quantum processing is to establish a secret key between two distant partners, Alice and Bob, avoiding the attacks of a possible eavesdropper Eve. Once a common secret key is established, Alice and Bob will encode the message using classical secret-key protocols, known to be unbreakable even if the message is sent on a public authenticated channel.

We describe (fig. 1) an implementation of QKD that uses a source of entangled states, and for clarity we speak of two-dimensional quantum systems (qubits). Alice has a source that produce a pair of qubits in the maximally entangled state

$`|\mathrm{\Phi }_{AB}`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2}}}\left(|+z|+z+|z|z\right)`$ (1)
$`=`$ $`{\displaystyle \frac{1}{\sqrt{2}}}\left(|+x|+x|x|x\right).`$
She keeps one qubit and forwards the other one to Bob. In the absence of Eve: (i) if Alice and Bob measure the same observable, either $`\sigma _z`$ or $`\sigma _x`$, they obtain the same result, the same random bit; (ii) if one of the partners measures $`\sigma _z`$ and the other $`\sigma _x`$, they obtain completely uncorrelated random bits. This protocol is repeated a large number of times. At the end, the items in which Alice and Bob have performed different measurements are discarded later by public communication on the classical channel, leaving Alice and Bob with a list of perfectly correlated random bit: the secret key. This is what happens in the absence of the spy.

Eve can in principle do whatever she wants on the quantum channel. The security of QKD comes from the fact that, since any measurement or interaction perturbs the state, Eve’s intervention cannot pass unnoticed: Alice and Bob know that someone is spying. Two situations are then possible. (I) Eve has got a ”small” amount of information; in this case, Alice and Bob can process their data in order to obtain a shorter but completely secret key. Such classical protocols are the object of important studies in classical information theory. (II) Eve has got ”too much” information; then Alice and Bob discard the whole key. This may seem a failure, but it is not: it simply means that the spy has no other alternative than cutting the channel and forbid any communication; and this achieves the goal of cryptography, because no encrypted message is ever sent that the spy could decode.

It is then important to quantify the words ”small” and ”too much” in the previous discussion: what is the amount of Eve’s information that Alice and Bob can tolerate, that is, at what critical value are they obliged to discard the whole key? Here is where remarkable links appear between classical and quantum information.

We refer to fig. 2. Because of Eve’s intervention, before any measurement the quantum system is in a three-party entangled state of Alice-Bob-Eve, $`\mathrm{\Psi }_{ABE}`$. Alice and Bob on their own share the mixed state $`\rho _{AB}`$, obtained from $`\mathrm{\Psi }_{ABE}`$ by partial trace on Eve’s system. Two procedures are then possible:

(a) The one that we described above: all the partners make a measurement, ending in a classical probability distribution $`P(A,B,E)`$. Then, Alice and Bob apply classical protocols (advantage distillation) in order to extract a shorter secret key, that is, a shorter list of bits distributed according to a new distribution $`P^{}(A,B)P^{}(E)`$ in which Eve is uncorrelated and $`P^{}(A=B)=1`$.

(b) If the state $`\rho _{AB}`$ is entangled, Alice and Bob can delay any measurement and process many copies of $`\rho _{AB}`$, to obtain a smaller number of copies of $`|\mathrm{\Phi }_{AB}`$ — and in this case, automatically Eve is uncorrelated. This procedure is known as entanglement distillation, and is one of the fundamental processes of quantum information. Once Alice and Bob have $`|\mathrm{\Phi }_{AB}`$, the measurement provide them immediately with the secret key.

Having understood this, we can state the main results that have been obtained:

* Classical advantage distillation of $`P(A,B,E)`$ is possible for bits if and only if quantum entanglement distillation is possible for the state $`\rho _{AB}`$ (which is equivalent of asking that $`\rho _{AB}`$ is entangled in the case of qubits). This was demonstrated by Gisin and Wolf when Eve uses the so-called optimal individual attack , and has been recently extended to all individual attacks .
* The same holds for dits ($`d`$-valued random variables) and qudits ($`d`$-dimensional quantum systems), under Eve’s individual attack that is supposed to be the optimal one . The demonstration is more involved because not all entangled states of two qudits are distillable.
* If $`\rho _{AB}`$ is entangled enough to violate a Bell inequality, then a secret key can be extracted from $`P(A,B,E)`$ in an efficient way, that is, using only one-way communication. This was first proven in Ref. ; for the state-of-the-question, see . A similar result holds for a multi-partite scheme of key distribution known as ”quantum secret sharing” .

Mainly because Eve’s optimal attack is not generally known, there are still several open questions. The most important ones are reviewed in the last section of Ref. .

This concludes my first ”unconventional” link between the classical and the quantum worlds: at the level of information processing, specifically of the extraction of a secret key from an initially noisy distribution/state, the critical parameters are exactly the same, irrespective whether the purification of the correlations is performed at the quantum or at the classical level. Moreover, a typically quantum feature such as the violation of Bell’s inequalities is related to the efficiency of the classical key-extraction procedure.

## 3 Quantum physicists meet telecom engineers

This section is devoted to another kind of unconventional link between the classical and the quantum world. I prefer let the examples speak first and draw my conclusions later.

### 3.1 No-cloning theorem

The first example concerns the no-cloning theorem, a well-known primitive concept of quantum information . In its basic form, it states that no evolution (or more generally, no trace-preserving completely positive map) can bring $`|\psi |0`$ onto $`|\psi |\psi `$ for an unknown state $`|\psi `$.

This no-go theorem has motivated the search for an optimal quantum cloner: given that perfect cloning is impossible, what is the best one can do? Optimal cloners have indeed been found and widely studied; all the meaningful references can be found in any basic text on quantum information, e.g. . In the course of these investigations, a sharp link has been found between optimal cloning and the well-known phenomenon of amplification of light: stimulated emission of light in a given mode (perfect amplification, or cloning) cannot be done without spontaneous emission (random amplification). Suppose that $`N`$ photons enter an amplifier, and at the output one selects the cases in which exactly $`M>N`$ photons are found: it turns out that this process realizes the optimal quantum cloning from $`N`$ to $`M`$ copies. The fidelity of the amplification is the ratio between the mean number of photons found in the initial mode (i.e. the mean number of correct copies) and the total number of copies, $`M`$ here. The optimal fidelity is found to be

$`_{NM}^{opt}`$ $`=`$ $`{\displaystyle \frac{MN+M+N}{M(N+2)}}.`$ (2)
We realized an experimental demonstration of optimal cloning using the principle just described to clone the polarization of light . Polarized light of intensity $`\mu _{in}`$ is sent into a conventional fiber amplifier (exactly as those that are used in telecommunications); at the output, we have an intensity $`\mu _{out}`$; we separate the input polarization mode from its orthogonal, and measure the fidelity. The theoretical prediction for this experiment is

$`\overline{}_{\mu _{in}\mu _{out}}`$ $`=`$ $`{\displaystyle \frac{Q\mu _{out}\mu _{in}+\mu _{out}+\mu _{in}}{Q\mu _{out}\mu _{in}+2\mu _{out}}}`$ (3)
where $`Q[0,1]`$ is a parameter related to the quality of the amplification process. The experimental results are in excellent agreement (fig. 3).

It is striking to notice that for $`Q=1`$, formula (3) is exactly the same as (2). Its meaning is however rather different. In our experiment, everything is classical: the laser light is in a coherent state, therefore it can be described by a classical field; the amplifier is ”classical” in the sense that it transforms coherent states into coherent states. The quantities $`\mu _{in}`$ and $`\mu _{out}`$ that appear in eq.(3) are not photon numbers as the $`N`$ and $`M`$ of eq. (2), but mean values, that have been measured using an intensity detector. As I said above, all the devices (source, fibers, amplifier, detectors) are typical of telecom engineering.

### 3.2 Weak measurements with post-selection

The second example is related to the meaning and physics of the measurement process, a widely debated topic of the foundations of quantum mechanics. In this context, Aharonov, Vaidman and others introduced the notion of weak measurement with post-selection , sometimes called the ”two-state formalism” of quantum mechanics. The authors’ intention in studying this formalism is strongly motivated by interpretational issues; that is why most physicists tend to look at these concepts as artificial ones, introduced on purpose, and that do not add anything to physics itself. To date, apart from some experiments that were designed on purpose, only some complex tunnelling phenomena had received some clarification through this formalism.

We have found however  that this formalism does apply to something that exists and is extremely widespread: once again, the optical telecommunication network. Telecom engineers are performing weak measurements with post-selection in basically all that they do! A modern optical network is composed of different devices connected through optical fibers. With respect to polarization, two main physical effects are present. The first one is polarization-mode dispersion (PMD): due to birefringency, different polarization modes propagate with different velocities; in particular, the fastest and the slowest polarization modes are orthogonal. PMD is the most important polarization effect in the fibers. The second effect is polarization-dependent loss (PDL), that is, different polarization modes are differently attenuated. PDL is negligible in fibers, but is important in devices like amplifiers, wavelength-division multiplexing couplers, isolators, circulators etc.

The first piece of the connection we want to point out is the following: a PMD element performs a measurement of polarization on light pulses (Fig. 4). In fact, PMD leads to a separation $`\delta \tau `$ of two orthogonal polarization modes in time. If $`\delta \tau `$ is larger than the pulse width $`t_c`$, the measurement of the time of arrival is equivalent to the measurement of polarization — PMD acts then as a ”temporal polarizing beam-splitter”. However, in the usual telecom regime $`\delta \tau `$ is much smaller than $`t_c`$. In this case, the time of arrival does not achieve a complete discrimination between two orthogonal polarization modes anymore; but still, some information about the polarization of the input pulse is encoded in the modified temporal shape of the output pulse. We are in a regime of weak measurement of the polarization. The formulae introduced by Aharonov and co-workers are recovered by measuring the mean time of arrival, that is, the ”center of mass” of the output pulse.

The second piece of the connection defines the role of PDL: a PDL element performs a post-selection of some polarization modes. Far from being an artificial ingredient, post-selection of some modes is the most natural situation in the presence of losses: one does always post-select those photons that have not been lost! This would be trivial physics if the losses were independent of any degree of freedom, just like random scattering; but in the case of PDL, the amount of losses depends on the meaningful degree of freedom, polarization. An infinite PDL would correspond to the post-selection of a precise polarization mode (a pure state, in the quantum language); a finite PDL corresponds to post-selecting different modes with different probabilities (a mixed quantum state).

In summary: by tuning the PMD, we can move from weak to strong measurements of polarization; the PDL performs the post-selection of a pure or of a mixed state of polarization. Any telecom network, devices connected by fibers, is performing ”weak measurements with post-selection”. Just as in the example of quantum cloning discussed above, all this can be (and is actually) described by the classical theory of light.

### 3.3 The fundamental role of entanglement

We have shown that two results thought to be ”typically quantum”, namely the no-cloning theorem and the theory of weak measurements, can be demonstrated with classical light and standard telecom devices. The key for a deep understanding is the conceptual distinction between two superposition principles: the classical one, which is dynamical (fields superpose because Maxwell’s equations are linear); and the quantum one, which is kinematical: states are superposed. These two superposition principles, at the level of interpretation, have a completely different meaning. However, it may difficult to tell which is acting in a real situation.

I would like to extend this observation to stress the fundamental role of entanglement. In the traditional textbooks of quantum mechanics, entanglement has been considered a kind of a side-issue, and in any case a derived notion: if a composed quantum system is described by a tensor product of Hilbert spaces, and if the superposition principle has to hold in this total space, then non-factorizable states must appear. In other words, traditionally one starts with the quantum physics of the single system, states the superposition principle in this context, and derives the existence of entanglement a posteriori. While this may be an unavoidable approach for a didactic course, I don’t think that the view so conveyed is really the whole story. Students meeting the Stern-Gerlach experiment in their ”quantum physics” course fail to realize that they have studied its analog with light polarization some months before, in their lectures on ”classical electrodynamics”. But what does it mean? Is a spin $`\frac{1}{2}`$ classical? Or is polarization a quantum intruder in the classical theory of light?

The solution comes by noticing that the Stern-Gerlach experiment is not the only experimental result involving the spin! The spins of the electrons explain the Mendeleev table via the Pauli exclusion principle, a principle that has no classical analogue; different cross-sections have been observed in scattering experiments, according to whether the full spin was in a symmetric or in the anti-symmetric state; spins couple coherently to one another in nuclear magnetic resonance, or to the polarization of photons in atomic physics… The list may rapidly become very large. But if we give a second glance to this list, we notice that it contains only phenomena in which two or more quantum systems are involved. And if we finally notice that ”coherent interaction” means ”entanglement”, we have the solution: we know that a single spin $`\frac{1}{2}`$ is a quantum object because we observe the consequences of its entanglement with other spins or other degrees of freedom. The same can be said for polarization.

The difference between the ”classical superposition principle of waves” and the ”quantum superposition principle of states” lies in the fact that only the second gives rise to entanglement. If we’d have only the quantum physics of the single particle (the Stern-Gerlach experiment, Young’s double-slit…), the most economic solution would be to adopt once for all the de Broglie-Bohm view of a real particle guided by a hidden wave — and we’d lose all the fascinating view of the world that is inspired by quantum physics.

## 4 Conclusion

The main message I wanted to convey is that ”classical” and ”quantum” physics — or information — are tightly connected. Specifically, I have discussed how in the analysis of the security of quantum cryptography, we discover numbers that come from the analysis of the security of classical cryptography (Section 2); and how experiment with classical light and standard telecom devices can provide demonstrations of the no-cloning theorem and of the theory of weak measurements with post-selection (Section 3).

In this text, I reported on results obtained at the University of Geneva under the direction of prof. Nicolas Gisin, together with Antonio Acín, Nicolas Brunner, Daniel Collins, Sylvain Fasel, Grégoire Ribordy and Hugo Zbinden. I also benefited from several discussions with François Reuse and Antoine Suarez.


text:
# Calculation of CP Violation in Non-leptonic Kaon Decay on the Lattice

## 1 INTRODUCTION

In the investigations of the Standard Model, a very important issue is the theoretical treatment of $`K\pi \pi `$ decay to the accuracy such that comparison with the experimental results is possible. In particular, the ratio of direct and indirect CP violation, $`ϵ^{}/ϵ`$, has been determined experimentally EXPERIMENT  in recent years and theoretical calculation is desired to test Kobayashi-Maskawa theory. In the theoretical calculation, numerical simulation of lattice QCD is the most systematic method to estimate the non-perturbative effect of QCD which is the main source of the error. Using the operator product expansion, the interaction in this decay is written as $`H_W=\frac{G_FV_{us}V_{ud}^{}}{\sqrt{2}}_iW_i(\mu )Q_i,`$ where the coefficients $`W_i`$ contain the effects of the energy scales higher than the matching point $`\mu `$ and can be obtained perturbatively Buras . Non-perturbative QCD effects will appear in $`K\pi \pi `$ matrix elements of the local operators $`\pi \pi \left|Q_i\right|K`$, which should be calculated on the lattice. A couple of years ago, CP-PACS and RBC Collaboration CPPACSep ; RBCep  calculated all of the matrix elements using the domain-wall fermion formalism Kaplan ; FurmanShamir  to realize the chiral symmetry required in this calculation and reported small and negative values of $`ϵ^{}/ϵ`$ in conflict with the experimental result. Another work using staggered fermion has obtained a larger negative value PekurovskyKilcup . In these works, however, there are several uncontrolled systematic errors such as 1) the effect of the small, but non-zero, chiral symmetry breaking, 2) the effect of finite lattice spacing, 3) the effect of the perturbative treatment of the charmed quark in the matrix elements, 4) quenching effect, and 5) $`K\pi \pi `$ matrix elements are obtained from $`K\pi `$ and $`K0`$ (vacuum) by using lowest order chiral perurbation theory BernardSoni .

In order to examine all of these systematic errors except the fifth one, we are performing two types of numerical simulation with domain-wall fermion and the DBW2 gluonic action RBCDBW2  to improve the chiral symmetry on the lattice. “Numerical Simulation I” is the quenched calculation including directly the effect of the charm quark on the lattice. The degree of chiral symmetry breaking is decreased by a factor 1/10 compared with the previous work of RBC Collaboration. In addtion, we are generating gauge configurations with $`N_f=2`$ dynamical quarks RBCdyn  in “Numerical Simulation II.” In the rest of this article, we present the contents of these numerical simulations and report preliminary results of the matrix elements which numerically dominate $`ϵ^{}/ϵ`$ and kaon B-parameter $`B_K`$.

## 2 NUMERICAL SIMULATION I

We are generating gauge configurations on a relatively fine $`24^3\times 48`$ lattice with the scale $`a^1=2.86(9)`$. The residual quark mass $`m_{\mathrm{res}}`$ which measures the chiral symmetry breaking is as small as $`\stackrel{<}{_{}}`$ 0.3 MeV. Since quark mass $`m_fa`$ is introduced as a parameter of the boundary condition in the fifth dimension in domain-wall QCD, the localization of chiral modes on domain-walls in the fifth dimension tends to fail for a heavy quark mass $`m_f`$. However, our small lattice spacing made the value of $`m_ca`$ acceptable as a domain-wall fermion: $`m_ca`$ 0.45. We found that, around this value, the behavior of wave function in the fifth dimension is qualitatively same as the case of much smaller quark mass.

At the lowest order of chiral perturbation theory, $`K\pi \pi `$ matrix elements are in proportion to $`K\pi `$ matrix elements calculated on the lattice. For $`i=1`$$`6,9,10`$, these matrix elements are related as,

$`\pi ^+\pi ^{}\left|Q_i^{(I)}\right|K^0`$ $`=`$ $`{\displaystyle \frac{m_K^2m_\pi ^2}{\sqrt{2}f}}\left[{\displaystyle \frac{1}{m_{\mathrm{PS}}^2}}\pi ^+\left|Q_i^{(I)}\right|K^+|_{(\mathrm{subt})}+𝒪(p^2)\right],`$ (1)
in particular, for $`\mathrm{\Delta }I=1/2`$, or $`I=0`$, subtraction of a lower dimension operator is needed:

$`\pi ^+\left|Q_i^{(0)}\right|K^+|_{\mathrm{subt}}`$ $`=`$ $`\pi ^+\left|Q_i^{(0)}\alpha _iQ_{\mathrm{sub}}\right|K^+,`$ (2)
$`Q_{\mathrm{sub}}=(m_s+m_d)\overline{s}d`$ $``$ $`(m_sm_d)\overline{s}\gamma _5d,\alpha _i=0\left|Q_i^{(0)}\right|K^0/0\left|Q_{\mathrm{sub}}\right|K^0`$ (3)
For $`i=7,8`$, we have the simpler relation

$`\pi ^+\pi ^{}\left|Q_i^{(I)}\right|K^0`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2}f}}\pi ^+\left|Q_i^{(I)}\right|K^++𝒪(p^2).`$ (4)
In particular, $`Q_6^{(0)}`$ and $`Q_8^{(2)}`$ have the largest contribution to $`ϵ^{}/ϵ`$, numerically. In FIG. 1, results of $`K\pi `$ matrix elements of these operators are plotted. In particular, the left panel, which is the example with $`m_ca=0.40`$, shows that there is a severe cancellation in the subtraction in (2) for $`Q_6^{(0)}`$. Since the slope of the subtracted matrix elements have the error of $`200\%`$, we cannot quote a result of $`K\pi \pi `$ matrix element with the current statistics. And its depencence on $`m_ca`$ is not visible, so far.

Lattice value of kaon B parameter which is defined by

$`B_K={\displaystyle \frac{\overline{K}\left|Q_{\mathrm{\Delta }S=2}\right|K}{8/3\overline{K}\left|A_\mu \right|00\left|A_\mu \right|K}},`$ (5)
is plotted in FIG. 2 as a function of $`m_fa`$. In this figure, the fit function used is $`B_K=\xi _0[1+Cm_fa\mathrm{ln}(m_fa)]+\xi _1m_fa`$ with $`C`$ taken from analytic result Sharpe . The physical result for $`B_K`$ can be obtained at $`m_f=m_s/2`$ (the filled symbol). To obtain the physical value, we are now calculating the $`Z`$ factor for $`B_K`$ by non-perturbative renormalization proposed in NPR  and the preliminary result is roughly consistent with the previous works CPPACSBK ; RBCep .

## 3 NUMERICAL SIMULATION II

Since the dynamical simulation demands much more resources than a quenched one, dynamical domain-wall QCD has been explored by only our collaboration RBCdyn , so far. In this calculation, we generated three kinds of gauge configuration on a $`16^3\times 32`$ lattice with the mass of the sea quark ($`u`$ or $`d`$ quark) being $`m_{\mathrm{sea}}a=0.02,0.03`$ and $`0.04`$. For each series of configurations, $`K\pi `$ and $`K0`$ matrix elements are calculated in the same way as Simulation I with the five valence quark masses $`m_{\mathrm{val}}=0.01`$$`0.05`$, and basic parameters $`a^11.8`$ GeV and $`m_{\mathrm{res}}3`$ MeV are obtained. FIG. 3 shows the same matrix elements as in FIG. 1 as an example of the case of $`m_{\mathrm{sea}}=0.03`$. Although the signal seems to be reasonable, we need much more statistics to take correct chiral limit $`m_{\mathrm{sea}}a=m_{\mathrm{val}}0`$ using three data points with $`m_{\mathrm{sea}}a=m_{\mathrm{val}}=0.02,0.03`$ and $`0.04`$. $`B_K`$ at the physical point such that $`m_{\mathrm{sea}}=m_{u/d}`$ and $`m_s120`$ MeV will be also obtained after a careful treatment of our data GoltermanLeung  and non-perturbative renormalization which is now under calculation.

We thank RIKEN, BNL and the U.S. DOE for providing the facilities essential for the completion of this work.


text:
# A fully polarizable and dissociable potential for water

## Abstract

A new classical interaction potential for water simulations is presented. Water is modeled as a fully dissociable set of atoms with a point dipole, determined self-consistently, on every oxygen atom. The oxygen polarizability is not fixed but depends on the geometry of the system. We show that, in spite of the limited number of free parameters, the model reproduces the geometrical and vibrational properties of microclusters in a satisfactory way.

journal: Chemical Physics Letters

and

Water, being arguably the most important liquid in our life, has always attracted a great deal of attention from physicists and chemists. It is also a rather difficult substance to model, and, in spite of vast improvements in numerical techniques, ab-initio simulations are not yet able to simulate more than a hundred molecules for a reasonable time. Many classical potentials have been proposed, but very few of them are able to take into account all the important structural and dynamical features of water. Dissociability, for instance, is important in order to describe bulk water and its hydration and proton-transfer properties. Polarizability is crucial in the description of structural properties.

In this Letter we propose a new dissociable and polarizable potential for water and validate it by means of the study of the geometrical and vibrational properties of the water molecule and of the water dimer and trimer; results on larger clusters, and a full comparison with other potentials, will be presented in a full paper. The validation process we used is especially stringent as we predict a range of physical properties much larger than usually done in this kind of studies. We believe this gives a better guarantee of transferability to our potential than the usual procedures. Our potential contains a small number of parameters and is based on reasonable physical assumptions, which include some quantum effects previously neglected. Its aim is to reunite the advantages of dissociable and polarizable potentials while at the same time keeping a comparatively simple and physically transparent form.

We assume that, in the molecule, most of the electric charge of each hydrogen is transferred to the oxygen. We also assume that the electronic polarizability of the molecule is entirely due to the oxygen. Several models already exist that allow one to treat successfully ionic crystal structures (see for instance ), and we will start from there. The potential we propose has the following form:

$$U=U_{ZZ}+U_{BM}+U_{DD}+U_{VW}+U_{ZD}+U_{SR}.$$

In the term

$$U_{ZZ}=\frac{1}{2}\underset{ij}{}\frac{Z_iZ_j}{r_{ij}}$$
(1)
$`Z_o`$ and $`Z_h`$ indicate ionic charges and are considered as adjustable parameter, bound by the charge neutrality constraint $`Z_o+2Z_h=0`$ and $`\text{r}_{ij}=\text{r}_i\text{r}_j,`$ where ri is the position of the i-th nucleus. The Born-Mayer repulsive term

$$U_{BM}=\frac{1}{2}\underset{ij}{}f(\rho _i+\rho _j)exp\left(\frac{R_i+R_jr_{ij}}{\rho _i+\rho _j}\right)$$
(2)
includes the adjustable parameters $`f,R_o,R_h,\rho _o,\rho _h`$. The term

$$U_{DD}=\frac{1}{2}\underset{iO}{}\underset{jO,ji}{}\left(\frac{\text{p}_i\text{p}_i}{r_{ij}^3}\frac{3(\text{p}_i\text{r}_{ij})(\text{p}_j\text{r}_{ij})}{r_{ij}^5}\right)+\underset{jO}{}\frac{p_j^2}{2\alpha _o}$$
(3)
describes dipole-dipole interaction, $`\text{p}_i`$ being a point dipole located on the $`i`$th oxygen, and the bare oxygen polarizability $`\alpha _o`$ is taken as a further parameter; since hydrogen is almost entirely deprived of electrons, it is considered unpolarizable. The Van der Waals term is written as

$$U_{VW}=\frac{1}{2}\underset{i}{}\underset{ji}{}\frac{c_ic_j}{r_{ij}^6}$$
(4)
while the term

$$U_{ZD}=\underset{jO}{}\underset{i,ij}{}\text{p}_jZ_i\frac{\text{r}_{ij}}{r_{ij}^3}$$
(5)
describes the charge-dipole interaction. The term

$$U_{SR}=\underset{iH}{}\underset{jO}{}\text{p}_jB(r_{ij})\frac{\text{r}_{ij}}{r_{ij}},B(r_{ij})=\frac{F}{\alpha _o}fexp(\frac{R_{sr_i}+R_{sr_j}r_{ij}}{\rho _i+\rho _j})$$
(6)
is taken from Ref., where the polarizability in the shell model is studied. Intuitively, this term reduces the polarizability of oxygen by taking into account the interaction between its electronic charge and that of the closest hydrogen atoms, so it is not surprising that it has the same form of Eq. 2. In principle the values considered for $`R_{sr_o}+R_{sr_h}`$ (only the sum of these parameters is relevant) are independent of $`R_o+R_h`$, but in practice they are only slightly different, and in some previous studies  they were set as equal.

In almost all this work we set $`\rho _h=0`$, that is we neglected the short-range hydrogen-hydrogen interactions given by Eqs. 2 and 6. In short, our potential is characterized by 11 independent parameters, which are listed in table 1 together with their optimized values.

It is worth noting that the optimized value of $`\alpha _o`$ lies approximately midway between the polarizabilities of oxygen and of the water molecule. We fitted several physical quantities we considered of primary interest: of the monomer, the geometrical data, the vibrational frequencies and the dipole moment, all of them known experimentally. Of the clusters, the geometrical data relative to the equilibrium configurations, which are known experimentally and sometimes from ab-initio calculations. The equilibrium geometries were found using a simple steepest-descent algorithm, with $`\text{p}_i`$ determined self-consistently, while the vibrational frequencies were obtained via numerical calculation and diagonalization of the dynamical matrix. After fixing the parameters of the potential, as a further test we calculated the cluster binding energies, the vibrational frequencies and some configurations considered as local minima of the potential energy as reported also in some ab-initio studies, comparing all these data with those found in the literature.

In the rest of this paper we shall use the following symbols: $`\mu `$ for the dipole moment of the molecule; $`\nu _{ss}`$, $`\nu _{as}`$ and $`\nu _b`$ for the molecule normal modes, that is, respectively, symmetric stretching, asymmetric stretching and bending; $`\overline{\mu }(molec)`$ is the average molecular dipole moment in the clusters.The subscripts $`b`$ and $`f`$ indicate the bond and free hydrogens, respectively.

The results for the molecule are shown in table 2. As one can see, the overall agreement with the experimental data is good, the only quantity in error of more than 15% being $`\nu _b`$. The frequencies $`\nu _{ss}`$ and $`\nu _{as}`$ are in the wrong order, a feature common in our potential, but given the small difference between them this does not look too worrying. Attempts made to fix the discrepancy led to an oxygen-oxygen repulsion that is too small.

The numerical results on the dimer are collected in table 3. The ground-state geometry is, qualitatively, the usual one; $`\theta _d`$ is the angle between the bisector of the H-O-H angle of the donor molecule and the O-O direction, $`\theta _a`$ is the same for the acceptor. $`D_e`$ is the dimer dissociation energy.

We found that, as $`c_o`$ and $`R_o`$ vary, when the oxygen-oxygen separation increases then $`\alpha _o`$ decrease by about the same amount, and vice versa: this is clearly an electrostatic effect due to the attraction of the hydrogens in the acceptor molecule and the oxygen of the donor molecule. In addition, the angle $`\theta _a`$ increases, as one would expect, as the molecular dipole moments decrease and tend not to align. The excessive value of $`\theta _a`$ is therefore a price we have to pay in order to obtain a dipole moment not too high. We also verified that, as $`d(OO)`$ increases, $`D_e`$ decreases. It is thus not surprising that, since $`d(OO)`$ is overestimated, $`D_e`$ is underestimated.

Result for the dimer normal modes are shown in table 4. For their definition we follow Ref. and their identification Refs . The ordering of the intermolecular frequencies we find is not in complete agreement with experimental or ab initio data; it is the same found by , with the exception of the “O-O stretch” mode. The experimental data show that the intramolecular frequencies are not much different from those of the monomer; the main difference consists of an increase of the bending frequencies and a decrease of the symmetric and asymmetric stretching frequencies. These trends, confirmed by ab initio calculations ( and ), are well reproduced in our results.

The equilibrium geometry of the trimer is shown in fig.1 and the numerical data are collected in table 5. The longest side of the triangle corresponds to the smallest H-bond angle. This is characteristic of our potential. We obtained two relative minima, shown in fig. 2 and 3. The first is 0.06 eV above the energy in the absolute minimum, the second 0.15 eV. Their ordering in energy is the same as in the ab initio calculations , respectively 0.04 and 0.24 eV.

As an illustration of the overall quality of our potential, in Table 6 we show the trends of two important quantities — the average oxygen-oxygen distance and the average molecular dipole moment — with increasing number $`n`$ of molecules in the cluster. To make trends clearer, for $`n<8`$ the lowest-energy cyclic clusters have been considered, even when they are not the absolute energy minima. It is clear that the trends from ab initio calculations are well reproduced and the absolute errors actually decrease with $`n`$.

In conclusion, we have shown that the model reproduces the basic physical properties of microclusters in a satisfactory way. In particular, we are able to obtain bond lengths and dipole moments within 10-20% of experimental and ab-initio values, and to reproduce qualitatively not only all the ground-state geometries, but also several local minima. This remains true when the potential is applied to larger clusters, as we will show in a forthcoming paper. It should be stressed that for almost none of the potentials found in the literature one can find a comparison with experimental or ab-initio data as extensive and thorough as ours. Moreover, the limited number of parameters we used makes it more likely that their values are close to the real ones. We therefore believe that our potential is a promising one with regard to transferability and accuracy.

This work has been funded by a MIUR-COFIN grant.


text:
# A measure of betweenness centrality based on random walks

## 1 Introduction

Over the years network researchers have introduced a large number of centrality indices, measures of the varying importance of the vertices in a network according to one criterion or another (Wasserman and Faust 1994; Scott 2000). These indices have proved of great value in the analysis and understanding of the roles played by actors in social networks,111“Actor” is the generic term used by sociologists to refer to a node in a social network. as well as by vertices in networks of other types, including citation networks, computer networks, and biological networks. Perhaps the simplest centrality measure is degree, which is the number of edges incident on a vertex in a network—the number of ties an actor has in social network parlance. Degree is a measure in some sense of the popularity of an actor. A more sophisticated centrality measure is closeness, which is the mean geodesic (i.e., shortest-path) distance between a vertex and all other vertices reachable from it.222Some define closeness to be the reciprocal of this quantity, but either way the information communicated by the measure is the same. Closeness can be regarded as a measure of how long it will take information to spread from a given vertex to others in the network.

Another important class of centrality measures is the class of betweenness measures. Betweenness, as one might guess, is a measure of the extent to which a vertex lies on the paths between others. The simplest and most widely used betweenness measure is that of Freeman (1977; 1979), usually called simply betweenness. (Where necessary, to distinguish this measure from other betweenness measures considered in this paper, we will refer to it as shortest-path betweenness.) The betweenness of a vertex $`i`$ is defined to be the fraction of shortest paths between pairs of vertices in a network that pass through $`i`$. If, as is frequently the case, there is more than one shortest path between a given pair of vertices, then each such path is given equal weight such that the weights sum to unity. To be precise, suppose that $`g_i^{(st)}`$ is the number of geodesic paths from vertex $`s`$ to vertex $`t`$ that pass through $`i`$, and suppose that $`n_{st}`$ is the total number of geodesic paths from $`s`$ to $`t`$. Then the betweenness of vertex $`i`$ is

$$b_i=\frac{\underset{s<t}{}g_i^{(st)}/n_{st}}{\frac{1}{2}n(n1)},$$
(1)
where $`n`$ is the total number of vertices in the network.333Alternatively, $`b_i`$ may be normalized by dividing by its maximum possible value, which it achieves for a “star graph” in which one central vertex is connected to every other by a single edge (Freeman 1979). We may, or may not, according to taste, consider the end-points of a path to fall on that path; the choice makes only the difference of an additive constant in the values for $`b_i`$. In this paper we will generally include the end-points.

Betweenness centrality can be regarded as a measure of the extent to which an actor has control over information flowing between others. In a network in which flow is entirely or at least mostly along geodesic paths, the betweenness of a vertex measures how much flow will pass through that particular vertex. Betweenness can be calculated for all vertices in time $`\mathrm{O}(mn)`$ for a network with $`m`$ edges and $`n`$ vertices (Newman 2001; Brandes 2001).

In most networks however, information (or anything else) does not flow only along geodesic paths (Stephenson and Zelen 1989; Freeman et al. 1991). News or a rumor or a message or a fad does not know the ideal route to take to get from one place to another; more likely it wanders around more randomly, encountering who it will. And even in a case such as the famous small-world experiment of Milgram (1967; Travers and Milgram 1969), or its modern-day equivalent (Dodds et al. 2003), in which participants are explicitly instructed to get a message to a target by the most direct route possible, there is no evidence that people are especially successful in this task. Thus we would imagine that in most cases a realistic betweenness measure should include non-geodesic paths in addition to geodesic ones.

Furthermore, by giving all the weight to the geodesic paths, and none to any other paths, no matter how closely competitive they are, the shortest-path betweenness measure can produce some odd effects. Consider the network sketched in Fig. 1a, for instance, in which two large groups are bridged by connections among just a few of their members. Vertices A and B will certainly get high betweenness scores in this case, since all shortest paths between the two communities must pass through them. Vertex C on the other will hand get a low score, since none of those shortest paths pass through it, taking instead the direct route from A to B. It is plausible however that in many real-world situations C would have quite a significant role to play in information flows. Certainly it is possible for information to flow between two individuals via a third mutual acquaintance, even when the two individuals in question are themselves well acquainted.

To address these problems, Freeman et al. (1991) suggested a more sophisticated betweenness measure, usually known as flow betweenness, that includes contributions from some non-geodesic paths. Flow betweenness is based on the idea of maximum flow. Imagine each edge in a network as a pipe that can carry a unit flow of some fluid. We can ask what the maximum possible flow then is between a given source vertex $`s`$ and target vertex $`t`$ through these pipes. In general the answer is that more than a single unit of flow can be carried between source and target by making simultaneous use of several different paths through the network. The flow betweenness of a vertex $`i`$ is defined as the amount of flow through vertex $`i`$ when the maximum flow is transmitted from $`s`$ to $`t`$, averaged over all $`s`$ and $`t`$.444Technically, this definition is not unique, because there need not be a unique solution to the flow problem. To get around this difficulty, Freeman et al. define their betweenness measure as the the maximum possible flow through $`i`$ over all possible solutions to the $`st`$ maximum flow problem, averaged over all $`s`$ and $`t`$. Maximum flow from a given $`s`$ to all reachable targets $`t`$ can be calculated in worst-case time $`\mathrm{O}(m^2)`$ using, for instance, the augmenting path algorithm (Ahuja et al. 1993), and hence the flow betweenness for all vertices can be calculated in time $`\mathrm{O}(m^2n)`$.555One can do somewhat better, particularly on networks like those discussed here in which all edges have the same capacity, by using more advanced algorithms. See Ahuja et al. (1993).

In practical terms, one can think of flow betweenness as measuring the betweenness of vertices in a network in which a maximal amount of information is continuously pumped between all sources and targets. Necessarily, that information still needs to “know” the ideal route (or one of the ideal routes) from each source to each target, in order to realize the maximum flow. Although the flow betweenness does take account of paths other than the shortest path (and indeed need not take account of the shortest path at all), this still seems an unrealistic definition for many practical situations: flow betweenness suffers from some of the same drawbacks as shortest-path betweenness, in that it is often the case that flow does not take any sort of ideal path from source to target, be it the shortest path, the maximum flow path, or another kind of ideal path.

Moreover, like the shortest-path measure, flow betweenness can give counterintuitive results in some cases. Consider for example the network sketched in Fig. 1b, which again has two large groups joined by a few contacts. In this case, the maximum flow from one group to the other is clearly limited to two units, one unit flowing through each of vertices A and B. Vertex C will, in this case, get a low betweenness score, even though the path through C may be as short or shorter than that through A or B. Once again, it is plausible that in practical situations C would actually play quite a significant role.

In this paper, therefore, we propose a new betweenness measure, which might be called random-walk betweenness. Roughly speaking, the random-walk betweenness of a vertex $`i`$ is equal to the number of times that a random walk starting at $`s`$ and ending at $`t`$ passes through $`i`$ along the way, averaged over all $`s`$ and $`t`$. This measure is appropriate to a network in which information wanders about essentially at random until it finds its target, and it includes contributions from many paths that are not optimal in any sense, although shorter paths still tend to count for more than longer ones since it is unlikely that a random walk becomes very long without finding the target. In some sense, our random-walk betweenness and the shortest-path betweenness of Freeman (1977) are at opposite ends of a spectrum of possibilities, one end representing information that has no idea of where it is going and the other information that knows precisely where it is going. Some real-world situations may mimic these extremes while others, such as perhaps the small-world experiment, fall somewhere in between. In the latter case it may be of use to compare the predictions of the two measures to see how and by how much they differ: if they differ little, then either is a reasonable metric by which to characterize the system; if they differ by a lot, then we may need to know more about the particular mode of information propagation in the network to make meaningful judgments about betweenness of vertices.

Our random-walk betweenness can, as we will show, be calculated for all vertices in a network in worst-case time $`\mathrm{O}((m+n)n^2)`$ using matrix methods, making it comparable in its computational demands with flow betweenness.

Some other centrality measures based on random walks merit a mention in this context, although none of them are betweenness measures. Bonacich’s power centrality (Bonacich 1987) can be derived in a number of ways, but one way of looking at it is in terms of random walks that have a fixed probability $`\beta `$ of dying per step. The power centrality of vertex $`i`$ is the expected number of times such a walk passes through $`i`$, averaged over all possible starting points for the walk. The random-walk centrality introduced recently by Noh and Rieger (2003) is a measure of the speed with which randomly walking messages reach a vertex from elsewhere in the network—a sort of random-walk version of closeness centrality. The information centrality of Stephenson and Zelen (1989) is another closeness measure, which bears some similarity to that of Noh and Rieger. In essence it measures the harmonic mean length of paths ending at a vertex $`i`$, which is smaller if $`i`$ has many short paths connecting it to other vertices.

The outline of this paper is as follows. In Sec. 2 we define in detail our random-walk betweenness and show how it is calculated. We introduce the measure first using an analogy to the flow of electrical current in a circuit, and then show that this is equivalent also to the flow of a random walk. In Sec. 3 we give a number of examples of applications of our measure, first to networks artificially designed to pose a challenge for the calculation of betweenness, and then to various real-world social networks, including a collaboration network of scientists, a network of sexual contacts, and Pagdett’s network of intermarriages between prominent families in 15th century Florence. In Sec. 4 we give our conclusions.

## 2 Random-walk betweenness

In this section we give the definition of our random-walk betweenness measure and derive matrix expressions that allow it to be calculated rapidly using a computer. For pedagogical purposes, we will take a slightly circuitous route in developing our ideas. We start by introducing a definition of our betweenness measure that does not use random walks but instead is based on current flow in electrical circuits. This definition is simple and intuitive and makes for easy calculations. Later we introduce the random-walk definition of our measure and prove that the two definitions are the same. The developments of this section follow similar lines to a previous presentation we have given on methods for hierarchical clustering (Newman and Girvan 2003).

### 2.1 A current flow analogy

Consider, then, an electrical circuit created by placing a unit resistance on every edge of the network of interest, as shown in Fig. 2. One unit of current is injected into the network at a source vertex $`s`$ and one unit extracted at a target vertex $`t`$, so that current in the network as a whole is conserved. We now define the current-flow betweenness of a vertex $`i`$ to be the amount of current that flows through $`i`$ in this setup, averaged over all $`s`$ and $`t`$.

Let $`V_i`$ be the voltage at vertex $`i`$ in the network, measured relative to any convenient point. Kirchhoff’s law of current conservation states that the total current flow into or out of any vertex is zero, which implies that the voltages satisfy the equations

$$\underset{j}{}A_{ij}(V_iV_j)=\delta _{is}\delta _{it},$$
(2)
for all $`i`$, where $`A_{ij}`$ is an element of the adjacency matrix thus:

$$A_{ij}=\{\begin{array}{cc}\hfill 1& \text{if there is an edge between }i\text{ and }j\text{,}\hfill \\ \hfill 0& \text{otherwise,}\hfill \end{array}$$
(3)
and $`\delta _{ij}`$ is the Kronecker $`\delta `$:

$$\delta _{ij}=\{\begin{array}{cc}\hfill 1& \text{if }i=j\text{,}\hfill \\ \hfill 0& \text{otherwise.}\hfill \end{array}$$
(4)
Noting that $`_jA_{ij}=k_i`$, the degree of vertex $`i`$, we can write Eq. (2) in matrix form as

$$(𝐃𝐀)𝐕=𝐬,$$
(5)
where $`𝐃`$ is the diagonal matrix with elements $`D_{ii}=k_i`$ and the source vector $`𝐬`$ has elements

$$s_i=\{\begin{array}{cc}\hfill +1& \text{for }i=s\text{,}\hfill \\ \hfill 1& \text{for }i=t\text{,}\hfill \\ \hfill 0& \text{otherwise.}\hfill \end{array}$$
(6)
We cannot simply invert the matrix $`𝐃𝐀`$ to get the voltage vector $`𝐕`$, because the matrix (which is called the graph Laplacian) is singular: the vector $`𝐕=(1,1,1,\mathrm{})`$ is always an eigenvector with eigenvalue zero because voltage is arbitrary to within an additive constant, and since the determinant is the product of the eigenvalues, it follows that the determinant is always zero. Mathematically, this says that one of the equations in our system of $`n`$ equations is redundant. (Physically, it is telling us that current is conserved.) To fix the problem we need only choose one equation, any equation, and remove it from the system, to get a matrix we can invert. This operation is made most simple if we simultaneously choose to measure our voltages relative to the corresponding vertex. Thus, let us measure voltages relative to some vertex $`v`$, and remove the $`v`$th equation, which means removing the $`v`$th row of $`𝐃𝐀`$. Since $`V_v=0`$, we can also remove the $`v`$th column, giving a square $`(n1)\times (n1)`$ matrix, which we denote $`𝐃_v𝐀_v`$. Then

$$𝐕=(𝐃_v𝐀_v)^1𝐬.$$
(7)
The voltage of the one missing vertex $`v`$ is, by definition, zero. To represent this, let us now add a $`v`$th row and column back into $`(𝐃_v𝐀_v)^1`$ with values all equal to zero. The resulting matrix we will denote $`𝐓`$. Then, using Eq. (6), the voltage at vertex $`i`$ for source $`s`$ and target $`t`$ is given in terms of the elements of $`𝐓`$ by

$$V_i^{(st)}=T_{is}T_{it}.$$
(8)
The current flowing through the $`i`$th vertex is given by a half of the sum of the absolute values of the currents flowing along the edges incident on that vertex:

$$I_i^{(st)}=\frac{1}{2}\underset{j}{}A_{ij}|V_i^{(st)}V_j^{(st)}|=\frac{1}{2}\underset{j}{}A_{ij}|T_{is}T_{it}T_{js}+T_{jt}|,\text{for }is,t\text{.}$$
(9)
As noted, this expression does not work for the source and target vertices, for which one also has to take account of the current injected and removed from the network, but these vertices necessarily have a current flow of exactly one unit, so one can simply write

$$I_s^{(st)}=1,I_t^{(st)}=1.$$
(10)
(Alternatively, if one is adopting the convention under which the end-points of a path are not considered part of that path, then one should set these two currents to 0 rather than 1.) Then the betweenness is the average of the current flow over all source-target pairs:

$$b_i=\frac{\underset{s<t}{}I_i^{(st)}}{\frac{1}{2}n(n1)}.$$
(11)
If the network has more than one component, then the procedure described here should be repeated separately for each component.

The inversion of the matrix takes time $`\mathrm{O}(n^3)`$, while the evaluation of Eq. (11) takes time $`\mathrm{O}(mn)`$ for each vertex or $`\mathrm{O}(mn^2)`$ for all of them. Thus the total running time to calculate the current-flow betweenness for all vertices is $`\mathrm{O}((m+n)n^2)`$, or $`\mathrm{O}(n^3)`$ on a sparse graph. This is comparable with the time for calculation of the flow betweenness, although slower than the fastest algorithms for shortest-path betweenness. In our experience, the calculation is tractable for networks up to about $`\mathrm{10\hspace{0.17em}000}`$ vertices using typical desktop computing resources available at the time of writing.666In fact, as computer hardware stands at present, one is more likely to run out of memory than time, the memory requirements for matrix inversion being $`\mathrm{O}(n^2)`$, which means a gigabyte or more for a $`\mathrm{10\hspace{0.17em}000}\times \mathrm{10\hspace{0.17em}000}`$ matrix. It is possible that larger systems could be tackled using specialized sparse-matrix inversion methods, although there is a penalty in running time to be paid for doing this.

This current-flow betweenness measure seems an intuitively reasonable one. Current will flow along all paths from source to target, but more along shorter than longer ones, the shorter ones offering less resistance than the longer. And vertices that lie on no path from source to target, those that sit in a cul-de-sac off to the side of the network, get a betweenness of zero, which is also sensible. However, there is no special reason to believe that the flow of electrical current has anything to do with processes in non-electrical networks, such as social networks. In the following section, therefore, we introduce our random-walk betweenness, whose definition, we believe, *is* relevant for social networks and other types of networks also, and we show that it is in fact numerically equal to the current-flow betweenness.

### 2.2 Random walks

Imagine a “message,” which could be information of almost any kind, that originates at a source vertex $`s`$ on a network. The message is intended for some target $`t`$, but the message, or those passing it, have no idea where $`t`$ is, so the message simply gets passed around at random until it finds itself at $`t`$. Thus, on each step of its travels, the message moves from its current position on the network to one of the adjacent vertices, chosen uniformly at random from the possibilities. This is a random walk.

With the important proviso discussed in the following paragraph, let us define a betweenness measure for a vertex $`i`$ that is equal to the number of times that the message passes through $`i`$ on its journey, averaged over a large number of trials of the random walk. The full random-walk betweenness of vertex $`i`$ will then be this value averaged over all possible source/target pairs $`s,t`$.

There is one small, but important, further technical point. It would be perfectly possible for a vertex to accrue a high betweenness score if a random walk were simply to walk back and forth through that vertex many times, without actually going anywhere. This situation does not correspond to our intuition of what it means to have high betweenness, and indeed if we count walks in this way our betweenness measure is found to give mostly useless results. So instead, we define the betweenness of vertex $`i`$ to be the *net* number of times a walk passes through $`i`$. By “net” we mean that if a walk passes through a vertex and then later passes back through it in the opposite direction, the two cancel out and there is no contribution to the betweenness. Furthermore, if, when averaged over many possible realizations of the walk in question, we find that the walk is equally likely to pass in either direction through a vertex, then again the two directions cancel. How we allow for these cancellations in practice will become clear shortly.

Consider then an absorbing random walk, a walk that starts at vertex $`s`$ and makes random moves around the network until it finds itself at vertex $`t`$ and then stops. If at some point in this walk we find ourselves at vertex $`j`$, then the probability that we will find ourselves at $`i`$ on the next step is given by the matrix element

$$M_{ij}=\frac{A_{ij}}{k_j},\text{for }jt\text{,}$$
(12)
where once again $`A_{ij}`$ is an element of the adjacency matrix, Eq. (3), and $`k_j=_iA_{ij}`$ is the degree of vertex $`j`$. In matrix notation, we can write $`𝐌=𝐀𝐃^1`$, where $`𝐃`$ is, as before, the diagonal matrix with elements $`D_{ii}=k_i`$.

The only exception to Eq. (12), as noted, is for $`j=t`$; since this is an absorbing random walk, we never leave $`t`$ once we get there (a behavior sometimes jokingly called the “Hotel California effect”), so $`M_{it}=0`$ for all $`i`$. Alternatively, we can simply remove row $`t`$ from the matrix altogether. We can also remove column $`t`$ without affecting transitions between any other vertices. Let us denote by $`𝐌_t=𝐀_t𝐃_t^1`$ the matrix with these elements removed, and similarly for $`𝐀_t`$ and $`𝐃_t`$.

Now for a walk starting at $`s`$, the probability that we find ourselves at vertex $`j`$ after $`r`$ steps is given by $`[𝐌_t^r]_{js}`$, and the probability that we then take a step to an adjacent vertex $`i`$ is $`k_j^1[𝐌_t^r]_{js}`$. Summing over all values of $`r`$ from 0 to $`\mathrm{}`$, the total number of times we go from $`j`$ to $`i`$, averaged over all possible walks, is $`k_j^1[(𝐈𝐌_t)^1]_{js}`$. In matrix notation we can write this as an element of the vector

$$𝐕=𝐃_t^1(𝐈𝐌_t)^1𝐬=(𝐃_t𝐀_t)^1𝐬,$$
(13)
where $`𝐬`$ is defined as before—see Eq. (6). (The element $`s_t=1`$ is not strictly necessary—we could give $`s_t`$ any value we like, since row $`t`$ is removed from the equations anyway. We make this particular choice in order to demonstrate that our random-walk betweenness is the same as the current-flow betweenness.) Clearly this equation is precisely the same as Eq. (7), for the particular choice $`v=t`$.

Now the net flow of the random walk along the edge from $`j`$ to $`i`$ is given by the absolute difference $`|V_iV_j|`$ and the net flow through vertex $`i`$ is a half the sum of the flows on the incident edges, just as in Eq. (9). The rest of the derivation follows through as before, and the final net flow of random walks through vertex $`i`$ is given by Eq. (11). (Although Eq. (13) was derived for the particular case in which the $`t`$th row and column are removed from the matrix $`𝐃𝐀`$, the developments of Sec. 2.1 show that the same result can be derived by removing any row and column.)

To summarize, the prescription for calculating random-walk betweenness, which is the expected net number of times a random walk passes through vertex $`i`$ on its way from a source $`s`$ to a target $`t`$, averaged over all $`s`$ and $`t`$, is as follows for each separate component of the graph of interest.

1. Construct the matrix $`𝐃𝐀`$, where $`𝐃`$ is the diagonal matrix of vertex degrees and $`𝐀`$ is the adjacency matrix.
2. Remove any single row, and the corresponding column. For example, one could remove the last row and column.
3. Invert the resulting matrix and then add back in a new row and column consisting of all zeros in the position from which the row and column were previously removed (e.g., the last row and column). Call the resulting matrix $`𝐓`$, with elements $`T_{ij}`$.
4. Calculate the betweenness from Eq. (11), using the values of $`I_i`$ from Eqs. (9) and (10).

## 3 Examples and applications

In this section we give a number of examples to illustrate the properties and use of our random-walk betweenness measure in the analysis of network data.

### 3.1 Simple examples

We start off by presenting some cases with which previous betweenness measures have difficulties, but for which, as we now show, our new measure works well. Our examples are based on the graphs sketched in Fig. 1, with the two groups consisting of complete graphs of five vertices each, as depicted in Fig. 3. We show figures for the betweenness scores in Table 1.

As the table shows, the shortest path betweenness fails to give a higher score to vertex C in the first network than to any of the other vertices within the two communities, while flow betweenness has the same problem with vertex C in the second network. In both cases, by contrast, our random-walk betweenness gives vertex C a distinctly higher score, reflecting our intuition that this vertex has a higher centrality in both of the networks.

### 3.2 Correlation with other measures

Shortest-path betweenness is known to be strongly correlated with vertex degree in most networks (Nakao 1990; Goh et al. 2003), and it has been argued that this makes it a less useful measure. If the two are strongly correlated, then what is the point of going to the effort of calculating betweenness, when degree is almost the same and much easier to calculate? The answer is that there are usually a small number of vertices in a network for which betweenness and degree are very different, and betweenness is useful precisely in identifying these vertices.

We can look at a similar question for our random-walk measure. In Fig. 4, for example, we show scatter plots of random-walk betweenness vs. (a) degree and (b) shortest-path betweenness for the actors in a network of sexual contacts drawn from the study of Potterat et al. (2002). As the figure shows, the random-walk betweenness is moderately highly correlated with degree ($`r^2=0.626`$) and very highly correlated with shortest-path betweenness ($`r^2=0.923`$). Thus, in general, vertices with higher degree or higher shortest-path betweenness tend also to have higher random-walk betweenness. However, this observation misses the real point of interest, which is that there are a few vertices that have random-walk betweenness values quite different from their scores on the other two measures.

In Fig. 5 we show a picture of the network in question, in which we have drawn each the vertices with a size indicating their random-walk betweenness score. It is immediately clear that some, but not all, of the high-degree vertices have high random-walk betweenness. Furthermore, we have highlighted the vertices in the network for which the random-walk betweenness is more than twice their shortest-path betweenness—these are vertices which the shortest-path measure misses because, although they lie on many paths between others, they don’t lie on many *shortest* paths.

The primary reason for the study of networks of sexual contacts is to improve our understanding of the propagation and control of sexually transmitted diseases. Certainly there is no reason to suppose that diseases always know precisely where they are going and spread along the shortest path to some “target” victim. A random-walk model of disease spread is probably a more reasonable representation of what actually happens, in which case the highlighted nodes in Fig. 5 are nodes that are likely to be responsible for transmission of the disease to others, but which would be missed if we evaluated the centralities using standard shortest-path-based methods.

### 3.3 Example applications

We now give two brief examples of applications of our betweenness measure to previously studied networks. First, we look at Padgett’s famous network of intermarriages between prominent families in early 15th century Florence (Padgett and Ansell 1993), depicted in Fig. 6. In Table 2, we rank the fifteen families by their random-walk betweenness, finding that the Medici come out well ahead of the competition, and in particular, they easily best their arch-rivals, the Strozzi. It is suggested that that it was in part the Medici’s skillful manipulation of this marriage network that led to their eventual dominance of the Florentine political landscape.

As a second example, we show in Fig. 7 the largest component of a coauthorship network taken from the study by Newman and Park (2003). The actors in this network are scientists, primarily in applied mathematics and theoretical physics, who work on graph theory and related mathematical studies of networks, and ties represent coauthorship of papers. As in Fig. 5, the size of the vertices represents their betweenness, calculated using our random-walk measure. As we can see there are a number of actors central to the groups in the network who have high betweenness, although there are others who do not. And there are less central actors with high betweenness because they are the brokers who establish connections between different groups (e.g., those labeled “A” in the figure). But notice also that, where there are two (or more) paths to an outlying group of vertices, those along all paths get a high score (e.g., those labeled “B”), since the random-walk betweenness counts all paths and not just geodesic ones.

## 4 Conclusions

Betweenness is a measure of network centrality that counts the paths between vertex pairs on a network that pass through a given vertex. Vertices with high betweenness lie on paths between many others and may thus have some influence over the spread of information across the network. One can define a variety of different betweenness measures, depending on which paths one counts and how they are weighted. The most widely used measure, first proposed by Freeman (1977), counts only shortest paths, and is thus appropriate to cases in which information flow is entirely or mostly along such paths. Flow betweenness (Freeman et al. 1991) counts all paths that carry information when a maximum flow is pumped between each pair of vertices. In many networks, however, neither of these cases is realistic. Both count only a small subset of possible paths between vertices, and both assume some kind of optimality in information transmission (shortest paths or maximum flow).

In this paper we have proposed a new betweenness measure that counts essentially all paths between vertices (we exclude those that don’t actually lead from the designated source to the target), and which makes no assumptions of optimality. Our measure is based on random walks between vertex pairs and asks, in essence, how often a given vertex will fall on a random walk between another pair of vertices. The measure is particularly useful for finding vertices of high centrality that do not happen to lie on geodesic paths or on the paths formed by maximum-flow cut-sets. We have shown that our betweenness can be calculated using matrix inversion methods in time that scales as the cube of the number of vertices on a sparse graph, making it computationally tractable for networks typical of current sociological studies.

We have given a number of brief examples of the use of our betweenness measure, including artificial examples illustrating cases in which it gives substantially different results from previous measures, an example of how it correlates with other measures in a network of sexual contacts, and two applications to previously studied networks, Padgett’s famous Florentine families, and a network of collaborations between scientists. We would be delighted to see more, and more extensive, applications of our random-walk betweenness measure in future studies.

## Acknowledgments

The author thanks Steven Borgatti and Michelle Girvan for useful comments and conversations, and Richard Rothenberg and Stephen Muth for providing the data for the example of Fig. 5. This work was funded in part by the James S. McDonnell Foundation and by the National Science Foundation under grant number DMS–0234188.