Urban Road Usage Patterns

Introduction

In an era of unprecedented global urbanization, society faces a rapidly accelerating demand for mobility, placing immense pressure on urban road networks. This demand manifests in the form of severe traffic congestion, which decreases the roads’ level of service, while at the same time increasing both fuel consumption and traffic-related air pollution.

In this blog post, we look at a methodology, which employs comprehensive mobile phone data to detect patterns of road usage and the origins of the drivers. Thus, providing a basis for better informed transportation planning, including targeted strategies to mitigate congestion. We formalize the problem by counting the observed number of individuals moving from one location to another, which we put forward as the transient origin destination (t-OD) matrix.

To study the distribution of travel demands over a day we divide it into four periods (Morning: 6 am–10 am, Noon & Afternoon: 10 am–4 pm, Evening: 4 pm–8 pm, Night: 8 pm–6 am) and cumulate trips over the total observational period. A trip is defined when the same mobile phone user is observed in two distinct zones within one hour (zones are defined by 892 towers’ service areas in the San Francisco Bay Area and by 750 census tracts in the Boston Area). In the mobile phone data, a user’s location information is lost when he/she does not use his/her phone, but by defining the transient origin and destination with movements within one hour, we can capture the distribution of travel demands. Specifically we calculate the t-OD as:

where A is the number of zones. W is the one-hour total trip production in the studied urban area, a number readily available for most cities. However this number gives no information about the trip distribution between zones, which we can enhance by the information gained via mobile phones. Directly from the mobile phone data we calculate T_ij(n), which is the total number of trips that user nmade between zone i and zone j during the three weeks of study. Via calibrating T_ij(n) for the total population we obtain:  , where N_k is the number of users in zone k. The ratio M scales the trips generated by mobile phone users in each zone to the trips generated by the total population living there: M(k) = N_pop(k)/N_user(k), where N_pop(k) and N_user(k) are the population and the number of mobile phone users in zone k. Furthermore to assign only the fraction of the trips attributed to vehicles, we correct F^all_ij by the vehicle usage rate, which is a given constant for each zone and therefore obtain F^vehicle_ij .

For each mobile phone user that generated the t-OD, we can additionally locate the zone where he or she lives, which we define as the driver source. Connecting t-ODs with driver sources allows us for the first time to take advantage of mobile phone data sets in order to understand urban road usage. In the following, we present the analysis of the road usage characterization in the morning period as a case study.

Results

A road network is defined by the links representing the road segments and the nodes representing the intersections. Using incremental traffic assignment, each trip in the t-OD matrix is assigned to the road network, providing us with estimated traffic flows (Fig.1(a)). The road network in the Bay Area serves a considerable larger number of vehicles per hour (0.73 million) than the one in the Boston (0.54 million). The traffic flow distribution P(V) in each area can be well approximated as the sum of two exponential functions corresponding to two different characteristic volumes of vehicles (Fig. 1a); one is the average traffic flow in their arterial roads (v_A) and the other is the average traffic flow in their highways (v_H). We measure  (R²>0.99) with v_A = 373 (236) vehicles/hour for arterials and v_H = 1,493 (689) vehicles/hour for highways in the Bay Area (Boston numbers within parenthesis, p_A and p_H are the fraction of arterial roads and the fraction of highways). Both road networks have similar number of arterials (~20,000), but the Bay Area with more than double the number of highways than Boston (3,141 highways vs 1,267 in Boston) still receives the double of the average flow in the highways (v_H) and a larger average flow in the arterial roads.

Figure 1: Distributions of traffic flow, betweenness centrality and VOC in the two urban areas.

