Location-Based Social Networking Data

Trip distribution is an invaluable portion of the transportation planning process; this distribution leads to the creation of origin–destination (O-D) matrices. Location-based social networking (LBSN) has increased in popularity and sophistication and has emerged as a new travel demand data source. Users of LBSN provide location-sensitive data interactively with mobile devices, including smartphones and tablets. These data can provide O-D estimates with significantly higher temporal resolution at a much lower cost in comparison with traditional methods. An LBSN O-D estimation model based on the doubly constrained gravity model was proposed to improve a previously proposed model based on the singly constrained gravity model. The proposed methodology was calibrated and comparatively evaluated against the O-D matrix generated by the method based on the singly constrained gravity model as well as a reference matrix from the local metropolitan planning organization. The results of this method illustrate significant improvement in reducing the O-D estimation errors caused by the sampling bias from the method based on the singly constrained gravity model.

Trip distribution is a significant step in the transportation planning process; it generates the static or dynamic origin-destination (O-D) trip patterns to be used by traffic assignment models. The existing data collection methods for trip distribution can be classified into three main categories: survey based, traffic count based, and positioning technology based. Survey-based methods such as telephone, in-person interview, mail, or e-mail survey can collect complete sociodemographic information of travelers and households and trip information. These methods are time-consuming and labor intensive and can only generate static travel demand information at low frequency (e.g., every 5 to 10 years) because of funding and resource limitations. Methods based on traffic counts calibrate an O-D matrix based on traffic detector data (1)(2)(3)(4)(5). These methods are relatively low in cost and can provide dynamic O-D information if calibrated properly. However, they require an existing O-D matrix and rely on traffic assignment models to generate accurate traffic flow data to be compared with field detector data in model calibration. The use of positioning technologies for O-D data collection has the potential of producing O-D data with much higher spatial and temporal resolution, larger sample size, and less cost than survey-based methods (6)(7)(8). The complication lies in (a) the penetration rate of a specific positioning technology in the mobile devices of travelers, (b) privacy protection, and (c) the uncertainty in determining trip purposes and destinations because of positioning errors.
In the United States, the affordability and accessibility attributed to recent technological advances has allowed smartphones and tablets with location-based service features to be available to individuals of diverse income levels. This development in conjunction with the fast expansion of social networks attracts a substantial number of users active in relaying their personal activities online, often including their locations. Location-based social networking (LBSN) combines the aspects of social networking with location-based service features; LBSN provides some advantages over other positioning technologies (9). Users produce trip purposes and destination information through applications with built-in GPS by checking in at particular venues. The sample provided from this methodology has the potential to be larger than that of other methods because of the penetration rate of social networking services, which are growing at a rapid pace. Furthermore, the lack of auxiliary data collection devices and availability of real-time updated data make this method of data collection an attractive low-cost option. In a previous study, a method based on a singly constrained gravity model was proposed and evaluated (10). Although the study revealed promising potential of LBSN data for O-D estimation, the proposed model still has some limitations, especially the significant bias in O-D patterns related to short-distance trips and residential areas.
A method based on a doubly constrained gravity model is proposed whose improved learning capability, when compared with the singly constrained method, during model calibration can reduce the sampling bias of LBSN check-in data.

State-of-Practice review on o-d Estimation
Conventionally, O-D matrices are derived by expanding sample O-D matrices collected from traditional household travel behavior surveys based on sociodemographic and economic data for a planning area.

Location-Based Social Networking Data
Exploration into use of doubly constrained gravity Model for origin-destination Estimation These survey methods include personal home interviews, telephone interviews, mail survey, and Internet survey. Personal home interviews are one of the most complete data sources with the highest response rate, 60% to 70%, when compared with other household survey methods (6). Home interviews are the most expensive and timeconsuming method, whereas telephone, mail, and Internet-based surveys involve significantly less cost and time. This reduction in time and cost comes with a decrease in response rate and introduces sampling bias. In recent years, travel surveys assisted by GPS have become popular both in the United States and internationally (11). However, significant incentives as well as logistical issues, including battery outages leading to incomplete data and loss of GPS units, have been identified. Moreover, studies have shown that participants may be burdened by the extended length of GPS surveys, equipment complications, and privacy concerns (11), and samples are often biased (7).
Traffic counts have been implemented as a data collection method for use in O-D matrices. Studies have shown that O-D matrix creation is possible given traffic volumes for each transportation link (1)(2)(3)(4)(5)12). However, many different matrices can be reproduced from observed traffic counts, and deployment of a comprehensive detector infrastructure on all viable routes would be required. In addition, concerns about the accuracy of estimated traffic conditions between fixed detectors have been discussed in recent research efforts (13). A complementary survey method for the traffic count-based method is the roadside intercept survey, which provides additional information regarding the O-D composition of traffic flow in a road section.
In recent years, secondary planning data sources, such as GPS, cell phone, and Bluetooth, have caught researchers' attention. As opposed to the aforementioned GPS-based survey, recent research efforts have demonstrated the feasibility of replacing traditional survey methods with O-D data directly derived from GPS trajectories generated by travelers' in-vehicle devices (6,8). Cell phones have been explored for their data collection capabilities through their employment of wireless location technologies. Studies have shown that cell phone technologies are both theoretically and experimentally feasible with reasonably precise estimation results (14,15). Penetration rates needed to achieve the spatiotemporal coverage of a network are between 2% and 3% (16). There are limitations with the technology. The spatial resolution of the cell phone positions may be within a cellular cell or location area that may include multiple travel analysis zones (TAZs). The method based on location-based service can significantly increase the spatial resolution, but users may not turn on the location-based service function or report their location-based service data because of privacy concerns. Recently, Bluetooth has been noted to be a low-cost and user-friendly method for data collection (17)(18)(19). Use of a unique media access control assigned by each device's manufacturer alleviates privacy concerns affiliated with other methods of data collection. However, the technology is limited by the short ping cycle, which could lead to over sampling of devices; the potential for a single vehicle to have multiple Bluetooth-capable devices; as well as the ability to turn off Bluetooth functions in a device. In addition, the variability of Bluetooth samples could yield objectionable expansion errors; this problem negates the technology's ability to independently create an estimate for an O-D matrix (20).
Currently, research is being conducted to determine the ability for "big," vehicle-to-infrastructure, and smartphone data to be used for O-D matrix creation. Big data include transactional (i.e., credit card purchases and payment records and product and service logs), interactional, and observational data (21). Although these data sources have great potential, there are limitations to their incorporation into transportation planning, specifically with the ability for data to be shared. Also, data capture, management, and storage pose potential difficulty with utilization, and biases may exist. Similar to the credit card data mentioned within big data, transactional data have been researched for potential use to improve transit planning (22). Utsunomiya et al. noted that concerns with market penetration, sampling bias, privacy concerns, as well as errors with transaction and routing assignment exist with the method (22). Vehicle-to-infrastructure technology has recently been explored as providing a potential new data source; research indicates that the use of the dedicated shortrange communications connecting vehicles to infrastructure would have the potential to collect data on every vehicle in the system and effectively eliminate the need for an estimated O-D matrix (23). With the exception of vehicle-to-infrastructure test beds, this method of data collection is not currently viable and privacy concerns would need to be addressed before its acceptance.

Location-Based Service and austin LBSn data characteristics
Location-based services are services that use location and time data as a control feature. This feature has been encompassed within social networking to create LBSN. With the increased popularity of sites like Facebook, Twitter, and Foursquare, which include LBSN, this form of data collection has been explored recently for comprehension of user spatial patterns. The first study exploring this area was by Li and Chen, who used the Markov-based location predictor to determine future locations of users with an accuracy of 49% (24). The relationships between geographic movements, the temporal dynamics of human movements, and social networking ties were investigated in various studies (9,25,26). In addition, studies by Backstrom et al. and Cheng et al. demonstrated the ability to predict user locations via the user's friends and content, respectively (27,28).
Many social networking sites have added features that allow users to check in to a place of interest, which is called a venue. This capability allows individuals to share and save places that have been visited with fellow users and friends. Foursquare is the most popular site that includes this feature, and as of January 2013 it had more than 30 million users worldwide with over 3 billion check-ins. Users of this particular site include businesses, which encourage check-ins through promotions and discounts. Because of the site's popularity, high penetration rate, and large sample size, researchers have used the available LBSN data to investigate mobility patterns across spatial, temporal, and social aspects (29,30).
Yang et al. were among the first to use Foursquare data to specifically estimate an O-D matrix (10). This study examined noncommuting trips in the Chicago urban area and demonstrated the promising potential of the methodology. Jin et al. furthered this effort by examining the use of check-in data to analyze the O-D demand for Austin, Texas, with a singly constrained gravity model with a two-regime friction factor; the study illustrated the potential of LBSN data for travel demand analysis and monitoring (31). The detailed LBSN O-D estimation model based on a singly constrained gravity model is as follows: where P i = productions for zone i; . . . , P indicates the pth venue type; A j = attractions for zone j; γ = adjustment factor to zonal trip production from Foursquare check-in counts; ε = adjustment factor to zonal trip attractions for Foursquare check-in counts; 1/NΣ i (γ − ε)x i = residual term for zone i that ensures total production equal to total attraction; T ij = number of trips between origin zone i and destination zone j; and F(d ij ) = friction function, where d ij is the travel cost between zones i and j.
For the calibration of the model, the trip-balancing process is applied to the following equations iteratively: where n is a step in the iterative process.

