text:
# On the origin of the various types of radio emission in GRS 1915+105

## 1 Introduction

The black-hole candidate GRS 1915+105 is one of the most studied X-ray sources in our Galaxy due to its remarkably rich phenomenological diversity across the entire electromagnetic spectrum except the visible band. It was first detected in 1992 with the WATCH instrument on-board the GRANAT satellite (Castro-Tirado, Brandt, & Lund 1992). In contrast with other transient X-ray sources, it has never been switched off since detection. Its optical counter-part has not been detected due to a very high line-of-sight absorption ($``$26 magnitude, Chaty et al. 1996). In the absence of optical observations, the binary parameters as well as the nature of the companion were unknown till 2001. Finally nine years after its detection, Greiner et al. (2001), by near-infrared spectroscopic observations with VLT, established it as a Low Mass X-ray Binary (LMXB) system with a K-M III type companion star of mass 1.2$`\pm `$0.2 M. The black hole mass was determined to be 14$`\pm `$4 M which is the largest mass known so far for any black hole candidate in an X-ray binary. GRS 1915+105 achieved the status of micro-quasar much earlier in 1994 when Mirabel & Rodriguez (1994) detected episodes of superluminal ejections from this source, first time in any Galactic source. Observations of many such episodes of superluminal ejections during the past eight years make GRS 1915+105 distinct among other micro-quasars in our Galaxy. Apart from huge superluminal radio flares, GRS 1915+105 also shows various other types of radio emission like radio oscillations (Pooley & Fender 1997) and extended periods of steady, flat spectrum radio emission known as radio “plateau” states (Fender et al. 1999). These radio “plateau” states are particularly interesting due to their association with the large radio flares. It is found that the “plateau” states are almost always followed by large radio flares with steep spectrum (Hannikainen et al. 1998; Fender et al. 1999; Klein-Wolt et al. 2002), though so far there is no satisfactory explanation for this observed association.

The true glory of this source came into notice after the launch of NASA’s Rossi X-ray Timing Explorer (RXTE) in 1996. Pointed observations with RXTE-PCA showed extremely rich and exciting morphology in the X-ray intensity patterns (Greiner, Morgan, & Remillard 1996; Morgan, Remillard, & Greiner 1997; Muno, Morgan, & Remillard 1999). Similar diversity in the X-ray emission from this source was also observed with the Indian X-ray Astronomy Experiment (IXAE) (Paul et al. 1997, 1998; Yadav et al. 1999). Belloni et al. (2000) carried out a detailed analysis of all the RXTE pointed observations in 1996-97 and classified the complex diversity of the X-ray emission exhibited by this source into 12 classes on the basis of light curves and hardness ratios (one more variability class was identified later on - see Klein-Wolt et al. 2002; Naik, Rao & Chakrabarti 2002). They also put an important step forward in understanding the complexity of this source by showing that all the variability classes occur because of repeated transitions of the source in three basic states. They showed that the transitions between these three states, named as states A, B, and C, can be very fast i.e. within a few seconds. The states A and B are characterized by a soft spectrum with the total luminosity being low and high, respectively. The state C is characterized by a hard spectrum and the presence of strong Quasi Periodic Oscillations (QPO) in the power density spectrum.

This source is probably the best example for a strong connection between the accretion disk, manifested in the X-ray band, and the jet, manifested in the radio/IR band, in a black hole system (Pooley & Fender 1997; Eikenberry et al. 1998; 2000; Mirabel et al. 1998). Study of the correlated behavior of the source in the X-ray and the radio/IR wave bands plays a very important role in the endeavor of understanding this source and many attempts have been made so far to relate the X-ray emission characteristics with the episodes of various types of radio emission. Muno et al. (2001) studied representative observations in detail and showed that the properties of the QPO, like frequency, phase-lag, coherence etc. are correlated with the radio emission. Rau & Greiner (2003) showed that the properties of accretion disk are not correlated with the radio emission. Naik & Rao (2000) showed that the radio emission is high only during three variability classes: $`\beta `$, $`\theta `$ and a sub-class of $`\chi `$ ($`\chi _1`$/$`\chi _3`$ or $`\chi _{RL}`$.)111 Belloni et al. (2000) divided class $`\chi `$ into four sub-classes $`\chi 1`$, $`\chi 2`$, $`\chi 3`$ and $`\chi 4`$ based on their order of occurrence. Out of these four sub-classes only $`\chi _1`$ and $`\chi _3`$ show high radio emission. However, later more such occurrences of class $`\chi `$ have been observed during which the radio emission is high. Thus, instead of numbered sub-classes, class $`\chi `$ can be divided into two generic sub-classes radio-quiet ($`\chi _{RQ}`$) and radio-loud ($`\chi _{RL}`$). The sub-class $`\chi _{RL}`$ corresponds to the radio “plateau” states. They suggested that the radio emission is associated with the soft X-ray dips (short periods of state A) observed in the classes $`\beta `$ and $`\theta `$, apart from the sub-class $`\chi _{RL}`$. Naik et al. (2001) detected similar dips in the X-ray light curve during the presence of a large radio flare indicating their association with large radio flares.

Klein-Wolt et al. (2002) studied all simultaneous observations of the source by RXTE and Ryle Telescope and showed that the radio emission is associated with only state C and not with states A or B. They also found an one-to-one relation between series of long ($`>`$ 100 s), well separated state C intervals and radio oscillation events. They suggested a scenario, according to which the long uninterrupted state C intervals are associated with continuous jets which give “plateau” radio emission, whereas if the state C intervals are well separated by other states then the radio oscillation events are observed. A different picture, however, emerges when the association of the radio emission with the different sub-classes of $`\chi `$ (state C) are examined in detail (see discussion in section 4.2 for more details on this).

The sub-classes of class $`\chi `$ can be divided into two different types of hard states: radio-loud hard state (i.e. $`C_{RL}`$) and radio-quiet hard state (i.e. $`C_{RQ}`$) (Vadawale et al. 2001b; Trudolyubov 2001). By a detailed spectral study of RXTE observations of the source belonging to the two types of hard states, Vadawale et al. (2001b) showed that the wide band X-ray spectrum of state $`C_{RQ}`$ consists of two components: a multicolor disk-blackbody and a Comptonized component whereas the wide band X-ray spectrum of state $`C_{RL}`$ consists of three components: a multicolor disk-blackbody, a Comptonized component and a power-low. They further showed that the additional power-law component can be modeled as due to synchrotron radiation in X-rays, coming from the base of a continuous jet which is present only during the $`C_{RL}`$ states. This three-component picture gets further support from other results such as: only the Comptonized component is responsible for the low-frequency QPO (Rao et al. 2000) and both the QPO as well as the Comptonized component are absent during the soft dips (short state A periods) observed in class $`\theta `$ (Vadawale et al. 2001a). It should be noted that the radio-loud hard state also occurs as a part of other variability classes like $`\theta `$ and $`\beta `$. Hence we will refer it generically as $`C_{RL}`$, whereas the particular sub-class of class $`\chi `$ during which the radio emission is high, will be referred as $`\chi _{RL}`$.

In this paper we explore the association of the radio “plateau” states with large superluminal radio flares and try to envisage a scenario to explain this association as well as the various types of radio emission observed from this source. Since there are not many detailed studies of such episodes of superluminal jet emissions, in the first part of the paper we present a detailed study of a complete sequence of flare morphology described, sequentially, by a small flare, “plateau” state, a disturbed accretion disk and a superluminal jet. We report the observations of the source with Giant Meter-wave Radio Telescope (GMRT) at 1.28 GHz when the source exhibits a flare which turned out to be a pre-plateau flare. We also present the results of a detailed analysis of all the pointed RXTE observations during this flare cycle which confirm the three-component X-ray spectral description of the pre-flare “plateau” state. In order to confirm the three-component description during all occurrences of the “plateau” state, we further carry out similar analysis of representative pointed RXTE observations prior to all huge radio flares identified in the GBI monitoring data on this source. Finally we summarize the results and propose a phenomenological model for different types of radio emission from this source.

## 2 Observations : 2001 June-July radio flare episode

### 2.1 GMRT observations

Radio observations of the micro-quasar GRS 1915+105, at 1.28 GHz with a band pass of 16 MHz, were carried out with GMRT (Swarup et al. 1991) on 2001 June 18, 22, 23, 27, 28, 29, 30 and July 1. The flux density scale was set by observing the primary calibrator 3C286 / 3C48. A phase calibrator was observed before and after a 45 minutes scan on GRS 1915+105. The integration time during the source observations was 32 s. The data reduction and analysis were done by using the standard Astronomical Image Processing System (AIPS) package. The observations on 2001 June 18, 22, 23, and 27 were of $``$ 30-60 minutes, whereas on June 28, 29, 30 and July 1, the observations were of $``$ 8-10 hours. Light curves, with 32 s integration time, were extracted from each of the individual observations of the source and are shown in Figure 1.

It can be seen from the figure that the source was quite steady on June 18 with a very low flux density ($``$10 mJy). The source was found to be bright in radio on June 22 with a flux density of $``$ 50 mJy, along with a sharp dip with a decrease in the flux density by a factor of $``$ 2. On June 23 the source was steady at about 30 mJy. It was very weak ($``$ 5 mJy) on June 27. From June 28 onwards the observations were of long durations (8 – 10 hours) and hence a wide range of flux variabilities could be studied. On June 28 the source was found to be very weak at the beginning of the observations (UTC 17 hour), but the radio flux density gradually increased to $``$ 50 mJy followed by a sharp decrease to $``$ 5 mJy at the end of observations (UTC 24 hour). On the other hand, on June 29, the source was bright in radio with flux density $``$ 70 mJy at the beginning which decayed down to 10 mJy towards the end. The source was relatively weak and steady on June 30 and July 1. It can be seen that the radio emission is highly variable over time scales of a few tens of minutes, similar to that observed during mini flares (or “baby jets”). Analyzing many individual “clean” flares from the same data, Ishwara-Chandra et al. (2002) have tried to model these flares as due to adiabatically expanding synchrotron emitting clouds.