(a) The one-hour traffic flow V follows a mixed exponential distribution for both Bay Area and Boston Area, where constants p_A and p_H are the fraction of arterial roads and the fraction of highways, v_A and v_H is the average traffic flow for arterial roads and highways respectively. (b) The distribution of road segment’s betweenness centrality b_c is well approximated by  , where the power-law distribution approximates arterial roads’ b_c distribution and the exponential distribution approximates highways’ b_c distribution. β_Hdenotes the average b_c of highways and α_A is the scaling exponent for the power-law. (c) The volume over capacity VOC follows an exponential distribution P(VOC) = γe^−VOC/γ with an average VOC = 0.28 for the two areas. Traffic flows in most road segments are well under their designed capacities, whereas a small number of congested segments are detected.

The volume of vehicles served by a road depends on two aspects: the first is the functionality of the road according to its ability to be a connector based on its location in the road network (i.e. betweenness centrality) and the second is the inherent travel demand of the travelers in the city. The betweenness centrality b_c of a road segment is proportional to the number of shortest paths between all pairs of nodes passing through it: we measured b_c by averaging over each pair of nodes, and following the shortest time to destination. The two road networks, analyzed here, have completely different shapes: the Bay Area is more elongated and connects two sides of a bay, while the Boston Area follows a circular shape (Fig. 2a). But both have a similar function in the distribution of b_c: with a broad term corresponding to the arterial roads and an exponential term to the highways, which is at the tail of larger b_c. As Fig. 1b shows, we measure: P(b_c) =p_AP_A(b_c) + p_HP_H(b_c) (R²>0.99), with  for arterial roads and  for highways. The highways in the Bay Area have an average b_c of β_H = 2.6 × 10⁻⁴, whereas a largerβ_H = 4.6 × 10⁻⁴ is found for the Boston Area highways, indicating their different topological structures. Interestingly, despite, the different topologies of the two road networks, the similar shapes of their distribution of traffic flows indicate an inherent mechanism in how people are selecting their routes. 

Figure 2: Tracing driver sources via the road usage network.

(a) The colour of a road segment represents its degree K_road. Most residential roads are found to have small K_road, whereas the backbone highways and the downtown arterial roads are shown to have largeK_road. The light blue polygons and the light orange polygons pinpoint the MDS for Hickey Blvd and E Hamilton Ave respectively. The white lines show the links that connect the selected road segment and its MDS. The two road segments have a similar traffic flow V ~400 (vehicles/hour), however, Hickey Blvd only has 12 MDS located nearby, whereas E Hamilton Ave has 51 MDS, not only located in the vicinity ofCampbell City, but also located in a few distant regions pinpointed by our methodology. (b) The degree distribution of driver sources can be approximated by a normal distribution with µ_source = 1,035.9 (1,017.7), σ_source = 792.2 (512.3), R² = 0.78 (0.91) for Bay Area (Boston Area). (c) The degree distribution of road segments is approximated by a log-normal distribution  with µ_road = 3.71 (3.36) , σ_road = 0.82 (0.72), R² = 0.98 (0.99) for Bay Area (Boston Area).

Notice that only when the traffic flow is greater than a road’s available capacity, the road is congested; the ratio of these two quantities is called Volume over Capacity (VOC) and defines the level of service of a road. Surprisingly, despite the different values in average flows v and average betweeness centrality β, we find the same distribution of VOC (Fig. 1c) in the two metropolitan areas, which follows an exponential distribution with an average VOC given by γ = 0.28 (R²>0.98):

The exponential decay of VOC indicates that for both road networks traffic flows on 98% of the road segments are well below their designed road capacities, whereas a few road segments suffer from congestion, having a VOC > 1. The similarity between the two VOC distributions shows that in both urbanities drivers experience the same level of service, due to utilizing the existing capacities in the similar way.