MEthodoLogy
The proposed model attempts to address several limitations from the previous model. First, the zonal productions and attractions generated by the previous model usually result in symmetric patterns due to the uniform distribution of the residual term among all zones (see Equation 2). Second, the singly constrained model only tunes the zonal attractions. Third, the convergence rate of the singly constrained gravity model is relatively slow, which causes the model calibration to be slow and premature. For those limitations to be addressed, a new model based on a doubly constrained gravity model and zone-specific residual assignment is proposed: where ρ = power of location factor, β i = balancing factor for productions, α j = balancing factor for attractions, and x ρ i /Σ j x ρ i = factor to redistribute the residual on the basis of zonal check-in counts for zone i.
In this way, the residuals are assigned on the basis of the check-in intensity rather than even distribution among all zones. The initial values of P i and A j are calculated directly from the Foursquare checkin counts on the basis of Equations 6 and 7. T ij is then calculated from P i and A j on the basis of Equation 8.
The doubly constrained model can be calibrated by iteratively updating α j and β i . In this study, α j (0) = 1 and β i (0) = 1. The values of α j and β i are updated by using the following equations: For consistency, the same friction function was engaged for the doubly constrained model that provided the best coincidence ratio (CR) in the singly constrained model. The CR measures the percentage of the area that coincides for the two curves or distributions that are being compared (32). The friction function combined the linear model for short trips and the negative exponential model for long trips as follows: where θ, λ, µ, ρ, and σ are factors that were optimized through the genetic optimization algorithm and d ij is the Manhattan distance in miles between the centroids of origin zone i and destination zone j. The dual-regime formulation is used to capture the special treatment by Texas Capital Area Metropolitan Planning Organization (CAMPO) on O-D pairs with short distances.

Study area
The city of Austin, Texas, was selected as the study area. Austin is a diverse city that encompasses an area of 272 mi 2 and has an estimated population of almost 1 million. The city of Austin (33) was demographically compared with U.S. Foursquare users (34) as well as the general U.S. population (35), as shown in Figure 1. Foursquare users include a higher proportion of individuals between the ages of 25 and 54; this segment constitutes 80% of the site's users. This age group also has a greater distribution than is seen in Austin and in the United States. In addition, there are significantly more female users of Foursquare (65% women compared with 35% men); this distribution is also notably different from the distribution of gender in Austin and the United States. Examination of the educational and income trends of the Foursquare user in the income categories of $25,000 through $74,999 as well as in the Some College category reveals an overrepresentation as compared with the Austin and U.S. data. Finally, Foursquare prohibits users under the age of 13; this distribution is shown in the percentages of 17 and under and Less Than High School users. The foregoing potential sampling bias needs to be properly addressed when the number of Foursquare check-ins is converted to trip counts. CAMPO has identified 520 TAZs in the jurisdiction of the City of Austin; this area will serve as the study area for this paper. CAMPO's 2005 travel demand model serves as the reference data used for the analysis. CAMPO data are not considered the ground truth data because of the limitations of current data collection methods. These data serve as reference data for identifying critical empirical O-D patterns. The trip purposes identified in the CAMPO study were combined into eight categories: 1. Home-based work, 2. Home-based nonwork retail, 3. Home-based nonwork other, 4. Home-based nonwork University of Texas, 5. Nonwork airport, 6. Non-home-based work, 7. Non-home-based other, and 8. Non-home-based external.

Data Collection
Foursquare data were collected by first identifying the venues in the study area. Figure 2 shows the 19,710 venues identified in the study area; this distribution demonstrates the special coverage of the data. All TAZs with the exception of three had at least one venue, and the majority of venues were located in the denser urban areas.
Once the venues were identified, a trolling algorithm was used to collect check-ins for the creation of an hourly rate for each venue during the analysis period, Tuesday, June 11, through Tuesday, July 2, 2012. The data collected included the venue ID, venue name, category, latitude, longitude, number of check-ins per hour, and the number of unique users. An initial analysis of the checkins was performed to verify that a category was assigned to each venue. These categories (Table 1) include Arts and Entertainment, Colleges and Universities, Food, Professional and Other Places, Nightlife Spots, Residences, Great Outdoors, Shops and Services, and Travel and Transport. Since categories are assigned by venue creators and are optional, some venues did not have a category assignment. For those venues, a keyword search was performed when possible to assign the appropriate primary category. Table 1 provides a categorical breakdown of the number of venues and check-ins collected. Of the 10 venue categories, Shops and Services has the largest percentage of venues, and the lowest percentage is associated with Nightlife Spots. Check-ins are most frequently associated with Shops and Services and Food, which account for 51.3% of all check-ins. The Residences category has the least number of check-ins at 2.7% and a moderately low number of venues in the sample size. The average number of check-ins per venue was also calculated for each category; the largest average number of check-ins comes from the Nightlife Spots category (1,224 check-ins) and the least comes from the Unclassified category (67 check-ins). The top three average check-ins were in the previously mentioned Nightlife Spots, as well as the Food and Travel and Transport categories. Although the findings for Nightlife Spots

FIGURE 1 Comparative demographics: (a) age, (b) gender, (c) household income, and (d ) education.
and Food categories are to be expected since they involve social activities, the large number of Travel and Transport check-ins is unexpected. In addition, because of the low percentage (1.5%) of check-ins for the Unclassified category, it was determined that their removal from the study would not negatively affect the analysis.

Model Calibration
For calibration of the proposed model, a genetic algorithm was implemented. This algorithm in MATLAB optimizes through the mimicking of the principles of biological evolution via the repeated modification of a population of individual points by using rules modeled on gene combinations in reproduction. This optimization strategy was selected for the improved chances of finding a global solution due to the algorithm's random nature. With the algorithm's calculations, individuals are randomly selected from the current population and used as parents of the children for the next generation. This process is repeated and the population eventually evolves toward an optimal solution. The genetic algorithm was used to obtain parameters for the friction function and the production and the attraction calculations that would in turn minimize the mean absolute error (MAE) between the modeled O-D matrix and the reference CAMPO O-D matrix. For  where p w M is the percentage of trips within the trip length interval w in the predicted trips from the check-in data, in which the trip length interval is used to aggregate the trip counts with an aggregation interval of 1 mi (1.609 km), and p w O is the percentage of trips within the trip length interval w in the survey trips from CAMPO.
The value for the CR ranges from 0 when the distributions are completely different to 1 when the distributions are exactly the same. For this study, the higher the CR between the check-in and the CAMPO results for each model, the better the model. Table 2 provides the results from the genetic optimization. In general, the calibrated parameters are similar except for the attraction scaling factor ε and the friction factor function parameters θ and σ. Significant improvement can be observed for the CR-and MAE-values from the proposed model.

ExPEriMEntaL EvaLuation
A comparison between the calibrated singly constrained, doubly constrained, and CAMPO O-D matrices was done by examining the trip length distributions, the zonal trip production and attraction rates, and the zonal O-D flow patterns.

trip Length distributions
As with the CR, trip length distribution curves were examined to illustrate how closely the model output data match the reference data. Figure 3 shows the trip length distributions (a, b) and the cumulative trip length distributions (c, d) for the singly and doubly constrained models compared with the reference CAMPO O-D matrix. Examination of the trip length distribution shows that the doubly constrained model (Figure 3, c and d) is relatively constant with respect to the general curvature. However, for the singly constrained model (Figure 3, a and b), under estimation occurs for short trips and slight overestimation occurs for long trips. For the singly constrained cumulative distribution (Figure 3b), slight underestimation is consistently shown for the curve. Although the curves do generally follow the same paths, the deviations indicated lend themselves to further fine-tuning of this method.

Zonal Production and attraction rates
For the validity of the methods used to associate the check-ins with the various venues throughout the study area to be determined, heat maps were created that show the productions and attractions for each model. Figure 4a demonstrates where the methodology excels and where there are limitations for the production calculations. With the CAMPO production map as a reference map, the singly constrained model shows high-production areas that are significantly fewer in number. In addition, the singly constrained model shows a midlevel production area through the study region whereas the CAMPO map is more polarized. Conversely, the doubly constrained map shows production rates that are similar in magnitude to those on the CAMPO map through the study region, where TAZs that include the central business district, airport, as well as areas dense with living, entertainment, retail, and food venues are consistently depicted as large production generators. Figure 4b provides heat maps for the attractions of each model; the maps highlight where the methodology excels and where there are limitations for the attraction calculations. Once again, with the CAMPO attraction map as the reference, the singly constrained model predicts attraction rates similar to those of the CAMPO model for many areas, but it suffers from the inability to associate high attraction rates with all of the TAZs identified in the CAMPO map. The doubly constrained map demonstrates the model's ability to better identify areas with high attraction rates. However, the map highlights areas where overestimation occurs, namely, in the northwestern portion of the map. Although CAMPO data are used as a reference, the data still have limitations, for example, the high variations in trip frequencies among zones potentially caused by under-or oversampling in certain zones.