### 2.2 Radio observations by other telescopes

To corroborate the results from the GMRT observations, we obtained radio monitoring data of GRS 1915+105 from 2001 June 15 to July 25 observed with the Ryle telescope at 15.2 GHz (Pooley & Fender 1997). Radio light curves at 15.2 GHz are shown in Figure 2. A strong radio flare was observed on June 21 which was narrowly missed by GMRT. Radio flares with low peak flux density were also observed with both GMRT and Ryle telescopes on June 28 and 29. Similar flux densities at 1.4 GHz and 15.2 GHz suggest the flat nature of the spectrum during the flares. It can be seen, from Figure 2, that the source went into a radio-loud “plateau” state after the GMRT observations which is followed by a radio flare on July 16, observed with the RATAN telescope (Dhawan et al. 2003). The flux density of this flare was much higher at lower frequencies (as observed by RATAN) compared to that at 15 GHz (as observed by Ryle) suggesting a steep spectrum during the flare. This source was also observed by VLBA on July 16, 17 and 18 at 2.25, 8.3 and 15 GHz. VLBA observations clearly showed an ejecta well separated from the core (Dhawan et al. 2003).

These observations suggest that this superluminal flare episode followed a typical sequence of events observed during the past episodes of superluminal flares. It started with a small flare, which was observed by GMRT, followed by a long radio “plateau” state, followed by superluminal ejections. It is thought that the different types of radio emission are results of changes in the accretion flow which are directly reflected in X-rays. Thus to understand the sequence of these events it is necessary to make a detailed analysis of the X-ray observations during this time period.

### 2.3 RXTE pointed observations

To investigate the X-ray properties of the source during and before this 2001 July 16 flaring episode, we analyzed all the 20 available RXTE pointed observations of GRS 1915$`+`$105 from 2001 June 30 to 2001 July 16. Standard procedures for data reduction, response matrix generation, and background estimation were followed using the software package HEASoft 5.2. For spectral analysis we used Standard-2 mode data from Proportional Counter Array (PCA) and Archive mode data from HEXTE Cluster-0. We added the count rate spectrum of all layers of individual Proportional Counter Units (PCUs) and all available PCUs together. Analyzing the spectra of Crab with the new response matrices, it is found that 0.5% systematic error is required to achieve an acceptable fit and the value of the power-law photon index is also found to be close to the canonical value of 2.1. Systematic error of 0.5% is, therefore, added to the PCA spectra of all the observations used in the present work.

X-ray light curves with 1 s time resolution (Standard-1 mode) are generated for all the 20 observations. It is found that during all the RXTE/PCA observations before 2001 July 16, the source was in a hard state (i.e. the source state is $`C_{RL}`$ whereas the class is $`\chi _{RL}`$). Light curves of all the RXTE/PCA observations on July 16 and the last two RXTE/PCA observations before July 16, along with the X-ray (RXTE/ASM) and radio (Ryle telescope) monitoring light curves, are shown in Figure 3. It can be seen from Figure 3 that the last three pointed RXTE/PCA observations on July 16 clearly show evidence for a disturbed accretion disc. The first three pointed observations on July 16 (when the radio flare is already on) show enhanced X-ray emission, which could be either an enhanced $`\chi _{RL}`$ class or the steady part of the X-ray emission during a disturbed accretion disc. Because of the gaps between the pointed observations, it is not possible to precisely identify the time of occurrence of the state change from the X-ray light curves. We carried out a detailed timing and spectral analysis of all the 20 RXTE observations to examine the X-ray properties so that the time of occurrence of the state change could be better understood.

#### 2.3.1 Timing Analysis

For timing analysis, Single-Bit mode data, available in the energy ranges of 3.6 – 5.7 keV and 5.7 – 14.8 keV, are used. Power density spectra (PDS) of 256 bin light curves are generated and co-added for every 16 seconds to achieve better signal to noise ratio. Results of timing and spectral analysis are given in Table 1, along with the log of observations. The parameters for one representative observation per day (before the radio flare) and all observations carried out on July 16 (when the radio flare commenced) are given in the table. Quasi periodic oscillations (QPOs) in 1 – 3 Hz frequency range are seen in the PDS of all the RXTE observations made before July 16, whereas the PDS of all observations on July 16 show QPOs at $`>`$ 4 Hz (see Table 1a). Along with the PDS, phase-lag spectra are also generated by multiplying the imaginary part of the coefficients of the power density spectra in the above two energy ranges (Reig et al. 2000). Individual phase-lag spectra for each 16 s interval were also co-added. Phase-lag spectra of all the observations are shown in Figure 4. The top panel of Figure 4 shows the phase-lag spectra of all observations made before July 16 (“plateau” state) and the bottom panel shows the phase-lag spectra of all observations made on July 16 (including those showing flare/dips, however, these phase-lag spectra are calculated only for the steady portion of the light curve). It can be seen that there is a clear difference in the overall shape of the phase-lag spectra. In order to quantify the shape of the phase-lag spectra of the observations before and on July 16, we applied KS test which shows that these two distributions are different with 99.99% confidence level significance. The reason for this difference in the shape of the phase-lag spectra is not clear, however, it is possible that the ejected matter during the X-ray disturbance (see next section) might be playing some role here as suggested by Pottschmidt et al. (2000). However, the difference clearly shows that the source state before July 16 is different from the state during the steady observations on July 16 and the disturbance in X-rays has already occurred before the first observation on July 16.

#### 2.3.2 Spectral Analysis

XSPEC package (Ver. 11.2) is used for the spectral analysis. A simultaneous fit to the PCA (in the energy range of 3 - 35 keV) and HEXTE (in the energy range of 20 - 150 keV) data was carried out, keeping the relative normalization as a free parameter. A fit with any continuum model shows strong residuals near 6.4 keV and any fit without a Gaussian line at this energy is not acceptable. Such residuals, though with a low amplitude, are also seen in the Crab spectra obtained with PCA. It is not clear what fraction of the residuals is really due to the source and what fraction is due to an instrumental artifact. The line feature at 6.4 keV, therefore, will not be discussed further in this paper. It is found that a model consisting of three components: a disk-blackbody, a power-law and a Comptonized component (CompTT in XSPEC, see Titarchuk 1994) is required for a statistically and physically acceptable fit to the source spectra (see Vadawale et al. 2001b for a comparison of the various models). The best-fit parameters along with the continuum flux of individual spectral components are given in Table 1. It can be seen from Table 1 that the equivalent hydrogen column density is very high compared to the values reported in the literature (e.g. Muno et al. 1999; Vilhu et al. 2001). Spectral fitting with this three-component model requires NH to be within 12 $``$ 15 $`\times 10^{22}cm^2`$ with 99% confidence level. The derived inner-disk radii (Rin) are also found to be high during these observations, compared to the reported values (e.g. Rau & Greiner 2003). However, these apparently high values of Rin are physically plausible i.e. 15 – 25 Rg for a 14 M black hole. The inner disk temperature (kTin) and the plasma temperature (kTe) for all the observations are $``$ 0.5 keV and 7–11 keV respectively and are acceptable. It should be noted that on June 30 (MJD 52090), when the radio emission was relatively low (the “plateau” started on July 1), the spectral and timing parameters are different from the rest of the observations with the value of NH being close to the reported value, which gives confidence for the applicability of this three-component model to the $`C_{RL}`$ state of this source.

The presence of short duration and irregular flares and dips in the X-ray light curves of RXTE observations on July 16 makes spectral fitting extremely difficult during the individual flare/dip events. To examine the properties of the source during these flares and dips, we follow the ratio method used by Vadawale et al. (2001a). Figure 5 shows the Standard-1 light curve in the 2–60 keV energy band and the dynamic PDS along with the ratios of the Standard-1 light curve to the light curves in 2–8, 8–15, 15–23 and 23–60 keV energy ranges. The second panel of the figure shows that the low frequency 4–7 Hz QPO, present in the steady part of the light curve, is absent during the dips. The third panel of the figure shows that during the dips, the decrease in the count-rate in 2-8 keV range is less than that in the total count-rate. Inverted shapes of dips in the fourth and the fifth panels show that the counts in the energy band of 8-23 keV are preferentially decreased compared to the decrease in the total count rate (see Figures 8 and 9 for a clear picture where the dips are of longer duration). Preferential decrease in the count rate in the 8-23 keV energy band strongly supports the inference drawn by Vadawale et al. (2001a) that the Comptonized component, which is dominant in this energy band, is absent during these dips. The absence of QPO during these dips (Figure 5, second panel), and the observation that the Comptonized component is responsible for the QPO in the hard ($`C_{RL}`$) states (Rao et al. 2000), further strengthen the suggestion that the Comptonized component vanishes during the dips.

## 3 Large flares observed by GBI and RXTE-ASM

Our detailed analysis around the 2001 July radio flare (during which a separate ejecta was detected by VLBI, exhibiting superluminal ejection) shows that before the flare, the source was in $`C_{RL}`$ state consisting of three spectral components: a multi-color disk blackbody, a power-law, and a Comptonized component. During the radio flare, the source showed a dipping behavior during which the Comptonized component of the X-ray spectra appears to be vanishing. A similar behavior of the source was observed during the superluminal ejection episode of 1999 June (Dhawan et al. 2003) and 1997 October (Fender et al. 1999). The source was in $`C_{RL}`$ state before the flare (Rao et al. 2000; Vadawale et al. 2001b) and pointed observation during the flare showed soft dips (state A period) during which the Comptonized component vanishes. This leads to an interesting suggestion that the preceding $`C_{RL}`$ state and the presence of soft dips (state A periods) are the characteristics of all superluminal ejection episodes.