The traditional difficulty in gathering ODs at large scales has until now limited the comparison of roads in regard to their attractiveness for different driver sources. To capture the massive sources of daily road usage, for each road segment with V > 0, we calculate the fraction of traffic flow generated by each driver source, and rank these sources by their contribution to the traffic flow. Consequently, we define a road segment's major driver sources (MDS) as the top ranked sources that produce 80% of its traffic flow. We next define a bipartite network, which we call the network of road usage, formed by the edges connecting each road segment to their MDS. Hence, the degree of a driver source K_source is the number of road segments for which the driver source is a MDS, and the degree of a road segment K_road is the number of MDS that produce the vehicle flow in this road segment. As Fig. 2b shows, the driver source's degree K_source is normally distributed, centered in < K_source > ~1000 in both Bay Area and Boston Area, implying that drivers from each driver source use a similar number of road segments. In contrast, the road segment's degree K_road follows a log-normal distribution (Fig. 2c), where most of the road segments have a degree centered in < K_road > ~20. This indicates that the major usage of a road segment can be linked to surprisingly few driver sources. Indeed, only 6–7% of road segments are in the tail of the log-normal linked to a larger number of MDS, ranging from 100 to 300.

In Fig. 2a we show a road segment's degree K_road in the road network maps of the Bay Area and the Boston Area. Since census tracts and mobile phone towers are designed to serve similar number of population , a road segment's degree K_road quantifies the diversity of the drivers using it. We find that K_road is lowly correlated with traditional measures, such as traffic flow,VOC and betweenness centrality b_c . For example, in Fig. 2a, Hickey Blvd in Daly City and E Hamilton Ave in Campbell City have a similar traffic flow V~400 (vehicles/hour), however, their degrees in the network of road usage are rather different. Hickey Blvd, only has K_road = 12, with MDS distributed nearby, whereas E Hamilton Ave, has K_road = 51, with MDS distributed not only in its vicinity, but also in some distant areas as Palo Alto, Santa Cruz, Ben Lomond and Morgan Hill.

As Fig. 2a shows, the road segments in the tail of the log-normal (K_road > 100) highlight both the highways and the major business districts in both regions. This again implies that K_road can characterize a road segment's role in a transportation network associated with the usage diversity. To better characterize a road's functionality, we classify roads in four groups according to their b_cand K_road in the transportation network (Fig. 3). We define the connectors, as the road segments with the largest 25% of b_c and the attractors as the road segments with the largest 25% of K_road. The other two groups define the highways in the periphery, or peripheral connectors, and the majority of the roads are called local, which have both small b_c and K_road (Fig. 3). By combining b_c and K_road, a new quality in the understanding of urban road usage patterns can be achieved. Future models of distributed flows in urban road networks will benefit by incorporating those ubiquitous usage patterns.

Figure 3: Types of roads defined by b_c and K_road.

The road segments are grouped by their betweenness centrality b_c and degree K_road. The red lines (connectors) represent the road segments with the top 25% of b_c and K_road; they are topologically important and diversely used by drivers. The green lines (peripheral connectors) represent the road segments in the top 25% of b_c, but with low values of K_road; they are topologically important, but less diversely used. The road segments in yellow are those with low values of b_c, but within the top 25% K_road; they behave as attractors to drivers from many sources (attractors). The road segments in grey have the low values of b_c and K_road, they are not topologically important and locally used (locals).

Discussion

Today, as cities are growing at an unparalleled pace, particularly in Asia, South America and Africa, the power of this modeling framework is its ability to dynamically capture the massive sources of daily road usage based solely on mobile phone data and road network data, both of which are readily available in most cities. The values of K_road and b_c together determine a road's functionality. We find that the major traffic flows in congested roads are created by very few driver sources, which can be addressed by our finding that the major usage of most road segments can be linked to their own surprisingly few driver sources. This shows that the representation provided by the network of road usage is very powerful to create new applications, enabling cities to tailor targeted strategies to reduce the average daily travel time compared to a benchmark strategy.

References

1. Batty, M. The size, scale, and shape of cities. Science 319, 769–771 (2008).

2. Barthélemy, M. Spatial networks. Physics Reports 499, 1–101 (2011).

3. Schrank, D. & Lomax, T. Annual urban mobility report (Texas Transportation Institute, 2009).