Model Matrix comparison
The next step in the analysis of the methodology was to examine the zonal flow pattern for each model; this pattern can be regarded as the visualization of the O-D matrices. Destination zones are located along the horizontal axis, and origin zones are along the vertical axis ( Figure 5). The O-D flow intensity, I ij , is calculated as follows: 10 15 The O-D heat maps discussed next were used to provide an illustration of the distribution of trip intensities among TAZs. Each grid (i, j) in the O-D heat map indicates the I ij value from zone i to zone j; higher values are illustrated by lighter colors. A light horizontal or vertical band indicates a high production or attraction zone and light areas indicate heavily interacting zones. A difference diagram is also shown ( Figure 5, d and h) to demonstrate how the estimation error is distributed among the different O-D pairs. Overall, the heat maps provide a more detailed description of O-D patterns and error distributions as compared with a single performance measure.  Figure 4. In addition, the MAE matrix is provided to demonstrate how closely the estimated Foursquare matrix matches the CAMPO matrix.     The feasibility of using the LBSN data to analyze the urban travel demand pattern with a doubly constrained gravity model is investigated. Check-in data from Foursquare, a leading LBSN provider, were used to create production and attraction rates for the singly and doubly constrained gravity models, which were used in conjunction with the CAMPO O-D matrix to examine the predictability of the proposed methodology.

Method Based on Doubly Constrained Gravity Model
In comparison with the traditional methods used for O-D estimation, this study shows that LBSN data have potential. LBSN data are a low-cost option for updating the O-D matrix since the only cost comes from purchasing the historical data from Foursquare, Twitter, or other LBSN data vendors. The O-D matrix can be updated annually, monthly, or weekly depending on the requirements of the metropolitan planning organization. Compared with the prevailing secondary data methods based on GPS, Bluetooth, and cell phones, the LBSN data have user-confirmed trip purposes and destinations; this advantage eliminates the need for conducting reverse geocoding and recurrent trip pattern recognition. Furthermore, because of its intensive spatial and temporal coverage, LBSN data have the potential to become a promising dynamic travel demand data source for active traffic and demand management solutions (36).
LBSN data also have their bias for different venue types (e.g., residential areas, recreational locations, and tourist attractions). In comparison with the method of the existing singly constrained gravity model, the proposed method based on the doubly constrained model demonstrates better learning capabilities. There are some limitations with the proposed methodology that should be examined in future research. The model results still indicate some geographical bias for tourist regions (i.e., the northwest region in Figure 4) and residential areas. In addition, the estimated O-D matrix still has significant error for intrazonal trips (the diagonal in Figure 5). Further examination into the temporal aspects of the models as well as specific trip purposes should be done to further validate this proposed methodology.

acknowLEdgMEntS
The authors thank Foursquare for allowing the research team to obtain data through the programming interface of their developer application and the Capital Area Metropolitan Planning Organization for providing the 2010 O-D data used in this study.


extfieldsofstudy:
Computer Science
Medicine

text:
Efficient generation of connectivity in neuronal networks from simulator-independent descriptions

Simulator-independent descriptions of connectivity in neuronal networks promise greater ease of model sharing, improved reproducibility of simulation results, and reduced programming effort for computational neuroscientists. However, until now, enabling the use of such descriptions in a given simulator in a computationally efficient way has entailed considerable work for simulator developers, which must be repeated for each new connectivity-generating library that is developed. We have developed a generic connection generator interface that provides a standard way to connect a connectivity-generating library to a simulator, such that one library can easily be replaced by another, according to the modeler's needs. We have used the connection generator interface to connect C++ and Python implementations of the previously described connection-set algebra to the NEST simulator. We also demonstrate how the simulator-independent modeling framework PyNN can transparently take advantage of this, passing a connection description through to the simulator layer for rapid processing in C++ where a simulator supports the connection generator interface and falling-back to slower iteration in Python otherwise. A set of benchmarks demonstrates the good performance of the interface.