To verify this suggestion we carried out a similar analysis for all possible superluminal radio flares observed during the period of 1996 December to 2000 April when GBI radio monitoring data are available. Apart from the superluminal episodes in 1997 October and 1999 June, there is one more occasion, 1998 May, during which a separated ejecta is reported (Dhawan et al. 2000). However, a complete GBI monitoring radio light curve from 1996 December to 2000 April shows many other large flares and it might be possible that some such ejection episodes are missed. Therefore, we selected all large flares ($`>`$ 350 mJy at 2.25 GHz) from the GBI monitoring data. It is found that there are 9 flares satisfying this criteria, the characteristic properties of which are given in Table 2. The GBI and ASM monitoring radio light curves of the source during all these 9 selected radio flares are shown in Figure 6 along with the complete monitoring light curves from GBI, ASM and BATSE. All the large radio flares, during which separate ejecta are reported so far, show a fast rise and exponential decay (FRED) with decay time constant of the order of 3 days. It can be seen, from Table 2 and Figure 6, that the characteristic properties of 3 other radio flares (1998 April 13, 1998 June 3 and 1999 December 23) are found to be similar to those 3 flares during which superluminal ejection is reported. Hence we assume that all flares with the FRED morphology are superluminal flare episodes and we give the integrated flare energy (in units of Jy.day) in Table 2. The GBI light curve also shows that the source was in radio “plateau” state prior to the all six ‘assumed’ superluminal flares whereas the ASM light curves during these periods show that the source was in low and steady X-ray state. The properties of the three radio flares without FRED such as shape of the radio flares, variability in ASM light curve prior to the flares, are different from those seen during the superluminal radio flares.

A closer look at Table 2 reveals an interesting fact that the average ASM count rate and the GBI flux during the pre-flare “plateau” state show a strong correlation suggesting a strong coupling between the X-ray and radio emission. In Figure 7 (left panel) we show a plot of GBI flux against the ASM count rate along with a best-fit straight line. We derive a correlation coefficient of 0.96 (98% confidence level). This could be similar to the correlation between the X-ray and the radio emissions found in the Galactic black hole candidate sources (see eg. Gallo, Fender & Pooley 2003; Choudhury et al. 2003).

We also find that the average pre-flare ASM count rate and the total flux integrated over the duration of the flare are also strongly correlated. In Figure 7 (right panel) we show this correlation (with a correlation coefficient of 0.98) which is significant at 99% confidence level. The correlation between the pre-flare ASM count rate and the integrated flare flux is particularly interesting, given the temporal and spatial separation between the two types of emission. It shows that the pre-flare “plateau” state plays a crucial role in the formation of the large superluminal radio flares.

To quantify the timing and the spectral properties of the pre-flare states of all the six selected flares, we have done a detailed analysis of the RXTE pointed observations during these steady states. As the properties of the source are rather stable during these states, we analyzed two RXTE observations immediately before each flare. We also analyzed the RXTE observations on 1997 October 30 and 1999 June 8, which are the only pointed observations of the source during the rising phase of superluminal flares. We adopted a similar analysis procedure described in the previous section and fitted the same three-component model to the source spectra of all the observations. The log of observations and the best-fit spectral parameters are given in Table 3. The results of analysis of the two pointed observations during the onset of superluminal flares are shown in Figure 8 and 9, which are similar to Figure 5.

We find that X-ray spectrum during all the pointed RXTE observations immediately before the selected flares can be fitted by our model consisting of three components: a disk-blackbody, a Comptonized component and a power-law. This confirms our three-component description of the $`C_{RL}`$ state. Both the available observations close to but after the onset of the radio flare shows dipping behavior as shown in Figures 8 and 9. It can be seen that, though the morphology of the X-ray light curves (classes according to Belloni et al. 2000) is different in all the pointed observations during the superluminal flares (Figures 5, 8 and 9), the properties of the source during the dips are the same. The absence of QPOs during the dips in X-ray light curves (panel B of the above three figures) and the preferential decrease in 8 – 23 keV count rate (as seen from the inverted shape of the ratios in panels D and E of these figures) confirm the absence of the Comptonized component during the dips. We have verified, for a large number of observations containing similar soft dips (state A periods), that the characteristics of all the soft dips are similar. Thus it seems that the preferential decrease in $``$ 8 – 25 keV range, suggesting the absence of the Comptonized component, is rather a general feature of all the soft dips (short state A periods) seen in this source. This leads to an interpretation that the central Compton cloud is ejected away during all the soft dips. Similar conclusion of mass ejection during dips of type A is drawn by Yadav (2001) on the basis of their spectral study during the class $`\beta `$.

## 4 Discussion

We have presented a detailed study of all the candidate superluminal ejection episodes of GRS 1915+105, identified from the GBI, ASM, and BATSE monitoring observations. It should be noted here that there are at least two other episodes of large flares, first one during 2000 July-August, reported by Fender et al. (2002a) which follows the “plateau” state – large flare sequence and the other during 2001 March reported in Fender et al. (2002b) for which the superluminal ejection was observed directly. We have verified that the results presented here are consistent with the RXTE pointed observations during 2000 July-August 2000 flare episode. For the 2001 March flare episode, unfortunately, both RXTE-PCA and RXTE-ASM coverage are poor and hence the pre-flare state cannot be established, but we believe that it must be $`C_{RL}`$.

Results presented in the previous sections confirm the suggestions that (i) the wide band X-ray spectrum during the $`C_{RL}`$ state has three spectral components: a multicolor disk-blackbody, a Comptonized component and a power-law (ii) the soft dips (short periods of state A) are present in the X-ray light curve observed during the onset of superluminal flares, (iii) the Comptonized component is absent during the soft dips. These results lead to an interesting suggestion that the Compton cloud is ejected away during the soft dips. Formation of a central hot region can be explained under the Two Component Accretion Flow (TCAF) paradigm as the hot, quasi-spherical, post shock region near the black hole (Chakrabarti & Titarchuk 1995, Chakrabarti 2001 and references there in) which is responsible for the presence of the Comptonized component (Rao et al. 2000). Ejection of the central Compton cloud can be explained if magnetic field is included in the TCAF framework (Nandi et al. 2001). The pre-flare $`C_{RL}`$ states are known to have a steady jet and the sudden ejection of matter in the previously established jet raises an interesting possibility for the origin of the superluminal flares in terms of the internal shock model.

### 4.1 A Mechanism for superluminal motion?

Apparent superluminal motion of blobs during the large radio flares of Galactic micro-quasars is one of the most spectacular phenomena of high energy astrophysics. GRS 1915+105 is the only source which shows repeated episodes of large radio flares exhibiting superluminal motion. The apparent superluminal motion can be understood as geometric effect due to very high intrinsic velocity (i.e. close to $`c`$) of the moving blob at some angle with the line of sight. So far attempts have been made to understand the superluminal motions based on two different ideas: (1) matter blob moving at very high velocity and (2) shocks moving through a relatively slowly moving medium. Atoyan & Aharonian (1999) showed that it is possible to reproduce the observed radio light curves of the separating blobs in terms of ejection and evolution of discrete plasmons, however, the instantaneous power requirement is very high in this model. Further they found that a single population of relativistic particles accelerated at the time of ejection of the plasmon cannot explain the observations and a continuous replenishment of relativistic particles is necessary. The continuous acceleration of particles comes naturally in the alternative model, the internal shock model proposed by Kaiser, Sunyaev & Spruit (2000). They show that if the moving blobs are the traveling shock front arising due to differential velocity of the moving continuous jet material then it is possible to reproduce the observed light curves. The total energy requirement is the same as the plasmon model, however, the rate at which the energy supplied from the central source is much lower than that in the plasmon model.

The presence of the underlying continuous jet and the differential velocity of the moving matter are assumed a priori in the internal shock model and no attempt has been made to explain them. However, it can be seen that, in the context of the present work, these requirements are met quite naturally if the sudden ejection of the Compton cloud (i.e. the state A dip) occurs after a prolonged period of $`C_{RL}`$ state. The velocity of the ejected matter blob can be higher than the velocity of the matter in the underlying continuous jet, and hence as the ejected matter blob passes through the jet it creates an internal shock at the leading front where particles can be accelerated. Gallo et al. (2003) showed that, in other GBHCs, the velocity of the matter in steady jets is lower than that during transient events. This gives further confidence to the picture of the ejected mass driving through slower steady flow causing the internal shock. This moving internal shock can then be observed as separating blobs in the radio images. This suggestion provides a rather complete picture for the different types of radio emission from this source as described in the next section.

### 4.2 The suggested scenario

The results obtained from our analysis as well as the various results on radio flares reported in the literature, can be summarized as follows.