4. Helbing, D. A section-based queueing-theoretical traffic model for congestion and travel time analysis in networks. J. Phys. A: Math. Gen. 36, 593–598 (2003).

5. Chin, A. T. H. Containing air pollution and traffic congestion: transport policy and the environment in Singapore. Atmospheric Environment 30(5), 787–801 (1996).

6. Shen, W. & Wynter, L. Real-time traffic prediction using GPS data with low sampling rates: a hybrid approach. IBM Research Report RC25230 (2011).

7. Barthélemy, M. & Flammini, A. Modeling urban streets patterns. Phys Rev Lett 100, 138702(2008).

8. González, M. C., Hidalgo, C. A. & Barabási, A.-L. Understanding individual human mobility patterns. Nature 435, 779–782 (2008).

INFORMATION FLOW DURING EPIDEMICS

In this blog post I will be talking about Epidemic Information Dissemination in Distributed Systems.

Epidemic algorithms in general are  robust ,easy to deploy and highly resilent to failures.These are effective for information propagation in large peer-to-peer (P2P) systems on Internet.It is possible to adjust the parameters of an epidemic algorithm to achieve high reliability despite process crashes and disconnections, packet losses, and a dynamic network topology.The peer-to-peer (P2P) computing model offers an appealing alternative to conventional server-client model for large scale applications in distributed settings.The P2P approach gets rid of central points of failure and associated performance bottlenecks.It balances the problems—such as forwarding messages or storing data—among all system processes, each of which requires only local knowledge of the system state.

Epidemic algorithms mimic the spread of a contagious disease.Just as infected individuals pass on a virus to those with whom they come into contact, each process in a distributed system relays new information it has received to randomly chosen peers rather than to a server or cluster of servers in charge of forwarding it. In turn, each of these processes forwards the information to other randomly selected processes, and so on.

Every process that receives a message to be disseminated forwards it by default to a randomly chosen subset of other processes. Each of these infected processes in turn forwards the information to another random subset.

Once it has started, an epidemic is hard to eradicate: It only takes a few people to spread a disease, directly or indirectly, to the community at large. An epidemic is also highly resilient—even if many infected people die before they transmit the contagion or are immunized, the epidemic will reliably propagate throughout the population.

Figure of A multicast source, represented by the blue circle, sends a message to be disseminated in a system.

Epidemic algorithms exhibit bimodal behavior.

They either achieve successful delivery to almost all processes or only reach a negligible portion of the processes.

Implementing an epidemic algorithm in a practical setting requires addressing specific design constraints that the system processes resource requirements impose with respect to-:

• Membership—how processes get to know each other, and how many they need to know;

• Network awareness—how to make the connections among processes reflect the actual network    topology  to ensure acceptable performance;

• Buffer management—which information to drop at a process when its storage buffer is full;

•Message filtering—how to take into account the actual interest of processes and decrease the probability that they receive and store information of no interest to them.

Now a brief information on all these -

1.MEMBERSHIP

In Information  dissemination, every process p that receives a message can forward it only to other processes that it knows. How a given process p acquires its own specific membership information impacts the performance of subsequent disseminations and is thus central to the design of scalable implementations of epidemic algorithms.One possible solution is to integrate membership with the epidemic dissemination itself: When a process forwards a message, it includes in this message a set of processes it knows; thus, the process that receives the message can update its list of known processes by adding new ones.

Any criteria we choose should fulfill following properties :

1.Uniformity. Every process in an epidemic algorithm forwards every message it receives to a subset of processes chosen uniformly at random among all processes in the system

2.Adaptivity. If the partial view size  and the dissemination parameters are predetermined and do not evolve as the system grows the probabilistic guarantees of delivery will vary with system size.

3.Bootstrapping. A closely related question is how processes initially get to know one another. This requires some external mechanism to initiate and trigger the dynamic membership scheme.