INTRODUCTION
The central nervous systems of vertebrates and many invertebrates have complex patterns of connections. In developing neuronal network models of such systems, there are two main tasks related to connection patterns. The first is to express the connectivity in a machine-readable format, e.g., in code or in a configuration file. The second is to explain the connectivity unambiguously in prose in an article or book, so that the model can be understood and reproduced by someone else (Nordlie et al., 2009).
For expressing connectivity in code, three methods are commonly used: (1) procedural code written by the modeler, using low-level operations such as connecting pairs of neurons or connecting a single neuron to a group; (2) a library of pre-defined, parameterized connection routines; (3) an explicit list of connections. Each of these have their limitations. Procedural code and libraries limit the connectivity descriptions to a single language and often a single simulator, making it hard to port models from one simulator to another. Procedural code takes time to write, and will have more bugs than a library, since library code is likely to be more thoroughly tested and reused. On the other hand, the connectivity patterns available from a library are inevitably more limited than those that can be achieved with user-written code. Using an explicit list of connections is largely independent of a particular simulator or programming language, but may cause problems of storage and input/output efficiency, and does not enable conceptual descriptions of connectivity. All of these methods make it difficult to explain the connectivity in a scientific text. For a fuller discussion of these issues see Crook et al. (2012).
These problems can be reduced or avoided by using a general purpose connectivity-generating software library such as the connection-set algebra (CSA; Djurfeldt, 2012) or the NineML graph library (Raikov and De Schutter, 2010). Such libraries allow simulator-independent specification of connectivity and enable high-level, declarative descriptions which do not constrain how the connectivity should be realized in code and hence give scope for optimization and parallelization within the simulator software. The CSA in addition supports succinct, unambiguous descriptions of connectivity in text, using a mathematical notation.
The adoption of new, simulator-independent methods for expressing connectivity, such as CSA, is hindered by the effort needed to add support for a given connectivity-generating library to a simulator. This effort must, in general, be repeated for each simulator that aims to support the library. The exception to this is if using a simulator-independent modeling interface such as PyNN (http://www.neuralensemble.org/PyNN; Davison et al., 2009), which supports multiple simulators, and could also support multiple connectivity-generating libraries without the need to support it in each simulator. PyNN, however, is written in Python, which means that processing the CSA description will be slower than if using C/C++ (the languages in which many simulators are written). Furthermore, whether using a simulator-independent interface or not, a new programming effort is needed if another new method for expressing connectivity is developed.
To minimize the effort required of simulator software developers, and allow modelers to flexibly choose among simulators and libraries which generate connectivity, we have developed a generic connection generator interface, which enables the use of CSA and similar libraries in different neuronal simulators. The interface makes both the simulator and the connectivity-generating library replaceable and therefore gives maximum flexibility to the modeler.
In this article we first describe the connection generator interface. As an example of a connectivity-generating library, we then give a brief overview of CSA and of different software libraries that support it using CSA in Python and C++ code. We show how the connection generator interface has been integrated in the NEST simulator (http://www.nest-simulator.org; Gewaltig and Diesmann, 2007), enabling the use of connection libraries such as CSA, before describing its use from higher software layers, such as the PyNN framework. Finally, we provide benchmarks for different use case scenarios of the interface.

THE CONNECTION GENERATOR INTERFACE
To allow users to flexibly choose among simulators and libraries which generate connectivity, we have developed an interface that abstracts the simulator and the connectivity-generating library from each other, making both the simulator and the connectivity description library replaceable.
A connectivity-generating library, such as csa or libcsa of section 3.3, is used to create an object, a connection generator, representing network connectivity. In the case of a CSA library, this object is a connection-set, but it could also be a graph constructed from graph primitives. The connection generator interface provides a C++ level interface to such objects which allows software external to the connectivity-generating library to efficiently iterate through connections represented by the object. In the example shown in Figure 1, the connection generator interface is used to combine a Python-scripted simulator with a Python-scripted connectivity-generating library. A connectivity generating object is assembled at the Python level. If libcsa is used, the resulting object will be a C++ object with a Python wrapper (see lower two boxes to the right in the figure). The object is used by a C++ simulator kernel (lower box to the left) to specify network connectivity. By providing connectivity-generating software that implements the connection generator interface as dynamically linked libraries, multiple such libraries can be loaded into the Python runtime environment and used simultaneously without a need to recompile the simulator.

THE INTERFACE
In neuronal network simulations we often want to specify a "projection" between a source population of neurons and a target population. A projection consists of many individual connections between the populations. In nature, one such connection corresponds to an axon forming a synaptic contact on the spine/dendrite of a receiving neuron. A ConnectionGenerator object is modeled on the concept of a projection. The neurons in the source and target populations are enumerated using consecutive, non-negative integer indices starting from 0. These indices are used to specify source and target neuron identity for a connection and constitute an abstraction barrier between the actual elements of a population and the connection generator. This allows the elements to be either neurons (appropriate for networks of point neurons) or individual synapses (appropriate for networks with morphologically-detailed neurons).
The principle of operation of the connection generator interface is an iteration over connections represented by the object. A simulator, or other software using a connection generator, repeatedly calls a function next() until Boolean false is returned. Connections are represented by source and target index, together with zero or more connection parameters. The number of parameters is called the arity of the ConnectionGenerator.
Connection generators can be flexible with regard to the sizes of the source and target populations. The source and target index sets that should be iterated over for the populations at hand are each specified through the interface as a mask. In the case of a parallel simulator, a specific mask is given per MPI rank. Typically, the source index set is the same in all such masks while the target index sets are unique for each rank and nonoverlapping. Each rank should provide all masks (i.e., the set of masks for all ranks). Some connection generators can use such information to avoid the need for communication with other ranks.
The interface is designed as an abstract base class in C++ and consists of the following virtual functions: void start(): Start an iteration. This function must be called before the first call to next().
bool next(int& source, int& target, double * value): Advance to the next connection or return false, if no more connections are available from the ConnectionGenerator. Source and target indices of the connection as well as associated parameters are written into source, target and the array pointed to by value, respectively. The order of iteration is according to increasing index, with all sources iterated over per target.

LIBNEUROSIM
If the C++ header file for the connection generator interface definition and its supporting code were placed in the simulator or connectivity-generating library source trees, it would be duplicated over simulators or libraries. As new versions of the interface are developed, the situation would quickly become unmanageable. The connection generator interface has the desirable property that it is a symmetric abstraction barrier: it both allows a given simulator to use any library supporting the API and allows the same library to be used from any simulator supporting the API.
To create a space in which to put interfaces and other code of generic use for neuronal network simulation software, we have developed the neurosim library (http://software.incf. org/software/libneurosim). More precisely, libneurosim is a software package which currently consists of two main component libraries: libneurosim, providing C++ level support code and libpyneurosim, providing Python support code.
libneurosim provides the ConnectionGenerator interface (Figure 1, bottom). It also contains a registry for XML parser functions. Different types of connection generators can be described by different XML-based languages. For example, the csa library can serialize connection-set expressions using a MathML-based language. A connectivity-generating library may provide a parser for one or more such languages. Conversely, the same XML-based language might be used by one or more connectivity-generating libraries. The XML parser registry maps XML tags identifying specific languages to specific connection libraries. The interface to the registry consists of three static methods in the connection generator interface: void selectCGImplementation (std::string tag, std::string library): Associate the parent node tag tag with the library library. The library named library will be dynamically loaded and will invoke the libneurosim function registerConnection GeneratorLibrary to register its XML parser.
ConnectionGenerator * fromXML (std::string xml): Parse the XML representation xml of a connection generator and return it. The function dispatches to parsers of different libraries depending on previous calls to selectCGImplementation.
ConnectionGenerator * fromXMLFile (std:: string fname): Same as previous function, but read the XML stream from the file with pathname fname.
libpyneurosim currently contains generic support for registering new Python connection generator types and unwrapping instances of such objects: void registerConnectionGeneratorType (Check FuncT, UnpackFuncT): Register a new type checking and unwrapping function.
isConnectionGenerator (PyObject * pObj): Check if pObj is a known connection generator type (as identified by previously registered checking functions).

THE CONNECTION-SET ALGEBRA
The connection-set algebra 1 (CSA) is a declarative formalism for the specification of network connectivity which can be used both when describing a network to a fellow researcher and when implementing a model for a simulator. CSA expressions define connection-sets. A connection-set is the set of edges in a network graph, together with parameters associated with those edges. The abstract nature of CSA creates a clean separation between CSA and other aspects of model or simulator infrastructure. CSA expressions consist of pre-defined elementary connection-sets and operators such that new connection-sets can be defined in terms of existing ones. It enables a succinct and precise description and definition of connectivity in terms of such expressions. By allowing connection-sets to be infinite, they can represent connectivity patterns of arbitrary size in addition to connectivity of specific networks. There are ways to implement CSA on a computer which are both efficient and scalable on a parallel computer. The parallelization is transparent to the user since intersection operators in the algebra can efficiently subdivide a connection-set among processes. CSA is currently focused on the description of synthetic connectivity as opposed to connectivity obtained through data acquisition, but it can also be used when all network connections are given explicitly or in cases where only some elements of the connectivity are explicitly specified.

CONNECTION-SETS
To give a flavor of CSA, we will now further introduce some of its concepts. Given source and target neuron (or other object) populations P s and P t of fixed, finite size, a CSA connectionset is defined as the set of connections between P s and P t along with zero or more per-connection parameters such as weight or delay. As for connection generators, elements of populations are enumerated using non-negative integers. Thus, a population P is enumerated and represented by an index set I. One connection from P s to P t is represented by the pair (i, j), where i ∈ I s , j ∈ I t . Such indices are similar to the GIDs (Global IDentifiers) of the NEURON and NEST simulators but normally start at 0 and run consecutively for each population. Introducing this abstraction, in the form of a mapping from objects in the simulation domain to integers, gives at least two major advantages: 1. The CSA need not be aware of the nature of the objects in P-they could just as well be synaptic boutons as neurons. 2. The index set I can be chosen to be infinite. This is useful when generically specifying a connectivity pattern independent of the sizes of the specific source and target populations for which it will later be used. This is further discussed in section 3.2.
A connection-set with zero parameters is called a mask. A mask states which connections exist. In the example of the mask 2 M = {(0, 1), (1, 1), (1, 2), (3, 2), (2, 3), (0, 4)} it can be regarded either as a connection matrix (see Figure 2A) or as a Boolean indicator function: If the mask is combined with a source 2 In CSA notation, masks are marked with a bar. Network connectivity when the mask in (A) is applied to source population P s and target population P t . (C) The one-to-one maskδ. The mask is infinite, but finite portions can be cut out when applied to finite source and target populations. This is illustrated by the solid square for source and target size 7. When source and target population is the same,δ represents self-connections. population P s and a target population P t , the result is the network (P s , P t , M) shown in Figure 2B.
In CSA, connections can be parameterized through functions mapping connections to values: where V is some codomain, e.g., real numbers. In Djurfeldt (2012), such a function is called a value set. An example of a value set is distance dependent delays with added noise drawn from a clipped random normal distribution. A value set is typically used to assign a weight or delay to connections.
A CSA connection-set, C, is a tuple of a mask and zero or more value sets: The number of value sets of a connection-set, i.e., the number of values associated with each connection, is called its arity. A connection-set with arity 0, (M), is for all purposes equivalent to a mask, M, and the two can be used interchangeably.

AN ALGEBRA FOR CONNECTIVITY STRUCTURE
In CSA, the concepts defined in the previous section have been developed into a formalism for describing connectivity structure. Assume that a mask specifies connectivity for a single population such that P s = P t = P and that we are interested in describing self-connections, i.e., every neuron in P should be connected to itself. If the size of P is 4, the mask {(0, 0), (1, 1), (2, 2), (3, 3)} could be used. If the size is 2, the mask {(0, 0), (1, 1)} would be appropriate. Such masks contain not only information about connectivity structure but also about population size. We can generalize by stripping off the population size information and allowing the index set I and mask to be infinite, defining the one-to-one maskδ: Nowδ only encapsulates the concept of self-or one-to-one connectivity structure (depending on whether the source and target populations are the same or different) without reference to size, i.e., we can describe a connectivity pattern independently of any specific network. Finite portions can be cut out of such infinite connection-sets when applied to finite populations (see Figure 2C). CSA provides a set of elementary connection-sets such as δ. Another example is the random maskρ(p), a parameterized connection-set which captures the concept of Erdős-Rényi connectivity.ρ(p) can be regarded an infinite matrix of independent, Bernouilli distributed, random variables with parameter p, such that their realizations form an infinite mask. Thus, forR =ρ(p) (where the interpretation is thatR is the mask formed from realizations) By using CSA operators such as intersection (∩), union (∪), and set difference (−), connection-sets can be combined into expressions. For example, the idea of "random Erdős-Rényi connectivity without self-connections" can be represented by the CSA expressionρ(p) −δ (see Figure 2D). A mask representing all possible connections between two finite populations can be formed by taking the Cartesian product of their index sets, I s × I t . Intersecting with this mask can turn an infinite connection-set, representing connectivity structure, into a connection matrix between the populations. For example, the finite part of the matrix in Figure 2C is {0, . . . , 6} × {0, . . . , 6} ∩δ. For a more in-depth description of the CSA and principles of implementation see Djurfeldt (2012).

IMPLEMENTATIONS
There currently exist three implementations of CSA. They internally represent connection-sets as iterators and CSA expressions as trees of such iterators. The original implementation is written in C++ and is part of the SPLIT simulation library (Djurfeldt et al., 2005). It was used to specify the connectivity of the KTH cortex model (Djurfeldt et al., 2008)-a model with three hierarchical levels of structure. The second implementation is written in Python and is available as the Python library csa. Here, the aims were 1. to get an easily usable and extensible demonstration of CSA and 2. to experiment with new ways to implement CSA. This implementation has been released as free software under the GPL and is available at the INCF software center (http://software.incf. org/software/csa). A third implementation in C++, libcsa, is currently under development and will also be released under the GPL. It provides Python bindings such that CSA objects can be formed by Python level expressions with similar syntax as used with the csa library. For further information about this syntax, the reader is referred to the tutorial in the csa package. The benchmarks in this article (section 6) were performed using the latter two implementations in Python and C++, csa and libcsa.

USING CONNECTION GENERATORS IN NEST
NEST is a simulator for large networks of point neurons or neuron models with few electrical compartments (http://www. nest-simulator.org; Gewaltig and Diesmann, 2007). It is suited for a broad range of neuronal network modeling approaches and runs on a large variety of computer architectures. NEST is parallelized using OpenMP (OpenMP Architecture Review Board, 2008) and MPI (Message Passing Interface Forum, 1994) and scales well on ordinary desktop computers to large clusters of multi-core processors and supercomputers (Helias et al., 2012). The network description is a script, written either in SLI, NEST's built-in simulation language, or in Python, using the Python interface to NEST (PyNEST; Eppler et al., 2009). To build a network in NEST, the user first creates the neurons of the network and devices for stimulation and measurement using the Create function and then connects the elements with each other.

NATIVE CONNECTION FUNCTIONS
The most basic way to set up connections is using the Connect function, which takes a list of pre-synaptic neurons (or devices) and a list of the same amount of post-synaptic neurons (or devices) and connects the corresponding elements in a one-toone fashion. Because of the function call overhead, this function is not very efficient to use when creating large networks.
To avoid such overhead, the functions Convergent Connect and DivergentConnect can be used to create multiple connections with a single call. In addition, randomized variants for both of these functions exist to support the user in creating networks on the basis of knowledge of connectivity statistics. However, random connection parameters (e.g., weight, delay, or time constants) need to be specified by user code and supplied to NEST after the creation of connections.

TOPOLOGY MODULE
To ease the creation of complex networks with spatial structure, NEST provides the Topology Module (Plesser and Enger, 2013). It supports the user in connecting neurons and initializing synapse parameters based on their topological relationships in the network. In contrast to the CSA, the topology module is very much tailored to building structured networks consisting of layers in NEST with minimal overhead. The CSA has a wider focus in that it is simulator-independent and supports arbitrary connectivity patterns that can also include repetitive elements. We are currently investigating if future versions of the Topology Module can be based on the CSA.

SUPPORTING CONNECTIVITY-GENERATING LIBRARIES
As detailed above, NEST provides multiple methods for connecting neurons into a network. However, while the native routines scale very well (Helias et al., 2012), they are only suitable for creating simple patterns such as convergent/divergent connectivity without looping over them in user code. On the other hand, the topology module (Plesser and Enger, 2013) allows the creation of more complex structures, but requires neurons to be organized in special data structures (e.g., layers).
To support the connection generator interface in NEST and thus make more connectivity-generating libraries available to users, we created the ConnectionGeneratorModule. It is implemented as a plugin for NEST which extends both user interfaces, SLI and PyNEST, and builds on libneurosim (see section 2.2).
All neurons and devices in NEST are identified uniquely by an integer number, their global id (GID). As all existing connection routines in NEST work either on single GIDs or on lists of GIDs, we decided to also use this convention when a user specifies cells for a connection generator. These GIDs are internally mapped to contiguous ranges of integer indices starting at zero, for use by the connection generator. Our new interface for using connection generators in NEST consists of the following functions: CGConnect takes a ConnectionGenerator cg, lists of GIDs for pre-and post-synaptic populations, and a param_map. It creates the connections between neurons in pre and post as prescribed by the rules in cg. The parameter map param_map maps parameter names (e.g., weight, delay) to their index for the parameter value vector created by the call to next() in the connection generator interface (see section 2.1). In the current implementation, only arities 0 and 2 are supported.
CGParse takes a serialized version of a connection generator in the string xml and returns the corresponding ConnectionGenerator object. A special use of this function exists on supercomputers, where Python is often not available on the compute nodes, or where the memory and performance penalty would not be acceptable and a pure SLI-based solution is preferable.
CGParseFile takes a file name fname and parses the serialized version of a connection generator contained therein.
CGSelectImplementation takes an XML tag tag representing the parent node of a serialized connection generator and the name of a library library to provide a parser for such an XML file. This information determines which library should carry out the parsing for CGParse and CGParseFile.
In order to use the new interface in NEST, the user first has to construct a ConnectionGenerator object. This can be done at the Python level by either using csa or the Python bindings of libcsa (see section 3.3). When PyNEST is used, this object can be directly given to CGConnect, which wraps the ConnectionGenerator object into a SLI Datum of type connectiongeneratortype that can be handed over to NEST's simulation kernel. It is then iterated at the C++ level in case of libcsa, or by calling back into Python in case of csa.
Another way to construct a ConnectionGenerator object is by parsing an XML serialization of the object. Such a serialization could be created at the Python level, created by an external tool, or written by hand. At the SLI level this serialization can then be given to one of the SLI functions CGParse or CGParseFile, which reinstantiate the original object using the functions fromXML or fromXMLFile in the connection generator API. This object (of type connectiongeneratortype) can be given to SLI's version of the CGConnect function. Note that the step of creating the serialization of the ConnectionGenerator can also be carried out on another machine. In this way, simulations using CSA can be run on machines where Python is not available. Figure 3 shows the different entities in NEST involved in a user call to CGConnect in PyNEST. After setting the masks for the connection generator to tell it which neurons are local and which are remote (see section 2.1), the NEST kernel iteratively calls next(). This function returns source and target indices, and values for weight and delay if the arity of the connection generator is 2, until there are no more connections. The connections are internally established one by one calling NEST's basic Network::connect() function at the C++ level.

USING CONNECTION GENERATORS IN PyNN
PyNN (http://www.neuralensemble.org/PyNN; Davison et al., 2009) is a simulator-independent API for describing neuronal networks in Python. Given a PyNN/Python model description, the user can choose which simulator to use without needing to change the model script. This is achieved through a set of simulator backends. Each backend is a Python module that implements the API for a specific simulator, for example by providing a mapping from standard model names and units in PyNN to simulator-specific ones. In PyNN, a neuronal network is built from Populations of neurons and Projections between them. Each Projection is created by a Connector, which knows how to set up the individual connections. Different Connectors exist and allow to set up a variety of different deterministic and probabilistic connection patterns.
To enable them to be simulator-independent, each Connector is implemented in terms of lower-level commands, typically one-to-one or convergent connect functions, available in all simulators. However, because these commands are low-level this approach entails a certain performance penalty due to transfer of source/target lists and connection parameters and function call overhead.
To overcome the problem of excessive data transfers between PyNN and the simulator, a backend can supply customized Connector implementations that are more efficient than using the default, simulator-independent implementations. Such custom implementations can be iterated and expanded at the simulator level and thus avoid overhead. Moreover, they allow efficient parallelization at the lower software layers. Prior to the creation of the connection generator interface, however, the limitation of this was that a separate custom implementation had to be written for each PyNN Connector.
Since version 0.7, PyNN has provided the generic CSAConnector, which can iterate a CSA connection-set and issue one by one connect calls to the different simulators through their backends. Internally, the Connector executes the following two steps: 1. Form a finite connection-set adapted to the actual sizes of the populations by intersecting the given connection set with the Cartesian product of the neuron indices of the pre-and postsynaptic populations. 2. Connect the neurons. The weight, delay and any other synaptic parameters are taken from the connection set, if supplied as value sets (see section 3), or from the parameterization of the synapse type otherwise.
During this study, we extended the NEST backend for PyNN with a new and specialized CSAConnector which passes the complete ConnectionGenerator object down to the simulator (by calling PyNEST's CGConnect function). The iteration over the connections can then take place at the C++ level in NEST using the connection generator interface (see section 4). This greatly reduces the overhead and thus improves the runtime and scalability of connection generation (see section 6).

BENCHMARKS
We ran a series of benchmarks in order to assess the performance of and compare two implementations of CSA (see section 3.3) and the two implementations of the CSAConnector for PyNN (see section 5). Grouped by the software layer in which the iteration of the connection generator happens (either in Python by PyNN or in C++ by NEST, see section 4) and the CSA implementation used (csa is the Python version, libcsa the C++ version), the following scenarios were measured: • Python, csa used PyNN's original CSAConnector that is available for all backends in combination with the Python CSA implementation. The CSAConnector intersects the csa object with a mask representing the actual source and target nodes available and iterates the csa object entirely at the Python level. It connects the neurons by issuing ConvergentConnect() calls to PyNEST. • C++, csa used the new CSAConnector for PyNN's NEST backend, which is available in the development version of PyNN, and the Python CSA implementation. The csa object is passed down to NEST through CGConnect().
The ConnectionGeneratorModule then iterates it at the C++ level by repeatedly calling its Python level iterator through the C++ connection generator interface. • Python, libcsa used the generic CSAConnector in PyNN and the C++ CSA implementation libcsa. The CSAConnector iterates the libcsa object at the Python level, repeatedly calling its wrapped C++ iterator. • C++, libcsa used the new CSAConnector for PyNN's NEST backend and the C++ CSA implementation libcsa.
The libcsa object is passed down to NEST through CGConnect(). All iterations happen in C++ in the ConnectionGeneratorModule through the connection generator interface.
The population size benchmarks (Figures 4A,B) used one MPI process and varied the number of neurons from 10 2 to 10 5 with about one sample per order of magnitude. All tested implementations of CSA (csa, libcsa) scale excellently with slopes around 2 for the random mask, independent of the software layer (C++ or Python) at which the iteration was carried out. However, in Figure 4, the vertical offsets and the increasing slopes of the curves for the generic CSAConnector which iterates at the Python/PyNN level suggest that the current implementation of this connector together with calls through different software layers to setup individual connections adds a significant overhead to the process of connection generation.
To demonstrate the scalability of the implementations, we carried out both strong and weak scaling benchmarks, using CSA's random maskρ(p) with a probability p = 0.1 (Figures 4C,D). For each of these, the number of MPI processes was varied from 1 to 48.
In the strong scaling benchmark (Figure 4C), the number of MPI processes was varied while keeping the total number of neurons in the network fixed at 48,000. This resulted in approx. 230 million connections being created. It is easily visible that iteration of the CSA object at the Python level in the current PyNN implementation of the original CSAConnector is detrimental to the scalability. In contrast, it is possible to obtain near perfect scaling if the iteration of the CSA object is carried out from the C++ layer. Using the C++ implementation of CSA, it is, however, possible to gain another order of magnitude compared to the Python version.
During the weak scaling benchmark (Figure 4C), the number of MPI processes was varied while the work load was increased by a fixed number of connections per additional process. The number of connections grows quadratically with the number of neurons when using CSA's random mask with a fixed probality. The number of neurons per process was thus increased with the square root of the desired number of connections.
In the realm of natural numbers, this leads to a slight error, which was, however, acceptable, with values between −1.42 and +1.08 .

COMPARISON TO NATIVE INTERFACES
To compare the performance of the connection generator interface to more traditional ways of setting up connectivity, we also performed performance and scaling benchmarks of the native interfaces for random connectivity in PyNN and NEST. Figure 5 contrasts CSA's random mask with a probability of 0.1 with PyNN's FixedProbabilityConnector (FPC) and NEST's function RandomConvergentConnect (RCC).
Note that NEST does not provide a Bernoulli trial based connection scheme such as used by FPC in PyNN and the random mask in CSA (see section 3.2) and RCC was chosen because it is the function that most closely resembles such a method. The use of RCC results, however, in a bias toward the other methods over NEST, as it requires iterative calls to RCC from the Python level, which entail a certain overhead in SLI, PyNEST and the C++ implementation of RCC itself (data not shown).
The population size benchmark ( Figure 5A) again used one MPI process and varied the number of neurons from 10 2 to 10 5 with about one sample per order of magnitude. It shows that all tested variants for setting up the connectivity scale equally well with slopes slightly below 2. The offset between NEST's RCC (written in C++, but called repeatedly from Python) to the CSA object iterated in C++ can be attributed to overhead in the additional software layers.
As in Figure 4C, the comparative strong scaling benchmark shown in Figure 5B varied the number of MPI processes while keeping the total number of neurons in the network fixed at 48,000, resulting in a total of approx. 230 million connections being created. The results are consistent with the data from Figure 4C in that scalability is destroyed if additional interpreted software layers are involved and that an iteration in C++ is favorable. The effect is even stronger for RCC, because its use to create a number of connections corresponding to that yielded by a Bernoulli trial scheme entails even more iterations through the additional software layers.

BENCHMARK ENVIRONMENT
The machine used for benchmarking was equipped with 4 12-core AMD Operon 6174 (Magny Cours) processors, organized into 8 NUMA domains with 6 cores each. Other than the choice of the number of MPI processes in a NUMA-friendly way, no measures (like pinning of processes to cores, altering the affinity of threads to cores, etc.) were taken to avoid distortions of the results. Users are, however, free to benefit from such techniques to improve the performance of their simulations.

SOFTWARE VERSIONS AND BENCHMARK SCRIPTS
All benchmarks were using csa revision 119 from http://svn.incf. org/svn/csa, libcsa from an internal git repository (git@wand. pdc.kth.se:libcsa.git, version 3ef2db519a), the development version of PyNN from https://github.com/NeuralEnsemble/PyNN/ (version db76c748cd) and NEST revision r10722 from the internal Subversion repository. The L A T E X sources of this article, the benchmark scripts and all data we obtained are available from https://github.com/mdjurfeldt/pns2csa.

DISCUSSION AND OUTLOOK
We have developed and demonstrated a novel way to connect a simulator and external connectivity-generating software through the connection generator interface. It supports dynamic loading of connection generators without the need for recompilation of either simulator or generators. Benchmarks show good scaling when using connection-set algebra libraries from NEST and PyNN through the connection generator interface. The availability of this and associated interfaces lets users flexibly choose a connectivity-generating library independently of the simulator used, and thereby grants greater freedom for describing models.
The first version of the interface presented here was intentionally made simple, as a proof of concept, and there are several possible directions of development for its functionality. Currently, parameters are passed as doubles. This could be generalized to other data types. For parallel simulators, connection generators may need access to the MPI communicator in which case it needs to be passed through the connection generator interface. Instead of using a fixed iteration order, the order could be specified by the simulator. Iteration order could also be unspecified, giving opportunities for optimizing iteration on the part of the connectivity-generating library. In order to maintain backward compatibility as new revisions of the interface are developed, interface versioning could be introduced.
One temporary limitation in the current implementations of the NEST ConnectionGeneratorModule and the PyNN CSAConnector is that value sets for the connection generator can only be used if their arity is 0 (no parameters) or 2 (weight and delay). We are currently working on the infrastructure in NEST to support arbitrary arities, as it would be beneficial for many synapse models, to also set time constants, concentrations and other parameters based on rules in the connection generator.
At the moment, libneurosim only contains the connection generator interface and some auxiliary code. For the future, we are planning to turn this into a community based effort to share common interfaces and make it a generally useful library also for the developers of other simulators than PyNN and NEST.
The differences in run time and scalability between an iteration of the connection description in Python on the one hand and the CSA object iterated at the C++ level on the other suggests that a compact description of connectivity iterated solely at the level of the simulator indeed has a huge impact. NEST and other simulators can thus greatly benefit from the availability of compact descriptions such as enabled by the connection generator interface.


text:
Dynamic Cooperative Clustering Based Power Assignment: Network Capacity and Lifetime Efficient Topology Control in Cooperative Ad Hoc Networks

Cooperative communication (CC) is used in topology control as it can reduce the transmission power and expand the transmission range. However, all previous research on topology control under the CC model focused on maintaining network connectivity and minimizing the total energy consumption, which would lead to low network capacity, transmission interruption, or even network paralysis. Meanwhile, without considering the balance of energy consumption in the network, it would reduce the network lifetime and greatly affect the network performance. This paper tries to solve the above problems existing in the research on topology control under the CC model by proposing a power assignment (DCCPA) algorithm based on dynamic cooperative clustering in cooperative ad hoc networks. The new algorithm clusters the network to maximize network capacity and makes the clusters communicate with each other by CC. To reduce the number of redundant links between clusters, we design a static clustering method by using Kruskal algorithm. To maximize the network lifetime, we also propose a cluster head rotating method which can reach a good tradeoff between residual energy and distance for the cluster head reselection. Experimental results show that DCCPA can improve 80% network capacity with Cooperative Bridges algorithm; meanwhile, it can improve 20% network lifetime.

Introduction
Wireless ad hoc networks consist of wireless nodes that can communicate with one another in the absence of a fixed infrastructure. There are three important issues in wireless ad hoc networks. The first is network connectivity. The network is connected if any two nodes can communicate with each other in a network. It is much more difficult to ensure that two nodes connect in a wireless network than in a wired network because of the instable wireless channel, signal attenuation, and so on. Network connectivity is closely related to the node transmission power. The greater the node transmission power, the better the network connectivity [1]. The second is energy consumption. Wireless nodes have a limited operational time as they are battery powered [2]. It is nearly impossible for the battery at nodes to be recharged or replaced; thus, energy efficiency is crucial in wireless ad hoc networks. The key difference between wireless ad hoc networks and conventional communication structures, from the designer's point of view, lies in the power assignment model [3]. The energy consumption of a single node is proportional to the transmission power it assigned. The greater transmission radius of a node means that it requires higher transmission power. We evaluate the energy efficiency by two parameters: total energy consumption and network lifetime. The third is network capacity which is simply defined as the amount of data transmitted in a certain period of time. Future mobile wireless communication networks must be able to bear high-speed, highly efficient business processes if it is to support multimedia business featured by realtime and a large amount of data. Two main factors affect the network capacity: the transmission power and the radio interference caused by simultaneous transmission. According to typical Shannon theorem, the greater the transmission power, the greater the network capacity [4]. That is, there is a compromised relationship between reducing energy consumption and increasing network capacity.
Topology control is one of the most important techniques used in wireless ad hoc networks to reduce energy consumption or increase network capacity on the premise of maintaining connectivity by adjusting the transmission power [1]. However, the actual wireless network is difficult to be fully connected initially, making the topology control to operate poorly, so some researchers introduce cooperative communication to apply in topology control to solve this problem [5].
Cooperative communication is a new wireless communication technology which allows single-antenna terminal devices to share their physical resources to communicate in a multiuser environment. It forms a virtual antenna array by utilizing the broadcast feature of a signal [6,7], which achieves resource sharing and expands the coverage of network through mutual cooperation [8]. It is called cooperative ad hoc networks after using cooperative communication in wireless ad hoc networks. Energy consumption and network capacity issues are still very important in cooperative ad hoc networks. The previous works [2,5,9] mainly study the topology control problem in cooperative ad hoc networks to minimize the energy consumption and guarantee the network connectivity by constructing a sparse graph. They ignore the network capacity efficiency because they do not consider reducing the interference in a sparse graph, which will affect the network capacity destructively and eventually reduce the network capacity [10]. Figure 1 shows an example. At first the initial network is disconnected, as Figure 1(a) shows. Then CC in [5] is applied to make network connected; V 3 V 10 is a CC link and the final resulting topology structure is similar to the MST, which is a sparse graph and can reduce interference to a certain extent, but neighbors will still interfere with each other when nodes transmit simultaneously. As Figure 1(b) shows, when node V 6 transmits a message to node V 7 , nodes V 8 and V 9 will cause interference to V 7 ; when node V 7 transmits a message to V 6 , node V 5 will cause interference to V 6 . So, the previous works of topology control problem in cooperative ad hoc networks may not work efficiently in terms of network capacity.
Apart from ignoring the network capacity efficiency, previous research on topology control under the CC model failed to equalize the energy consumption among network nodes. Assume that the maximal transmission power of each node is max , 1 = (75% max , max ]; 2 = (50% max , 75% max ]; 3 = (25% max , 50% max ]; 4 = [0% max , 25% max ]. Figure 2 shows the average node energy consumption distribution of 100 topologies (suppose there are 100 nodes) built by Cooperative Bridges algorithm [5]. In the interval 1 there are only 11% nodes, which transmit messages in a relatively high transmission power. However, according to this algorithm, 11% 24% 38% 27% P 1 P 2 P 3 P 4 the network topology structure is static and immutable during the whole network lifetime. These will lead to the fact that nodes in the 1 transmit messages at a higher transmission power, thus suffering faster energy consumption, while nodes in other intervals transmit messages at a lower transmission power, and the energy consumption rate is slower accordingly. This means that when those few nodes which consume much energy die earlier, most of the nodes which consume little energy still have much residual energy. This situation is visually shown in Figure 3. Assume the primary energy of each node is , 1 = (75% , ]; 2 = (50% , 75% ]; 3 = (25% , 50% ]; 4 = [0% , 25% ]. Figure 3 shows the distribution of the remaining energy of nodes when the topology structure constructed by random network in Figure 2 comes to a final death. We can see from Figure 3 that, when the first node dies, the majority nodes of 80% stay in the high residual energy level L1. So, the uneven node energy consumption has a serious impact on network lifetime.
The Scientific World Journal 3 Therefore, the paper attempts to study the problem of how to maximize network capacity and energy efficiency in cooperative ad hoc networks. We design a topology control algorithm, called DCCPA, based on a dynamic cooperative cluster algorithm and power assignment to maximize its network capacity and network lifetime.
The paper is organized as follows. We summarize some related work in Section 2. Then we present the network model, introduce some definitions and statements which we use throughout the paper, and give a problem definition in Section 3. Section 4 studies our topology algorithm. Afterwards we present some simulation results in Section 5. Finally, we draw some conclusion in Section 6.

Related Work
In this section, we focus on related works about topology control problems in cooperative ad hoc networks.
The main goal of designing cooperative ad hoc networks is to increase network capacity, reduce energy consumption, and enhance network coverage. What deserves our attention is that there is a tradeoff between the three. The way of choosing relay nodes is decided by the needs of different systems which choose different optimized objects for optimization. It is a hot issue to determine the number of relay nodes in a relay node selection algorithm.
As topology control is a network layer issue, researchers usually consider simple physical characteristics instead of variations of channel state when CC is applied in topology control. In [11], Guan et al. abstracted the topology control problem in cooperative ad hoc networks for a discrete stochastic optimization problem and they viewed network capacity as the goal of optimization. However, the authors consider that the time-varying channels have important impact on the network capacity. In [2], Cardei et al. first studied the topology control problem under cooperative model (denoted by TCC) which aims to obtain a strongly connected topology with minimum total energy consumption. In [9], Zhu et al. proposed two topology control algorithms to build cooperative energy spanners in which the energy efficiency of individual paths is guaranteed. In [5], Yu et al. applied CC model in topology control to improve the network connectivity as well as reducing transmission power. Their algorithm first constructs all candidates of bidirectional links by using CC model which can connect different disconnected components. Then they apply a 2layer MST structure (one MST over the CC links and the other is inside each component) to further reduce the energy consumption. This is the best work in minimizing the total energy consumption while increasing the network connectivity. However, the proposed algorithm decreases the performance of network capacity greatly, which is validated by the experimental results. Therefore, the problem that the sparseness of the constructed topology under CC model should make network capacity and energy efficient at the same time is critical.
Such problem has been studied in traditional topology control algorithm (without CC) [3]. In [3], Shpungin and Li developed a static cluster based power assignment algorithm which achieves energy efficiency and also maximizes network capacity in the case of unlimited maximum transmission power of each node. Cluster algorithm is a kind of smart scheduling algorithms to improve the network capacity by lowering the interference of concurrent transmissions in a sparse network [12,13]. In cluster algorithm, nodes are assigned transmission time slots so that only a subset of nodes are active at any given time slot while the others are idle. This scheme requires a synchronization mechanism, such as TDMA. In clustering algorithm, the energy consumption of cluster head is generally much higher than the cluster member nodes. Static clustering algorithm can easily lead to an early death of the cluster head node due to energy depletion. To avoid this situation, the cluster head rotation mechanism [14][15][16] is adopted so that each node serves as the cluster head in turn, ensuring that the residual energy of each node is equal to one another as close as possible. Cluster head rotation mechanism is usually independent of the clustering algorithm; they are complementary with each other instead. However, so far there is no network capacity and network lifetime efficiency topology control algorithm proposed under CC model yet.

The Definition of Model and Problem
In this section, we describe a cooperative communication model and a network model for our topology control mechanism. In addition, we also introduce a topology control problem for network capacity and energy efficiency in cooperative ad hoc networks.

Cooperative Model.
The simple explanation of the cooperative communication is given by a three-node example as shown in Figure 4. In the graph, node V 1 is the source node, node V 3 is the destination node, and node V 2 is a relay node. The transmission from node V 1 to node V 3 is based on the frame-by-frame scheme. There are two time slots for a frame. In the first slot, node V 1 makes a transmission to node V 3 . Because of the wireless broadcast feature, it is also overheard by relay node V 2 . In the second time slot, node V 2 forwards the data received in the first time slot to node V 3 .
There are two CC models in the paper. As Figure 4 shows, source nodes cannot communicate with target nodes directly 4 The Scientific World Journal while source nodes can communicate with relay nodes and relay nodes can directly communicate with target nodes. In this case, we look on the relay nodes as the help nodes of source nodes. This CC model is similar to [17,18]. The other model which is showed in Figure 5 is that neither source nodes nor its neighbor nodes are able to communicate with destination nodes. The CC model is similar to [2,5]. It takes the advantage of the physical layer design [14] that combines partial signals containing the same information to obtain the complete information.
Assume that each node has a maximum transmission power max . In the direct communication, that is, in the absence of cooperative communication, if a source node V can communicate with a destination node V , they must satisfy where is the transmission power of node V and is the Euclidean distance between V and V , where is a constant representing the distance-power gradient, usually taken to be in the interval [1,2,4]. is the minimum average signal-tonoise ratio (SNR) for decoding received data.
When the first CC model is put to use, the transmission power of source node V and relay node V must meet the conditions below, respectively: When the second CC model is applied, if V transits the same signal with a set of help nodes , their transmission power satisfies

Network Model.
We consider a wireless ad hoc network with nodes which are capable of receiving and combining partial received packets in accordance with the CC model. Every node V can adjust its transmission power which is limited by a maximum value max . The network topology is modeled as a 2-dimensional directed graph: = ( , ), where = (V 1 , . . . , V ) denotes the set of wireless nodes and denotes a set of directed communication links. We assume that each node has a unique ID and knows its own location information. Node ID and location information are exchanged among all nodes.
In this paper, we assume that a source node can choose one or more relay nodes to transmit message. Helper node set, helper link, node connectivity, and network connectivity's definitions are the same as [5]. Besides, we formally give some other definitions.
Definition 1 (link capacity Cap(V , V )). It is the maximum amount of messages that node V transmits to node V in unit time via wireless channel (V , V ), that is, where is the channel bandwidth, SINR (V , V ) is signal to interference plus noise ratio, and 0 is the ambient noise power, which is negligible comparing to the interference caused by other transmitting nodes.
A closer look at expression (4) reveals that the link capacity has a relationship with transmission power and radio interference. We denote (V , V ) = ∑ V ∈ \{V ,V } / ; V ∈ \ {V , V } is the subset of nodes simultaneously transmitting at some time instant over a certain subchannel. Most of the paper is dedicated to analysis of how to reduce (V , V ), that is, radio interference.
Definition 2 (path capacity Cap( )). It is the minimum channel capacity on the path . The capacity of a path in a communication graph is defined as the capacity of the minimum capacity link in , that is, The Scientific World Journal 5 Definition 3 (network capacity Cap( )). It is the minimum path capacity of all paths that V and V pass through, that is, Definition 4 (network lifetime ( )). It is the time which takes the first node to run out of its battery charge.

Problem
Formulation. Now we can define the new topology control problem, network capacity and energy efficient topology control in cooperative ad hoc networks (CEETC). Given a 2-dimensional directed graph , which is strongly connected under CC model, assign transmission power to every node V such that to (1) maximize network capacity Cap ( ) and (2) maximize network lifetime ( ). As TCC problem [2], which only maintains the connectivity and reduces energy consumption, has been proved to be NP-complete, it is a simple case of CEETC in cooperative ad hoc networks when ignoring capacity, so CEETC is also NPcomplete. Therefore, we will propose a heuristic algorithm and give an approximate solution to CEETC problem.

Proposed Algorithm
In this section, we propose a dynamic cooperative clustering based power assignment (DCCPA) algorithm to solve the problem mentioned above. To keep the proposed algorithms simple and efficient, we only consider its one-hop neighbors as possible helper nodes for each node when CC is used [5].
This algorithm is divided into two steps: the first step is static clustering, including the intercluster communication and the transmission power assignment; the second step is cluster head rotating, including the cluster head election, the communication between cluster heads, and the transmission power reallocation. Before describing the algorithm, the pretreatment is conducted.
We denote the wireless multihop network as an undirected simple graph = ( , ), where is the set of nodes; direct communication link and CC link are expressed by the solid and dotted lines, respectively. In graph , first, ( ) ̸ = 0 and ( ) = 0. Then each node works with maximum power max , and from formula (1), the transmission radius of each node is √ max . If a direct path exists between the nodes , V, edge ( , V) is constructed. When the network is not connected, there are at least two groups after the construction of all edges has been completed, as Figure 6 shows. We describe every step in detail now.
Step 1 (static clustering). (1) Clustering in Graph . The clustering process is repeated. When clustering is completed, each node should belong to a cluster, either a cluster head or a cluster member. We use a set ( ) which is initialized to the set of all nodes; that is, ( ) = ( ). If ( ) is not empty, we select a node arbitrarily ∈ ( ) to work as a cluster head. The cluster took shape from and all the nodes which are with a distance of √ max from . The nodes in are defined as the cluster members of . Then we judge each node V ∈ whether it belongs to another cluster. If not, V chooses as its cluster. Otherwise, V chooses to be the cluster member with the nearest cluster head. Then we delete node and its cluster members from ( ) and judge whether it is empty. If it is, clustering is completed. Otherwise, the process continues. The clustering process is shown in Figure 7; a circle represents a cluster.
(2) Communicating between the Cluster Heads. In this step, to make clusters communicate with each other, the way of selecting help nodes is the same as that of Greedy Heuristic in [5]. The process is shown in Figure 8. After CC links are established between clusters, Kruskal algorithm is used to derive its spanning tree (MST), as Figure 9 shows. Through the step, we can know helper nodes set that each cluster head node needs, and we can get ∪ (V) according to formula (3), which is the transmission power of required to construct a CC link to the other cluster head node V with the help of helper nodes in : (3) Doing Power Assignment. For the cluster members, what is needed is the energy which enables them to communicate with the cluster head they belong to; that is, for a cluster member , we assume its cluster head is and the power of is 2 ; that is, Because of the characteristics of helper nodes and cluster heads, it is relatively complex to assign power to them. For helper nodes, also cluster members, they should be able to help when they communicate with cluster heads they belong to. The power of each helper node ℎ is decided by the following equation, where is its cluster head and V is another neighbor cluster head: For the cluster head node, it not only should be able to communicate with each cluster member but also can communicate with its neighboring cluster heads; therefore the energy value assigned to cluster heads should be the maximum among these values. The power of each cluster head is decided by the following equation, where is its cluster member and V is another neighbor cluster head: The final topology structure is shown in Figure 10, and the final topology structure in [5] is shown in Figure 11.
Step 2 (cluster head rotating). (1) Cluster Heads Reselection. In the algorithm, the cluster head is not generated periodically; a passive changing manner is adopted instead. Namely, when the residual energy of a cluster head is less than the threshold value, a new cluster head is reselected dynamically. Assume that V is the other nodes in the current cluster The Scientific World Journal 7 that need to change cluster head node and V is the nexthop nearest cluster head node on the routing. The rule of reselecting a new cluster head is as follows: we always reselect the node of the largest which stands for the tradeoff between residual energy and distance . can be obtained by the following: (2) Intraclusters Communication. The cluster which has selected a new cluster head needs to establish links within the cluster. If the new cluster head can directly communicate with its cluster member nodes, then the cluster head communicates with its cluster member nodes directly. Otherwise, the first CC model should be adopted, and the first cluster head node which was decided by static clustering is chosen as a relay node; they send messages to the node of the cluster members together. As the first cluster head nodes are able to communicate with its cluster member nodes, the new cluster head node will also be able to communicate with the cluster member nodes.
(3) Interclusters Communication. The cluster which has selected a new cluster head needs to establish links with its neighbor cluster. If the new cluster head can directly communicate with its adjacent cluster heads, the direct communication is reached; if cluster head V cannot directly communicate with the neighbor cluster head , but a cluster member node V of V can directly communicate with the cluster head , then V is chosen as the help node of V to communicate with ; if neither the cluster head V nor its cluster member nodes can communicate with the cluster head , then the CC link is built, help nodes are chosen, and the intraclusters communication in the first step should be adopted again.
(4) Transmission Power Reassignment. As for the cluster member node V , the transmission power of member cluster heads is calculated by the following: Here, V is the new cluster head and is the first cluster head.
As for the help node V ℎ , when it communicates with another cluster head node , the transmission power V ℎ is calculated by the following: Here, V is the cluster head node of the cluster it belongs to and is another cluster head node. In addition, help nodes, as cluster member nodes, should be able to directly communicate with its cluster head nodes of the cluster it belongs to. The final transmission power of help node V ℎ is calculated by the following: As for the new cluster head node V, when it communicates with another cluster head node , the transmission power of V is calculated by the following: Here, V is the neighbor node of V. The final transmission power of cluster head node V is calculated by the following:

Simulation Setting.
According to the simulation parameters, we do two groups experiments. The simulation parameters of the first group experiment are network capacity and average transmission power. The experimental environment is the same as [5]. In this simulation, 20-150 nodes are randomly arranged in a 500 m × 500 m area. We assume that = 2, = 10 −4 , and = 20 MHZ. The value of max is 490 mW. The value of initial energy is 49 J and the energy threshold is 30 J. The simulation parameter of the second group experiment is network lifetime. 10 pairs of source and destination nodes are generated randomly. Each source node transmits data packets to the destination at the rate of 2 packets/s. Packet size is 1024 bit. We adopt Floyd algorithm for routing and assume that the MAC protocol is ideal. In order to produce more reliable results, the data are generated by averaging the data from several random topologies.

Experimental
Results. The dynamic topology evolvement by DCCPA is shown in Figure 12. At = 0, as shown in Figure 10, the topology varied with the node residual energy distribution from Figures 12(a) and 12(b), the green dotted lines express the direct communication link between the cluster head, the blue dotted lines express the CC link between the cluster heads under the first CC model, and the red dotted lines express the CC link between the cluster heads under the second CC model.
(1) The Simulation Results of the First Group Experiment. Figure 13 shows that DCCPA's network capacity of last time increases by about 80%. DCCPA algorithm can well reduce radio interference by clustering. From Figure 14, we can see that DCCPA's average transmission power also increases. So the network capacity will be greatly improved according to formula (6).
From Figure 14 we can see that the average energy consumption of the DCCPA algorithm is more than that computed by Cooperative Bridges algorithm. From Figures 10  and 11, we can see that in DCCPA there are more cluster head nodes and assistant nodes. Under normal circumstances, the transmission power of cluster head nodes and assistant nodes will be slightly higher than that of ordinary member cluster nodes which can directly communicate messages in Cooperative Bridges algorithm. Moreover, in the second step of DCCPA, cluster head rotation occurs, which means that more nodes will become cluster head nodes or assistant nodes. Therefore, the average energy consumption of DCCPA will be higher.
(2) The Simulation Results of the Second Group Experiment. The ultimate goal of reducing energy consumption is to extend network lifetime. Figure 15 shows the network lifetime of DCCPA. Compared with Cooperative Bridges, the network lifetime of DCCPA is about 20% longer. According to the definition of network lifetime, it depends on the death time of the first node. The DCCPA detects that, when the residual energy of node is less than the threshold value, rotation will be adopted, in other words, reducing its transmission power while improving the transmission power of other nodes which have more residual energy. The network lifetime is lengthened through equalizing the energy consumption of nodes.

Conclusion
In this paper, we propose a dynamic cooperative clustering based power assignment (DCCPA) algorithm to solve a new topology control problem: network capacity and energy efficient in cooperative wireless ad hoc networks. To the best of our knowledge, this is the first study to investigate our proposed algorithm for solving the problem. We give a detailed description of the algorithm which aims to maximize the network capacity and network lifetime in cooperative wireless ad hoc networks. Simulation results demonstrate the high performance of DCCPA which can improve 80% network capacity and prolong 20% network lifetime compared with the Cooperative Bridges algorithm.