* All superluminal radio flares, during which a separated ejecta is reported, as well as candidate superluminal flares for which there is no report of observation, are preceded by the “radio-loud hard ($`C_{RL}`$) state”.
* The source spectrum during $`C_{RL}`$ state consists of three components: a multicolor disk-blackbody, a Comptonized component and a power-law. Large values of the derived inner disk radius suggest a geometry in which there is a hot spherical Compton cloud (responsible for the Comptonized component) surrounded by a thin disk (responsible for the disk-blackbody component).
* Whenever there is a pointed X-ray observation during the onset of a superluminal radio flare (3 out of 7 cases), the light curve shows soft dips (small state A episodes). During such dips, the Comptonized component is absent in the source spectrum.
* High radio emission is observed from the source only during the X-ray variability classes having soft dips (short state A periods) apart from the radio “plateau” periods.
* All superluminal flares show a characteristic fast rise and exponential decay profile in their radio light curve, which cannot be explained by the blob-ejection mechanism. Such profiles can be explained by the internal shock model of Kaiser et al.(1999). According to this model, the motion of the matter blob through the already present matter is seen as the moving ejecta during high spatial resolution radio observations.
* The radio “Plateau” ($`C_{RL}`$) state is known to have steady jets which eject a continuous stream of matter. Thus if a blob-ejection occurs after a “plateau” state, it will satisfy the requirement of the internal shock model and gives rise to a superluminal radio flare.
* The total integrated flux during the superluminal flares is highly correlated with the observed X-ray flux during the preceding $`C_{RL}`$ states.

These points suggest a scenario for different types of radio emission observed from this source.

* The $`C_{RL}`$ states have continuous jets and prolonged episodes of such states give rise to steady high radio emission with flat spectrum which arises from the continuous jet. This is a fairly robust statement as the compact jets have actually been observed during the episodes of $`C_{RL}`$ states (Dhawan et al. 2000).
* The ejection of the Compton cloud during a soft (state A) dip gives rise to a small radio flare. Repeated occurrence of such dips gives rise to radio oscillation events. It should be noted that the amplitude of the isolated flares or the radio oscillation events will depend on various aspects like the amount of mass outflow during the immediately previous $`C_{RL}`$ state, the amount of mass ejected during the dips etc. Hence, it might not be possible to always observe small radio flares or oscillation when such dips are present in X-ray, though, in such cases the average radio emission should be high. However, this means that whenever radio oscillations are observed, the soft dips must be present in the X-ray light curves.
* If the occurrence of the soft (state A) dip is preceded by a prolonged period of $`C_{RL}`$ state having a continuous jet then it satisfies the requirements of the internal shock model and gives rise to the observed superluminal motion of blobs as seen in high resolution radio images.

A schematic picture of this scenario is shown in Figure 10. According to this scenario, any short time variation in the radio flux is caused by the occurrence of the soft (state A) dips during which the Compton cloud is ejected. This is slightly different from the inference drawn by Klein-Wolt et al. (2002) that only state C episodes are related to the radio emission. They find that it is necessary to have the state C episodes well-separated in order to have radio oscillation events. However, there are X-ray variability classes like $`\lambda `$ which show long, well separated periods of state C, but the average radio flux during class $`\lambda `$ is much lower compared to the classes $`\beta `$, $`\theta `$ which also have well separated long state C periods (Naik & Rao 2000). This can be explained in our scenario according to which, the state C periods in class $`\lambda `$ are actually state $`C_{RQ}`$ periods whereas the state C periods in classes $`\beta `$, $`\theta `$ are actually state $`C_{RL}`$ periods. Further, it can be seen that such well-separated state C episodes, when the radio oscillations are observed, are almost always accompanied by state A dips. Thus the one-to-one relation between the state C episodes and the radio oscillation events found by Klein-Wolt et al. (2002) is valid in our scenario also. It should be noted that Figure 3g of Klein-Wolt et al. (2002) does not show any oscillations in the presence of class $`\theta `$. According to our scenario it is possible not to have radio oscillations in the presence of state A dips, i.e. because of close ejection events etc., but not vise-versa. As a counter example, Figure 10 of Dhawan et al. (2000) show clear oscillations during the presence of class $`\theta `$. This picture is further supported by the pointed radio observation near the onset of the superluminal flare in 1997 October by Fender et. al (1999), which shows core oscillations as well as superluminal jets on 1997 October 30 and 31. On both these days the source was in class $`\beta `$ which shows A type dips after C state (Yadav 2001). The hypothesis of mass ejection during the soft dips is also supported by the calculation of time delay between emissions at different frequencies as presented by Ishwara-Chandra et al. (2002). They show that the IR emission follows the mass ejection with almost zero time delay. It is known that IR flares start at the time of spike (in beta class) which marks the beginning of A type dips (Eikenberry et al. 1998).

There are some important cross-checks for this scenario. First of all, it predicts that the separated ejecta should not be observed for any radio flare other than those having FRED profile and are preceded by $`C_{RL}`$ states. Also whenever radio oscillations are observed, the soft (state A) dips must be present in the X-ray light curve. A large data base of radio and X-ray observation of GRS 1915+105 has been collected so far and all the reported observations satisfies these criteria. However, the most important aspect of this scenario, to be tested with future observations, is the three-component description of the wide band X-ray spectra during the $`C_{RL}`$ state. This can be verified, for example, by high sensitivity observations above 50 keV, where the differences in the variation of the RMS power of the QPO with energy between $`C_{RL}`$ and $`C_{RQ}`$ state will show the existence of additional component which is not participating in the QPO. It should be noted that according to this picture, the low luminosity and soft spectrum of state A is due to the absence of the central Compton cloud. However this applies only to the short duration state A period appearing as soft dips. There exists a variability class $`\varphi `$ during which the source appears to be in state A for much longer duration ($``$days) which can not be explained in the present picture (see, however, Vadawale et al. 2003 for an attempt to understand the class $`\varphi `$ as due to obscuration of the Compton cloud).

This mechanism suggests that whenever there is a $`C_{RL}`$ state, the next soft X-ray dip events will give rise to a superluminal flare. Thus it provides a very important handle in predicting the occurrence of a flare which can help to plan new coordinated observation of large flares. Such observations can lead to further understanding of very important questions like exact mechanism of ejection, cause of ejection, acceleration of the matter etc. It can be seen that a continuous hard X-ray and radio monitoring is very important in distinguishing $`C_{RQ}`$ state and $`C_{RL}`$ states. Unfortunately, after CGRO-BATSE there is no hard X-ray monitor currently available making an important observation handle on the occurrence of $`C_{RL}`$ state unavailable. The Solar X-ray Spectrometer (SOXS), which is a small phoswich type open hard X-ray detector (Malkar et al. 2003), will also perform daily monitoring of a few bright sources and hence might be useful in predicting large superluminal flares from this source.

## 5 Conclusion

In this paper we have tried to explain the observed association between the radio “plateau” or the $`C_{RL}`$ states and the superluminal flares in GRS 1915+105. All $`C_{RL}`$ states have very similar X-ray spectral properties and show a three-component spectra. We have further shown that the soft X-ray dips are observed near the onset of radio flares. During such dips the Comptonized component is absent, which we propose as due to the ejection of the central Compton cloud. This ejected matter is then responsible for the low frequency emission which can be observed as an isolated flare or regular oscillations (if the dips are repeating). Such ejections might give rise to superluminal flares if these dip events are preceded by a $`C_{RL}`$ state according to the internal shock model for the superluminal flares. Two definite predictions of this scenario are that (1) whenever radio oscillations are observed, the soft dips will be present in the X-ray light curves and (2) if $`C_{RL}`$ is not preceded by any radio flare it will not have the characteristic FRED shape and will not show separated ejecta. It also suggests that in the future whenever $`C_{RL}`$ is observed, there are very good chances to catch a superluminal flare in ‘live action’ and well coordinated multi wavelength observations of such an event will help understanding of the fundamental questions underlying such events.

## 6 Acknowledgments

We thank the members of the RXTE, BATSE, and GBI teams for making the data publicly available. This research has made extensive use of data obtained through the High Energy Astrophysics Science Archive Research Center (HEASARC) online service, provided by NASA/Goddard Space Flight Center. The Green Bank Interferometer (GBI) is a facility of the National Science Foundation operated by the NRAO in support of NASA High Energy Astrophysics programs.


format: text

text:
# Information Dynamics in the Networked World

## 1 Introduction

The problem of information flows in social organizations is relevant to issues of productivity, innovation and the sorting out of useful ideas from the general chatter of a community. How information spreads determines the speed with which individuals can act and plan their future activities. Moreover, information flows take place within social networks whose nature is sometimes difficult to establish. This is because the network itself is sometimes different from what one would infer from the formal structure of the group or organization.

The advent of email as the predominant means of communication in the information society now offers a unique opportunity to observe the flow of information along both formal and informal channels. Not surprisingly, email has been established as an indicator of collaboration and knowledge exchange wellman02computersocial ; whittaker96email ; guimera02email ; tyler03email ; eckmann03email . Email is also a good medium for research because it provides plentiful data on personal communication in an electronic form. This volume of data enables the discovery of shared interests and relationships where none were previously known schwartz93discovering .

In this chapter we will review three studies that utilized networks exposed by email communication. In all three studies, the networks analyzed were derived from email messages sent through the Hewlett Packard Labs email server over the period of several months in 2002 and 2003. The first study, by Tyler et al. tyler03email , develops an automated method applying a betweenness centrality algorithm to rapidly identify communities, both formal and informal, within the network. This approach also enables the identification of leadership roles within the communities. The automated analysis was complemented by a qualitative evaluation of the results in the field.

The second study, by Wu et al. wu03flow  analyzes email patterns to model information flow in social groups, taking into account the observation that an item relevant to one person is more likely to be of interest to individuals in the same social circle than those outside of it. This is due to the fact that the similarity of node attributes in social networks decreases as a function of the graph distance. An epidemic model on a scale-free network with this property has a finite threshold, implying that the spread of information is limited. These predictions were tested by measuring the spread of messages in an organization and also by numerical experiments that take into consideration the organizational distance among individuals.