2.NETWORK AWARENESS

     Epidemic algorithm ensures that messages are  mostly forwarded to processes within the same branch of the hierarchy, thereby limiting the load on core network routers. Only a few connections between sub- hierarchies are required to ensure successful implementation of epidemic dissemination.

One possibility is to incorporate some form of administration service that is aware of the actual hierarchy.

Another approach is to set up a two-level hierarchy in which processes favor the choice of low connectivity neighbors as infection targets.

Another solution relies on a tree-like organization of processes that induces a hierarchy and provides each process with a membership that grows logarithmically with system size.

3.  BUFFER MANAGEMENT

  Every process that receives a message must buffer it up to a certain capacity and forward it a limited number of times,each time to a randomly selected set of processes of limited size.Depending on the broadcast rate,a process’s buffer capacity might be insufficient for it to forward every message it receives enough times to achieve acceptable reliability.

Directing a process to drop new messages when its buffer is full would prevent forwarding such messages.On the other hand,instructing a process to drop old messages when its buffer is full and new messages come in could result in some old messages not being forwarded a sufficient number of times.

The process of determining the bufferers of a data  message is initiated by the source.When the bufferers are 

determined their ids are piggybacked to the data message and sent to the bufferers firstly.Then there is a tradeoff in the decision for the STL value of major aim is to distribute the buffering load to the entire bufferer request messages.If the STL value is chosen system evenly.As bufferers are distributed evenly among large enough,uniform selection of bufferers would be the peers,the load of cooperative data dissemination easily achieved since the request message will be able to would also be well distributed among the peers.

4. MESSAGE FILTERING

Ensuring that every message reaches every process in the system is the design objective when all processes are equally interested in receiving all messages. However, different groups of processes can have distinct interests. In this scenario, it might be desirable for the algorithm to first partition processes in the groups and then follow this objective for disseminating messages within each group.An alternative approach is to enable processes within a single system to express specific interests and make sure they receive the appropriate messages more precisely, to increase the probability P1 that a process receives a message it is interested in and simultaneously decrease the probability P2 that a process receives a message in which it is not interested.

Conclusion

Implementing epidemic dissemination in a largescale system requires connecting and managing the peers in a fully decentralized manner, thereby creating a peer-to-peer overlay network. Beyond the specific challenges we have discussed, a wider research agenda consists in extending the scope of epidemic algorithms from information dissemination to other applications that leverage the overlay network. Such applications would, for example, include content search, content-based publish/subscribe,and file sharing.

References-:

1.Epidemic Information Dissemination in Distributed Systems by Patrick T. Eugster ,Rachid Guerraoui,Anne-Marie Kermarrec, Laurent Massoulié.

2.Stepwise Probabilistic Buffering for Epidemic Information Dissemination by Emrah Ahi, Mine C;aglar and Oznur Ozkasap.

3.Information Dissemination using Epidemic Routing with Delayed Feedback by Yezekael Hayel and Hamidou Tembine

4.Sampling Strategies for Epidemic-Style Information Dissemination by Milan Vojnovic´, Varun Gupta, Thomas Karagiannis, and Christos Gkantsidi.

Identifying the greatest cricket team and captain using complex network

Let us today look at a very interesting application of complex networks in identifying the greatest cricket team and captain. We would numerically estimate the success of a team as well as the captain by analysing the network of interaction of competing teams and also the captains.

We will consider all Test matches played between 1877 and 2010 and ODI matches played between 1971 and 2010. The success of a team or captain is decided by the quality of win rather than number of wins alone. We form directed and weighted network of teams and their captain. We apply the diffusion based page rank algorithm on the network to rank the teams. In short we would quantify the success of the teams and their captains.

Networks of Cricket Teams

Three teams A,B and C compete against each other. If A defeats B, a directed link is establised from B to A. The thickness of the link is proportional to the fraction of wins between A and B. Thus considering all the teams a weighted and directed graph if formed. We quantify the relevance of matches with the use of a complex network approach equivalent to the one used for the computation of page rank score.