Since social structure affects the flow of information, knowledge of the communities that exist within a network can also be used for navigating the networks when searching for individuals or resources. The study by Adamic and Adaradamic03search , does just this, by simulating Milgram’s small world experiment on the HP Labs email network. The small world experiment has been carried out a number of times over the past several decades, each time demonstrating that individuals passing messages to their friends and acquaintances can form a short chain between two people separated by geography, profession, and race. While the existence of these chains has been established, how people are able to navigate without knowing the complete social networks has remained an open question. Recently, models have been proposed to explain the phenomenon, and the work of Adamic and Adar is a first study to test the validity of these models on a social network.

## 2 Email as Spectroscopy

Communities of practice are the informal networks of collaboration that naturally grow and coalesce within and outside organizations. Any institution that provides opportunities for communication among its members is eventually threaded by communities of people who have similar goals and a shared understanding of their activities ouchi80markets . These communities have been the subject of much research as a way to uncover the reality of how people find information and execute their tasks. (for example, see blau63organizations ; burt80network ; wasserman94socialnetwork , or for a survey see scott92organizations ).

These informal networks coexist with the formal structure of the organization and serve many purposes, such as resolving the conflicting goals of the institution to which they belong, solving problems in more efficient ways huberman95communities , and furthering the interests of their members. Despite their lack of official recognition, informal networks can provide effective ways of learning, and with the proper incentives actually enhance the productivity of the formal organization crozier64bureaucratic ; crane72colleges ; lave91learning .

Recently, there has been an increased amount of work on identifying communities from online interactions (a brief overview of this work can be found in wellman02computersocial ). Some of this work finds that online relationships do indeed reflect actual social relationships, thus adding effectively to the “social capital” of a community. Ducheneaut and Bellotti ducheneaut02email  conducted in-depth field studies of email behavior, and found that membership in email communities is quite fluid and depends on organizational context. Mailing lists and personal web pages also serve as proxies for social relationships adamic03friends , and the communities identified from these online proxies resemble the actual social communities of the represented individuals. Because of the demonstrated value of communities of practice, a fast, accurate method of identifying them is desirable.

Classical practice is to gather data from interviews, surveys, or other fieldwork and to construct links and communities by manual inspection (see allen84flow ; hinds95communication  or an Internet-centric approach in garton97online ). These methods are accurate but time-consuming and labor-intensive, prohibitively so in the context of a very large organization. Alani et al. alani02practice  recently introduced a semi-automated utility that uses a simple algorithm to identify nearest neighbors to one individual within a university department.

The method of Tyler et al. tyler03email  uses email data to construct a network of correspondences, and then discovers the communities by partitioning this network. It was applied to a set of over one million email messages collected over a period of roughly two months at HP Labs in Palo Alto, an organization of approximately 400 people. The only pieces of information used from each email are the names of the sender and receiver (i.e., the “to:” and “from:” fields), enabling the processing of a large number of emails while minimizing privacy concerns.

The method was able to identify small communities within the organization, and the leaders for those communities, in a matter of hours, running on a standard Linux desktop PC. This experiment was followed by a qualitative evaluation of the experimental results in the “field”, which consisted of sixteen face-to-face interviews with individuals in HP Labs. The interviews validated the results obtained by the automated process, and provided interesting perspectives on the communities identified. We describe the results in more detail below.

### 2.1 Identifying Communities

It is straightforward to construct a graph based on email data, in which vertices represent people and edges are added between people who exchanged at least a threshold number of email messages. Next, one can identify communities: subsets of related vertices, with many edges connecting vertices of the same subset, but few edges lying between subsets girvan02community .

The method of Wilkinson and Huberman wilkinson02genes , related to the algorithm of Girvan and Newman girvan02community , partitions a graph into discrete communities of nodes and is based on the idea of betweenness centrality, or betweenness, first proposed by Freeman freeman77centrality . The betweenness of an edge is defined as the number of shortest paths that traverse it. This property distinguishes inter-community edges, which link many vertices in different communities and have high betweenness, from intra-community edges, whose betweenness is low.

To illustrate the community discovery process, consider the small graph shown in Figure 1. This graph consists of two well-defined communities: the four vertices denoted by squares, including vertex A, and the nine denoted by circles, including vertex B. Edge AB has the highest betweenness, because all paths between any circle and square must pass through it. If one were to remove it, the squares and circles would be split into two separate communities. The algorithm of Wilkinson et al. repeatedly identifies inter-community edges of large betweenness such as AB and removes them, until the graph is resolved into many separate communities.

Because the removal of an edge strongly affects the betweenness of many others, the values were repeatedly updated with the fast algorithm of Brandes brandes01betweenness ; newman01scientist ; girvan02community . The procedure stops removing edges when it cannot further meaningfully subdivide communities. Figure 2 shows the smallest possible component that can be subdivided into two viable subcommunities. It has 6 nodes, consisting of two triangles linked by one edge. A component with fewer than 6 nodes cannot be subdivided further.

Components of size $`6`$, for example the group of size nine in Figure 1, can also constitute single cohesive communities. Figure 3 shows how the algorithm determines when to stop subdividing a community. The edge XY has the highest betweenness, but removing it would separate a single node, which does not constitute a viable community. In general, the single edge connecting a leaf vertex (such as X in Figure 3) to the rest of a graph of $`N`$ vertices has a betweenness of $`N1`$ , because it contains the shortest path from X to all $`N1`$ other vertices. The stopping criterion for components of size $``$ 6 is therefore that the highest betweenness of any edge in the component be equal to or less than $`N1`$.

### 2.2 Multiple Community Structures

As mentioned above, the removal of any one edge affects the betweenness of all the other edges, particularly in large, real-world graphs such as the email graph. Early in the process, there are many inter-community edges which have high betweenness and the choice of which to remove, while arbitrary, dictates which edges will be removed later. For example, a node belonging to two communities can be placed in one or the other by the algorithm, depending on the order in which edges are removed. One can take advantage of this arbitrariness to repeatedly partition the graph into many different “structures” or sets of communities. These sets are then compared and aggregated into a final list of communities.

Wilkinson and Huberman wilkinson02genes  introduced randomness into the algorithm by calculating the shortest paths from a random subset as opposed to all the nodes. The algorithm cycles randomly through at least $`m`$ centers (where $`m`$ is some cutoff) until the betweenness of at least one edge exceeds the threshold betweenness of a “leaf” vertex. The edge whose betweenness is highest at that point is removed, and the procedure is repeated until the graph has been separated into communities. The modified algorithm may occasionally remove an intra-community edge, but such errors are unimportant when a large number of structures is aggregated.

Applying this modified process $`n`$ times yields $`n`$ community structures imposed on the graph. One can then compare the different structures and identify communities. For example, after imposing 50 structures on a graph, one might find: a community of people A, B, C, and D in 25 of the 50 structures; a community of people A, B, C, D, and E in another 20; and one of people A, B, C, D, E and F in the remaining 5. This result is reported in the following way: A(50) B(50) C(50) D(50) E(25) F(5) which signifies that A, B, C, and D form a well-defined community, E is related to this community, but also to some other(s), and F is only slightly, possibly erroneously, related to it. For details of the aggregation procedure, please see wilkinson02genes .

The entire process of determining community structure within the graph is displayed below.

* For $`i`$ iterations, repeat {

1. Break the graph into connected components.
    2. For each component, check to see if component is a community.

    + If so, remove it from the graph and output it.
        + If not, remove edges of highest betweenness, using the modified Brandes algorithm for large components, and the normal algorithm for small ones. Continue removing edges until the community splits in two.
    3. Repeat step 2 until all vertices have been removed from the graph in communities. }
* Aggregate the $`i`$ structures into a final list of communities.

### 2.3 Results

The algorithm was applied to email data from the HP Labs mail server from the period November 25, 2002 to February 18, 2003, with 185,773 emails exchanged between the 485 HP Labs employees. For simplicity, emails that had an external origin or destination were omitted. Messages sent to a list of more than 10 recipients were likewise removed, as these emails were often lab-wide announcements (rather than personal communication), which were not useful in identifying communities of practice.

A graph was constructed from this data by placing edges between any two individuals that had exchanged at least 30 emails in total, and at least 5 in both directions. The threshold eliminated infrequent or one-way communication, and eliminated some individuals from the graph who either sent very few emails or used other email systems. The resulting graph consisted of 367 nodes, connected by 1110 edges.

There was one giant connected component of 343 nodes and six smaller components ranging in size from 2 to 8. The modified Brandes algorithm detected 60 additional distinct communities within the giant component. The largest community consisted of 57 individuals, and there were several communities of size 2. The mean community size was 8.4, with standard deviation 5.3. A comparison of these communities with information from the HP corporate directory revealed that 49 of the 66 communities consisted of individuals entirely within one lab or organizational unit. The remaining 17 contained individuals from two or more organizations within the company.

### 2.4 Identifying Leadership Roles

In addition to identifying formal and informal work communities, it is also possible to draw inferences about the leadership of an organization from its communication data. One method is to visualize the above graph of the HP Labs email network with a standard force-directed spring algorithm fruchterman91graph , shown in Figure 4. This spring layout of the email network does not use any information about the actual organization structure, and yet high level managers (the reddest nodes are at the top of the hierarchy) are placed close to the center of the graph. The trend is quantified in Table 1, which lists the average hierarchy depth (levels from the lab director) as a function of the position in the layout from the center.

Note that there is a group of 6 nodes in the upper right portion of the graph that are quite removed from the center, but are relatively high in the organizational hierarchy. This is the university relations group that reports directly to the head of HP Labs, but has no other groups reporting to it. Hence the layout algorithm correctly places them on the periphery of the graph, since their function, that of managing HP’s relationship with universities, while important, is not at the core of day-to-day activities of the labs.

Evaluating communication networks with this technique could provide information about leadership in communities about which little is known. Sparrow proposed this approach for analyzing criminal networks sparrow91criminal , noting that “Euclidean Centrality is probably the closest to the reality” of the current criminal network analysis techniques. More recently, Krebs applied centrality measures and graphing techniques krebs02terrorist  to the terrorist networks uncovered in the 9/11 aftermath. He found that the average shortest path was unusually long for such a small network, and concluded that the operation had traded efficiency for secrecy - individuals in one part of the network did not know those in other parts of the network. If one cell had been compromised, the rest of the network would remain relatively unaffected. Several social network centrality measures pointed to Mohamed Atta’s leadership role in the attacks of Sept. 11. The role was also confirmed by Osama bin Laden in a video tape following the attacks.

### 2.5 Field Evaluation

The HP Labs social network, being much less covert, could readily be compared to the structure of the formal organization. Nevertheless, the informal communities identified by the algorithm could not be verified in this way. Tyler et al. decided to validate the results of their algorithm by conducting a brief, informal field study. Sixteen individuals chosen from seven of the sixty communities identified were interviewed informally. The communities chosen represented various community sizes and levels of departmental homogeneity. They ranged in size from four to twelve people, and three out of the seven were heterogeneous (included members of at least two different departmental units within the company).

All sixteen subjects gave positive affirmation that the community reflected reality. More specifically, eleven described the group as reflecting their department, four described it as a specific project group, and one said it was a discussion group on a particular topic. Nine of the sixteen (56.25%) said nobody was missing from the group, six people (37.5%) said one person was missing, and one person (6.25%) said two people were missing. Conversely, ten of the sixteen (62.5%) said that everybody in the group deserved to be there, whereas the remaining six (37.5%) said that one person in the group was misclassified.

The interviews confirmed that most of the communities identified were based on organization structure. However, the communities also tended to include people who were de facto department members, but who did not technically appear in the department’s organization chart, such as interns or people whose directory information had changed during the two months of the study. Finally, the algorithm seemed to succeed in dividing departmental groups whose work is distinct, but lumped together groups whose projects overlap.

Heterogeneous, cross-department communities are of particular interest because they cannot be deduced from the formal organization. The interviews revealed that most of them represented groups formed around specific projects, and in one case, a discussion forum. For example, one community contained three people from different labs coordinating on one project: a technology transfer project manager, a researcher who was the original designer of a piece of PC hardware, and an engineer redesigning the hardware for a specific printer.

### 2.6 Discussion

The power of this method for identifying communities and leadership is in its automation. It does an effective job of uncovering communities of practice with nothing more than email log (“to:” and “from:”) data. Its simplicity means that it can be applied to organizations of thousands and produce results efficiently. However, it is important for computing centrality measures to be able to define membership in an organization as well as disambiguate identities. In a setting like a corporate lab, the organization is clearly defined and identities can be clarified from official directories. In an informal network, however, these tasks are much more difficult.

Communities identified in this automated way lack the richness in contextual description provided by ethnographic approaches. They do not reveal the nature or character of the identified communities, the relative importance of one community to another, or the subtle inter-personal dynamics within the communities. These kinds of details can only be uncovered with much more data- or labor-intensive techniques. However, in cases where an organization is very large, widely dispersed, or incompletely defined (informal), this method provides an suitable alternative or compliment to the more traditional, labor-intensive approaches.

## 3 Information Flow in Social Groups

In the previous section we saw that individuals tend to organize both formally and informally into groups based on their common activities and interests. In this section we examine how this structure in the interaction network affects the way information spreads. This is not unlike the transmission of an infectious agent among individuals, where the pattern of contacts determines how far a disease spreads. Thus one would expect that epidemic models on graphs are relevant to the study of information flow in organizations. In particular, recent work on epidemic propagation on scale free networks found that the threshold for an epidemic is zero, implying that a finite fraction of the graph becomes infected for arbitrarily low transmission probabilities zoltan02halting ; pastor-satorras01epidemic ; newman02emailnetworks . The presence of additional network structure was found to further influence the spread of disease on scale-free graphs eguiluz02epidemicclust ; vazquezPRE2003 ; newman02assortative .

There are, however, differences between information flows and the spread of viruses. While viruses tend to be indiscriminate, infecting any susceptible individual, information is selective and passed by its host only to individuals the host thinks would be interested in it. The information any individual is interested in depends strongly on their characteristics. Furthermore, individuals with similar characteristics tend to associate with one another, a phenomenon known as homophily lazarsfeld54friendship ; touhey74similarity ; feld81social . Conversely, individuals many steps removed in a social network on average tend not to have as much in common, as shown in a study adamic03friends  of a network of Stanford student homepages and illustrated in Figure 5.

Wu et al. wu03flow  introduced an epidemic model with decay in the transmission probability of a particular piece of information as a function of the distance between the originating source and the current potential target. This epidemic model on a scale-free network has a finite threshold, implying that the spread of information is limited. The predictions were further tested by observing the prevalence of messages in an organization and also by numerical experiments that take into consideration the organizational distance among individuals.

Consider the problem of information transmission in a power-law network whose degree distribution is given by

$$p_k=Ck^\alpha e^{k/\kappa },$$
(1)
where $`\alpha >1`$, there is an exponential cutoff at $`\kappa `$ and $`C`$ is determined by the normalization condition. A real world graph will at the very least have cutoff at the maximum degree $`k=N`$, where $`N`$ is the number of nodes, and many networks show a cutoff at values much smaller than $`N`$. For the analysis of the spread of information flow on networks, Wu et al. used generating functions, whose application to graphs with arbitrary degree distributions is discussed in newman01graphs . For a power-law network the generating function is given by

$$G_0(x)=\underset{k=1}{\overset{\mathrm{}}{}}p_kx^k=\frac{\mathrm{Li}_\alpha (xe^{k/\kappa })}{\mathrm{Li}_\alpha (e^{1/\kappa })}.$$
(2)
where $`Li_n(x)`$ is the $`n`$th polylogarithm of $`x`$.

Following the analysis in newman02epidemic  for the SIR (susceptible, infected, removed) model, one can estimate the probability $`p_m^{(1)}`$ that the first person in the community who has received a piece of information will transmit it to $`m`$ of their neighbors. Using the binomial distribution, we find

$$p_m^{(1)}=\underset{k=m}{\overset{\mathrm{}}{}}p_k\left(\genfrac{}{}{0pt}{}{k}{m}\right)T^m(1T)^{km},$$
(3)
where the superscript “$`(1)`$” refers to first neighbors, those who received the information directly from the initial source. The *transmissiblity* $`T`$ is the average total probability that an infective individual will transmit an item to a susceptible neighbor and is derived in newman02epidemic  as a function of $`r_{ij}`$, the rate of contacts between two nodes, and $`\tau _i`$, the time a node remains infective. If $`r_{ij}`$ and $`\tau _i`$ are iid randomly distributed according to the distributions $`P(r)`$ and $`P(\tau )`$, then the item will propagate as if all transmission probabilities are equal to a constant $`T`$.

$$T=T_{ij}=1_0^{\mathrm{}}𝑑r𝑑\tau P(r)P(\tau )e^{r\tau }$$
(4)
The generating function for $`p_m^{(1)}`$ is given by

$`G^{(1)}(x)`$ $`=`$ $`{\displaystyle \underset{m=0}{\overset{\mathrm{}}{}}}{\displaystyle \underset{k=m}{\overset{\mathrm{}}{}}}p_k\left({\displaystyle \genfrac{}{}{0pt}{}{k}{m}}\right)T^m(1T)^{km}x^m`$ (5)
$`=`$ $`G_0(1+(x1)T)=G_0(x;T).`$ (6)
Suppose the transmissibility decays as a power of the distance from the initial source. The probability that an $`m`$th neighbor will transmit the information to a person with whom he has contact is given by

$$T^{(m)}=(m+1)^\beta T,$$
(7)
where $`\beta >0`$ is the decay constant. $`T^{(m)}=T`$ at the originating node ($`m=0`$) and decays to zero as $`m\mathrm{}`$. Power-law decay is the weakest form of decay and the results obtained from it will also be valid for stronger functional forms such as an exponential decay.

The generating function for the transmission probability to 2nd neighbors can be written as

$$G^{(2)}(x)=\underset{k}{}p_k^{(1)}[G_1^{(1)}(x)]^k=G^{(1)}(G_1^{(1)}(x)),$$
(8)
where

$$G_1^{(1)}(x)=G_1(x;2^\beta T)=G_1(1+(x1)2^\beta T)$$
(9)
and

$$G_1(x)=\frac{_kkp_kx^k}{x_kkp_k}=\frac{G_0^{}(x)}{G_0^{}(1)}$$
(10)
is the generating function of the degree distribution of a vertex reached by following a randomly chosen edge, not counting the edge itself newman01graphs . Similarly, if we define $`G^{(m)}(x)`$ to be the the generating function for the number of $`m`$th neighbors affected, then we have

$$G^{(m+1)}(x)=G^{(m)}(G_1^{(m)}(x))\text{for }m1,$$
(11)
where

$$G_1^{(m)}(x)=G_1(x;(m+1)^\beta T)=G_1(1+(x1)(m+1)^\beta T).$$
(12)
Or, more explicitly,

$$G^{(m+1)}(x)=G^{(1)}(G_1^{(1)}(G_1^{(2)}(\mathrm{}G_1^{(m)}(x)))).$$
(13)
The average number $`z_{m+1}`$ of $`(m+1)`$th neighbors is

$$z_{m+1}=G_{}^{(m+1)}{}_{}{}^{}(1)=G_{1}^{(m)}{}_{}{}^{}(1)G_{}^{(m)}{}_{}{}^{}(1)=G_{1}^{(m)}{}_{}{}^{}(1)z_m.$$
(14)
The condition that the size of the outbreak remains finite is that at some distance $`m+1`$, fewer individuals will be infected than at distance $`m`$, i.e. the spread of the infection is halting. This can be expressed as