Mathematically, the process is described by the following set of equations

where wji is the weight of the link and sj(out) is the out strength of a link. pi is the page rank score assigned to team i and represents the fraction of the overall "influence" sitting in the steady state diffusion process on vertex i. q is a control parameter that accounts for the importance of the various terms contributing to the score of the nodes and N is the total number of teams in the network.

The network of teams in the history of Test cricket (1877−2010)

Results

The choice of q is set at 0.15 and ranking scheme is run on networks of cricket teams and also on their captains. As expected Australia is identified as the most successful team in both forms of the cricket. Steve Waugh is ranked as the best caption in test format and Ricky Ponting as the best caption in ODI.

Subgraph of most successfull captions

Conclusion

The work demonstrates the strength of social network analysis methods in quantifying the success of cricket teams and their captains. The correct assessment of a team's success needs the consideration of entire network of interaction. The Page Rank algorithm takes into account the quality of matches won. For example, a win against a strong team is more important than a win against a weak team. The analysis shows that Page Rank algorithm is effective in finding the most successful team and caption in the history of cricket.

References :

1. Bailey, M. J. and S. R. Clarke (2004): “Market inefficiencies in player head to head

betting on the 2003 cricket world cup,” Economics, Management and Optimization

in sport, 185–201.

2. Radicchi, F. (2011): “Who is the best player ever? a complex network analysis of the hostory of professional tennis," Plos ONE, 6, e17249

3. Onody, R. N. and P. A. de Castro (2004): “Complex network study of brazilian

soccer players,” Phys. Rev. E, 70, 037103.

Internet of things

The year 2013 is called to be the year of internet of things(IoT) and the decade to be the Internet of Everything (IOE) . This technology means to make internet to be extended to make it a part of our lives, and our lives extended to be a part of internet.

Speaking of an example scenario, just imagine that every light switch, device (TV, Fridge) and door lock in your house being connected to each other and the internet. So that you can adjust the overall brigthness of your living room to your preferred level of lumens. Now imagine that you can do that from anywhere in the world, through your mobile phone?  

and then of these devices could theoretically be connected to a wider grid, containing for example street lights. The system could then measure the amount of light that your house emits, couple it together with the amount of light needed on the street and power the street lights accordingly. If you connect light sensors and motion sensors to the grid, you can have the lights follow your car on a highway and not have any lights anywhere where it is not needed. This interconnectedness is what machine to machine communications could become. This new internet can and will be an order of magnitude bigger than what we currently have.


Some characteristics and architectural details:
Radio-frequency identification (RFID) is  seen as a prerequisite for the Internet of Things
The idea of Unique addressability of things is based on the  RFID-tags and unique identification through the Electronic Product Code.
The system will likely be an example of event-driven architecture, bottom-up made
In an Internet of Things, the meaning of an event will not necessarily be based on a deterministic or syntactic model but would instead be based on the context of the event itself: this will also be a semantic web. Consequently, it will not necessarily need common standards that would not be able to address every context or use: some actors (services, components, avatars) will accordingly be self-referenced and, if ever needed, adaptive to existing common standards (predicting everything would be no more than defining a "global finality" for everything that is just not possible with any of the current top-down approaches and standardizations). The Internet of objects would encode 50 to 100 trillion objects, being a system of Semi-open or closed loops (i.e. value chains, whenever a global finality can be settled) it will therefore be considered and studied as a Complex system,
e.g.

Image courtesy :  http://fixingpotholes.com/blog/2010/07/18/the-internet-of-things-in-public/

An IBM introduction to the Internet of Things by Mike Wing, Andy Stanford-Clark and John Tolva

Some of the external Impacts and challenges induced:
1) IoT is the emerging reasearch area for the wireless sensor networks
With  IoT the data transmission requirements increase rapidly. So, the sensor nodes with limited capability and energy have to be taken care of in the transmission scenarios for better network life
MAC protocols design considerations like e.g. multiple channels for transmissions etc are to be considered.
2)With the increase in the network size and topology routing algorithms would always be challenged
3)... This list is long as the IoT is adding features and functionalities to the existing Internet as such so the reasearch problems would arise in say, every network layer.