$$\frac{z_{m+1}}{z_m}=G_{1}^{(m)}{}_{}{}^{}(1)<1,$$
(15)
or

$$(m+1)^\beta TG_1^{}(1)<1.$$
(16)
Note that $`G_1^{}(1)`$ does not diverge when $`\alpha <3`$ due to the presence of a cutoff at $`\kappa `$. For any decaying $`T`$, the left hand side of the inequality above goes to zero when $`m\mathrm{}`$, so the condition is eventually satisfied for large $`m`$. Therefore the average total size

$$s=\underset{m=1}{\overset{\mathrm{}}{}}z_m$$
(17)
is always finite if the transmissibility decays with distance.

Wu et al. compared their model with previous results pastor-satorras01epidemic  on disease spread on scale-free networks, by considering a network made up of $`10^6`$ vertices. An epidemic was defined to be an outbreak affecting more than 1% or $`10^4`$ vertices. Thus for fixed $`\alpha ,\kappa `$ and $`\beta `$, $`T_c`$ is the critical transmissibility above which $`s`$ would be made to exceed $`10^4`$.

The numerical result of $`T_c`$ as a function of $`\alpha `$ is shown in Figure 6. When $`\beta =0`$ (there is no decay in transmission probability), $`\kappa =\mathrm{}`$ (there is no cutoff in the degree distribution), and $`\alpha <3`$, $`T_c`$ is zero and epidemics encompassing more than $`10^4`$ vertices occur for arbitrarily small $`T`$, as was found in pastor-satorras01epidemic . Keeping $`\beta `$ at zero and adding a cutoff at $`\kappa =100`$ produces a non-zero critical transmissibility $`T_c`$, as was found in newman02epidemic . For $`\alpha =2`$, a typical value for real-world networks, $`T_c`$ is still very near zero, meaning that for most values of $`T`$, epidemics do occur. However, when we impose a decay in transmissibility by setting $`\beta `$ to 1, $`T_c`$ rises substantially. For example, $`T_c`$ jumps to 0.54 at $`\alpha =2`$ and rises rapidly to 1 as $`\alpha `$ increases further, implying that the information may not spread over the network.

In order to validate empirically that the spread of information within a network of people is limited, and hence distinct from the spread of a virus, a sample from the mail clients of 40 individuals (30 within HP Labs, and 10 from other areas of HP, other research labs, and universities) was gathered. Each volunteer executed a program that identified URLs and attachments in the messages in their mailboxes, as well as the time the messages were received. This data was cryptographically hashed to protect the privacy of the users. By analyzing the message content and headers, the data was restricted to include only messages which had been forwarded at least one time, thereby eliminating most postings to mailing lists and more closely approximating true inter-personal information spreading behavior. The median number of messages in a mailbox in the sample was 2200, indicating that many users keep a substantial portion of their email correspondence. Although some messages may have been lost when users deleted them, it was assumed that a majority of messages containing useful information had been retained.

Figure 7 shows a histogram of how many users had received each of the 3401 attachments and 6370 URLs. The distribution shows that only a small fraction (5% of attachments and 10% of URLs) reached more than 1 recipient. Very few (41 URLs and 6 attachments) reached more than 5 individuals, a number which, in a sample of 40, starts to resemble an outbreak. In follow-up discussions with the study subjects, the content and significance of most of these messages was identified. 14 of the URLs were advertisements attached to the bottom of an email by free email services such as Yahoo and MSN. These are in a sense viral, because the sender is sending them involuntarily. It is this viral strategy that was responsible for the rapid buildup of the Hotmail free email service user base. 10 URLs pointed to internal HP project or personal pages, 3 URLs were for external commercial or personal sites, and the remaining 14 could not be identified.

The next portion of the analysis analyzed the effect of decay in the transmission probability on the email graph at HP Labs. The graph was constructed from recorded logs of all incoming and outgoing messages over a period of 3 months. The graph has a nearly power-law out degree distribution, shown in Figure 8, including both internal and external nodes. Because all of the outgoing and incoming contacts were recorded for internal nodes, their in and out degrees were higher than for the external nodes for which we could only record the email they sent to and received from HP Labs. A graph with the internal and external nodes mixed (as in ebel02email ) was used to specifically demonstrate the effect of a decay on the spread of email in a power-law graph.

The spread of a piece of information was simulated by selecting a random initial sender to infect and following the email log containing 120,000 entries involving over 7,000 recipients in the course of a week. Every time an infective individual (one willing to transmit a particular piece of information) was recorded as sending an email to someone else, they had a constant probability $`p`$ of infecting the recipient. Hence individuals who email more often have a higher probability of infecting. It is also assumed that an individual remains infective for a period of 24 hours.

Next a decay was introduced in the one-time transmission probability $`p_{ij}`$ as $`pd_{ij}^{1.75}`$, where $`d_{ij}`$ is the distance in the organizational hierarchy between individuals $`i`$ and $`j`$. The exponent roughly corresponds to the decay in similarity between homepages shown in Figure 5. Here $`r_{ij}=p_{ij}f_{ij}`$, where $`f_{ij}`$ is the frequency of communication between the two individuals, obtained from the email logs. The decay represents the fact that individuals closer together in the organizational hierarchy share more common interests. Individuals have a distance of one to their immediate superiors and subordinates and to those they share a superior with. The distance between someone within HP labs and someone outside of HP labs was set to the maximum hierarchical distance of 8.

Figure 9 shows the variation in the average outbreak size, and the average epidemic size (chosen to be any outbreak affecting more than 30 individuals). Without decay, the epidemic threshold falls below $`p=0.01`$. With decay, the threshold is set back to $`p=0.20`$ and the outbreak epidemic size is limited to about 50 individuals, even for $`p=1`$.

As these results show, the decay of similarity among members of a social group has strong implications for the propagation of information among them. In particular, the number of individuals that a given email message reaches is very small, in contrast to what one would expect on the basis of a virus epidemic model on a scale free graph. The implication of this finding is that merely discovering hubs in a community network is not enough to ensure that information originating at a particular node will reach a large fraction of the community.

## 4 Small World Search

In the preceding section we discussed how the tendency of like individuals to associate with one another can affect the flow of information within an organization. In this section we will show how one can take advantage of the very same network structure to navigate social ties and locate individuals.

The observation that any two people in the world are most likely linked by a short chain of acquaintances, known as the “small world” phenomenon has been the focus of much research over the last forty years milgram67 ; travers69smallworld ; lundberg75smallworld ; killworth78reverse . In the 1960’s and 70’s, articipants in small world experiments successfully found paths from Nebraska to Boston and from Los Angeles to New York. In an experiment in 2001 and 2002, 60,000 individuals were able to repeat the experiment using email to form chains with just four links on average across different contents dodds03networks . The small world phenomenon is currently exploited by commercial networking services such as LinkedIn, Friendster, and Spoke<sup>1</sup><sup>1</sup>1 http://www.linkedin.com/, http://www.friendster.com, http://www.spokesoftware.comto help people network, for both business and social purposes.

The existence of short paths is not particularly surprising in and of itself. Although many social ties are “local” meaning that they are formed through ones work or place of residence, Watts and Strogatzwatts98smallworld  showed that it takes only a few “random” links between people of different professions or location to create short paths in a social network and make the world “small”. In addition, Pool and Kochenpool78contacts  have estimated that an average person has between 500 and 1,500 acquaintances. Ignoring for the moment overlap in one’s circle of friends, one would have $`1,000^2`$ or $`1,000,000`$ friends of friends, and $`1,000^3`$ or one billion friends-of-friends-of-friends. This means that it would take only 2 intermediaries to reach a number of people on the order of the population of the entire United States.

Although the existence of short paths is not surprising, it is another question altogether how people are able to select among hundreds of acquaintances the correct person to form the next link in the chain. Killworth and Barnardkillworth78reverse  performed the “reverse” experiment to measure how many acquaintances a typical person would use as a first step in a small world experiment. Presented with 1,267 random targets, the subjects chose about 210 different acquaintances on average, based overwhelmingly on geographic proximity and similarity of profession to the targets.

Recently, mathematical models have been proposed to explain why people are able to find short paths. The model of Watts, Dodds, and Newman watts2002search  assumes that individuals belong to groups that are embedded hierarchically into larger groups. For example an individual might belong to a research lab, that is part of an academic department at a university, that is in a school consisting of several departments, that is part of a university, that is one of the academic institutions in the same country, etc. The probability that two individuals have a social tie to one another is proportional to $`\mathrm{exp}^{\alpha h}`$, where $`h`$ is the height of their lowest common branching point in the hierarchy.

The decay in linking probability means that two people in the same research laboratory are more likely to know one another than two people who are in different departments at a university. The model assumes a number of separate hierarchies corresponding to characteristics such as geographic location or profession. In reality, the hierarchies may be intertwined, for example professors at a university living within a short distance of the university campus, but for simplicity, the model treats them separately.

In numerical experiments, artificial social networks were constructed and a simple greedy algorithm was performed where the next step in the chain was selected to be the neighbor of the current node with the smallest distance along any dimension. At each step in the chain there is a fixed probability, called the attrition rate, that the node will not pass the message further. The numerical results showed that for a range of the parameter $`\alpha `$ and number of attribute dimensions, the networks are “searchable”, meaning that a minimum fraction of search paths find their target.