References:
http://www.symplio.com/2011/09/4-infographics-about-internet-of-things/
http://www.arcticstartup.com/2013/02/06/the-next-decade-is-the-internet-of-things
http://www.iot-a.eu/public
http://en.wikipedia.org/wiki/Internet_of_Things

Devidas Puranik
(Roll no: 12CS60S02)

‘Sexual Networks’ reveal complex mating game and affect HIV prevention

Well its sounds totally insane!. How can any mathematical model of complex networks govern of how we select our mating partners? Can animal instincts be modeled like that?Can we fight HIV more effectively just by observing some graph on a paper?.... really its a long list of intriguing questions.

Well for starters this is a mystery and this blog entry attempts to shed some light into it.

A sexual network is a social network that is defined by the sexual relationships within a set of individuals where an individual is a node and links represent sexual interactions. Sexual networks can be used to describe the sexual interactions in animal populations and reveal which individuals are directly competing in the mating game [1]

These 'sexual networks' can unlock how sexual selection operates in animal societies where females often mate with multiple males(strange! but blame it totally on research findings... :P). The network-based approach could also help to study the spread of sexually-transmitted diseases.

For centuries naturalists believed that most organisms played a very simple mating game in which a subset of males and females in the population would form monogamous reproductive pairs.Charles Darwin himself identified sexual selection, the selection of this successful subset, as the agent responsible for the evolution of a bewildering diversity of extravagant traits utilized in competition over reproductive opportunities.

Yet recent studies have undermined this simple view of sexual interactions. They show that, far from being monogamous, females often mate with multiple males – a process called polyandry – and that the sexual dynamics within polyandrous societies are typically highly-structured with sexual interactions being far from random as individuals choose and compete over mates within non-random groups.

By using the information gained from studying 'sexual networks' we can dissect the way that sexual selection operates on a particular trait both in the local and global population.This paper[1] demonstrates that this new approach allows for more accurate estimates of sexual selection particularly at intermediate levels of polyandry. We can also use our approach to examine the spread and impact of sexually-transmitted diseases across a particular population.

The issue shows how polyandry is emerging as a lens through which scientists can better resolve their understanding of a diverse range of ecological and evolutionary processes, from selfish genetic elements to extinction risk and conservation.

For the first time, complex network scientists have mapped the romantic and sexual relationships of an entire high school over 18 months, providing evidence that these adolescent networks may be structured differently than researchers previously thought.

The results showed that, unlike many adult networks, there was no core group of very sexually active people at the high school. There were not many students who had many partners and who provided links to the rest of the community.

Instead, the romantic and sexual network at the school created long chains of connections that spread out through the community, with few places where students directly shared the same partners with each other. But they were indirectly linked, partner to partner to partner. One component of the network linked 288 students – more than half of those who were romantically active at the school – in one long chain. (See figure for a representation of the network.)

Research finding compares this network to rural phone lines, running from a long main trunk line to individual houses. As a comparison, many adult sexual networks are more like an airline hub system where many points are connected to a small number of hubs but indeed it is a very different kind of network.

The results have implications for designing policies to stop the spread of sexually transmitted diseases among adolescents.

The most striking feature of the network was a single component that connected 52 percent of the romantically involved students.This means student A had relations with student B, who had relations with student C and so on, connecting all 52%(288/554) of these students.While this component is large, it has numerous short branches and is very broad – the two most distant individuals are 37 steps apart. (Or to use a currently popular term, there were 37 degrees of separation between the two most-distant students :P)

From a student’s perspective, a large chain like this would boggle the mind.They might know that their partner had a previous partner. But they don’t think about the fact that this partner had a previous partner, who had a partner, and so on.What this showed is that there are many of these links in a chain, going far beyond what anyone could see and hold in their head.