Kleinberg kleinberg2000navigation ; kleinberg2001dynamics  posed a related question: in the absence of attrition, when does the length of the chains scale in the same way as the average shortest path. Unlike the study of Watts. et al., there is no attrition - all chains run until completion, but need to scale as the actual shortest path in the network does. In the case of a small world network, the average shortest path scales as $`\mathrm{ln}(N)`$, where $`N`$ is the number of nodes. Kleinberg proved that a simple greedy strategy based on geography could achieve chain lengths bounded by $`(\mathrm{ln}N)^2`$ under the following conditions: nodes are situated on an $`m`$-dimensional lattice with connections to their $`2m`$ closest neighbors and additional connections are placed between any two nodes with probability $`pr^m`$, where $`r`$ is the distance between them. Since in the real world our locations are specified primarily by two dimensions, longitude and latitude, the probability is inversely proportional to the square of the distance. A person should be four times as likely to know someone living a block away, than someone two city blocks away. However, Kleinberg also proved that if the probabilities of acquaintance do not follow this relationship, nodes would not be able to use a simple greedy strategy to find the target in polylogarithmic time.

The models of both Watts et al. and Kleinberg show that the probability of acquaintance needs to be related to the proximity between individuals’ attributes in order for simple search strategies using only local information to be effective. Below we describe experiments empirically testing the assumptions and predictions of the proposed two models.

### 4.1 Method

In order to test the above hypothesis, Adamic and Adar adamic03search  applied search algorithms to email networks derived from the email logs at HP Labs already described in section 2. A social contact was defined to be someone with whom an individual had exchanged at least 6 emails each way over the period of approximately 3 months. The bidirectionality of the email correspondence guaranteed that a conversation had gone on between the two individuals and hence that they are familiar with one another.

Imposing this constraint yielded a network of 436 individuals with a median number of 10 acquaintances and a mean of 13. The degree distribution, shown in Figure 10, is highly skewed with an exponential tail. This is in contrast to the raw power-law email degree distribution, used in section 3 and shown in Figure 8, pertaining to both internal and external nodes and possessing no threshold in email volume. A scale free distribution in the raw network arises because there are many external nodes emailing just one individual inside the organization, and there are also some individuals inside the organization sending out announcements to many people and hence having a very high degree. However, once we impose a higher cost for maintaining a social contact (that is, emailing that contact at least six times and receiving at least as many replies), then there are few individuals with many contacts.

### 4.2 Simulating Milgram’s experiment on an email network

The resulting network, consisting of regular email patterns between HP Labs employees, had 3.1 edges separating any two individuals on average, and a median of 3. Simulations were performed on the network to determine whether members of the network would be able to use a simple greedy algorithm to locate a target. In this simple algorithm, each individual can use knowledge only of their own email contacts, but not their contacts’ contacts, to forward the message.

Three different strategies were tested, at each step passing the message to the contact who is either

* best connected
* closest to the target in the organizational hierarchy
* sitting in closest physical proximity to the target

The first strategy selects the individual who is more likely to know the target by virtue of the fact that he/she knows so many people. It has been shown adamic01plsearch , that this is an effective strategy in power-law networks with exponents close to 2 (the case of the unfiltered HP Labs email network), but that it performs poorly in graphs with a Poisson degree distribution that has an exponential tail. Since the distribution of contacts in the filtered HP network was not power-law, the high degree strategy was not expected to perform well, and this was verified through simulation. The median number of steps required to find a randomly chosen target from a random starting point was 17, compared to the three steps in the average shortest path. Even worse, the average number of steps is 40. This discrepancy between the mean and the median is a reflection of the skewness of the distribution: a few well connected individuals and their contacts are easy to find, but some individuals who do not have many links and are not connected to highly connected individuals are difficult to locate using this strategy.

The second strategy consisted of passing the message to the contact closest to the target in the organizational hierarchy. The strategy relies on the observation, illustrated in Figures 11 and 13 that individuals closer together in the organizational hierarchy are more likely to email with one another. Figure 12 illustrates such a search, labelling nodes by their hierarchical distance (h-distance) from the target. The h-distance is computed as follows: a node has distance one to their manager and to everyone they share a manager with. Distances are then recursively assigned, so that each node has h-distance 2 to their first neighbor’s neighbors, and h-distance 3 to their second neighbor’s neighbors, etc. A simple greedy strategy using information about the organizational hierarchy worked extremely well. The median number of steps was only 4, close to the median shortest path of 3. With the exception of one individual, whose manager was not located on site, and who was consequently difficult to locate, the mean number of steps was 4.7, meaning that not only are people typically easy to find, but nearly everybody can be found in a reasonable number of steps.

In the original experiment by Milgram the completed chains were divided between those that reached the target through his professional contacts and those that reached him through his hometown. On average those that relied on geography took 1.5 steps longer to reach the target, a difference found to be statistically significant. In the words of Travers and Milgram travers69smallworld , the following seemed to occur: “Chains which converge on the target principally by using geographic information reach his hometown or the surrounding areas readily, but once there often circulate before entering the target’s circle of acquaintances. There is no available information to narrow the field of potential contacts which an individual might have within the town.”

Performing the small world experiment on the HP email network using geography produced a similar result, in that geography could be used to find most individuals, but was slower, taking a median number of 7 steps, and a mean of 12. Figure 14 shows the email correspondence mapped onto the physical layout of the buildings. Individuals’ locations are given by their building, the floor of the building, and the nearest building post (for example “H15”) to their cubicle. The distance between two cubicles was approximated by the “street” distance between their posts (for example “A3” and “C10” would be $`(CA)25^{}+(103)25^{}=225^{}+725^{}=225`$ feet apart). Adding the $`x`$ and $`y`$ directions separately reflects the interior topology of the buildings where one navigates perpendicular hallways and cannot traverse diagonally. If individuals are located on different floors or in different buildings, the distance between buildings and the length of the stairway are factored in.

Figure 16 shows a histogram of chain lengths resulting from searches using each of the three strategies. It shows the clear advantage of using the target’s position in organizational hierarchy as opposed to his/her cubicle location to pass a message through one’s email contact. It also shows that both searches using information about the target outperform a search relying solely on the connectivity of one’s contacts.

### 4.3 Discussion

The above simulated experiments verify the models proposed in watts2002search  and kleinberg2000navigation  to explain why individuals are able to successfully complete chains in the small world experiments using only local information. When individuals belong to groups based on a hierarchy and are more likely to interact with individuals within the same small group, then one can safely adopt a greedy strategy - pass the message onto the individual most like the target, and they will be more likely to know the target or someone closer to them.

At the same time it is important to note that the optimum relationship between the probability of acquaintance and distance in physical or hierarchical space between two individuals, as outlined in kleinberg2000navigation ; kleinberg2001dynamics , are not satisfied. The general tendency of individuals in close physical proximity to correspond holds: over 87% percent of the 4000 email links are between individuals on the same floor, and overall there is a tendency of individuals in close physical proximity to correspond. Still, individuals maintain disproportionately many far-flung contacts while not getting to know some of their close-by neighbors. The relationship between probability of acquaintance and cubicle distance $`r`$ between two individuals, shown in Figure 15, is well-fitted by a $`1/r`$ curve. However, Kleinberg has shown that the optimum relationship in two dimensional space is $`1/r^2`$ \- a stronger decay in probability of acquaintance than the $`1/r`$ observed.

In the case of HP Labs, the geometry may not be quite two dimensional, because it is complicated by the particular layout of the buildings. Hence the optimum relationship may lie between $`1/r`$ and $`1/r^2`$. In any case, the observed $`1/r`$ probability of linking shows a tendency consistent with Milgram’s observations about the original small world experiment. At HP Labs, because of space constraints, re-organizations, and personal preferences, employees’ cubicles may be removed from some of the co-workers they interact with. This hinders a search strategy relying solely on geography, because one might get physically quite close to the target, but still need a number of steps to find an individual who interacts with them.

The same is true, but to a lesser extent, of the contacts individuals establish with respect to the organizational hierarchy. In Section 2 email spectroscopy revealed that while collaborations mostly occurred within the same organizational unit, they also frequently bridged different parts of the organization or broke up a single organizational unit into noninteracting subgroups. The optimum relationship derived in kleinberg2001dynamics  for the probability of linking would be inversely proportional to the size of the smallest organizational group that both individuals belong to. However, the observed relationship, shown in Figure 17 is slightly off, with $`pg^{3/4}`$, $`g`$ being the group size.

Overall, the results of the email study are consistent with the model of Watts et al. watts2002search . This model does not require the search to find near optimum paths, but simply determines when a network is “searchable”, meaning that fraction of messages reach the target given a rate of attrition. The relationship found between separation in the hierarchy and probability of correspondence, shown in Figure 13, is well within the searchable regime identified in the model.

The study of Adamic and Adar is a first step, validating these models on a small scale. The email study gives a concrete way of observing how the small world chains can be constructed. Using a very simple greedy strategy, individuals across an organization could reach each other through a short chain of coworkers. It is quite likely that similar relationships between acquaintance and proximity (geographical or professional) hold true in general, and therefore that small world experiments succeed on a grander scale for the very same reasons.

## 5 Conclusion

In this chapter we reviewed three studies of information flow in social networks. The first developed a method of analyzing email communication automatically to expose communities of practice and their leaders. The second showed that the tendency of individuals to associate according to common interests influences the way that information spreads throughout a social group. It spreads quickly among individuals to whom it is relevant, but unlike a virus, is unable to infect a population indiscriminately. The third study showed why small world experiments work - how individuals are able to take advantage of the structure of social networks to find short chains of acquaintances. All three studies relied on email communication to expose the underlying social structure, which previously may have been difficult and labor-intensive to obtain. We expect that these findings are also valid with other means of social communication, such as verbal exchanges, telephony and instant messenger systems.

Acknowledgements

We would like to thank Eytan Adar and TJ Giuli for their comments and suggestions.