Outside of this large component, there were numerous other smaller components in the network . There were 63 simple pairs – two individuals whose only partnership was with each other.All told, only 35 percent of the romantically active students (189) were involved in networks containing three or fewer students. There were very few components of intermediate size (4 to 15) students.

While many students were connected to much larger networks, they probably didn’t see it that way. In fact, they probably had no idea of their connections to the network.Many of the students only had one partner. They certainly weren’t being promiscuous. But they couldn’t see all the way down the chain.

The surprising thing about the network was the near absence of cycling –- situations in which people have relationships with others close to them on the network.

The lack of cycling seems traceable to rules that adolescents have about who they will not date. The teens will not date (from a female perspective) one’s old boyfriend’s current girlfriend’s old boyfriend. This would be considered taking “seconds” in a relationship.

If you break up with someone, you may want to get as away from them as possible in your next relationship. You don’t want to be connected to them in some way by dating someone with a close relationship.

The practical result from such a rule is that no cores form, and that long, chain-like networks form instead. That has important implications for preventing the spread of STDs in teenage populations.

In adult populations, in which there are cores of sexually active people who are the main conduits of disease, you can focus education and other efforts to this select group.

But in the case of adolescents there aren’t any hubs to target, so you have to focus on broad-based interventions.

This also means it matters less which people you reach with your efforts. Networks such as the one discussed are extremely fragile and just breaking one link in the chain – any link - will stop that part of the network from spreading any further. If enough links are broken, the spread of STDs can be radically limited.

Focusing on risk behavior alone does not explain why some persons and communities continue to be infected with HIV and other sexually transmitted diseases (STDs) more than others. Networks help explain why persons can have the same risk behavior and yet one may have a much greater risk of contracting or transmitting HIV.

Hope this gives the reader a useful insight into the world of ‘Sexual Networks’ and the sheer power of Complex Networks.

References

(1)Chains of Affection: The Structure of Adolescent Romantic and Sexual Networks

 by: Peter S. Bearman, James Moody, Katherine Stovel,American Journal of   Sociology, Vol. 110, No. 1. (July 2004), pp. 44-91

(2) R.J. Thorton, ‘Preventing AIDS: A new paradigm for a new strategy’, 2008,http://wiredspace.wits.ac.za.  

(3) Reinking, D., et al., 1994. Social transmission routes of HIV: A combined and life course perspective. Patient Education and Counseling, 24, pp.289-297.

(4) ‘Sexual networks and STI: A brief overview’, Centre for Health Training, 2009,http://www.centerforhealthtraining.org.

(5) D. Wohlfeiler and J. Potterat, ‘How do sexual networks affect HIV/STD prevention?’, 2003,http://caps.ucsf.edu; Adimora, A.A., and Schoenbach, V.J., 2005. Social context, sexual networks, and racial disparities in rates of sexually transmitted infections. Journal of Infectious Diseases, 191(1), pp. 115-122. 

(6) Liljeros, F., Edling, C.R., and Nunes Amaral, L.A., 2003. Sexual networks: Implications for the transmission of sexually transmitted infections. Microbes and Infection, 5, pp.189–196.

(7) Mah, T., and Halperin, D., 2010. Concurrent sexual partnerships and the HIV epidemics in Africa: Evidence to move forward. AIDS and Behavior, 14(1), pp.11-16. 

(8) ‘Expert think tank meeting on HIV prevention in high-prevalence countries in southern Africa’, SADC, 2008, http://www.sadc.int.

(9) Shelton, J.D., 2009. Why multiple sexual partners? The Lancet, 374, pp.367-69; Kenyon, C., Boulle, A., Badri, M., and Asselman, V., 2010 Journal of Social Aspects of HIV/AIDS, 7(3), pp.36-43.

(10) Wikipedia: http://en.wikipedia.org/wiki/Sexual_network