Spatial Social Network (SSN) Hot Spot Detection: Scan Methods for Non-Planar Networks

We first describe two methods based on moving window scan techniques. The goal is to detect places where there are incidences of connected nodes. Like in scan statistics for general hot spot detection within point patterns, sets of neighborhoods are scanned systematically. Here, neighborhood is defined using the common GIS/spatial statistics definitions, specifically: a set of $K$ events (e.g. $K$=15) is a point and its 14 closest neighbors) or a circle with a radius $r$ (e.g. a point and all other points within 1-kilometer buffer from the point) (Kulldorff and Nagarwalla 1995). In raster computing, a neighborhood is also defined as a specific number of cells, but since networks are not typically represented as rasters, we do not consider this definition here (Mu and Holloway 2019).

Both EdgeScan and NDScan resultant statistics are tabulated and visualized at the node level. It is also possible to use the above methods to produce a statistical surface (e.g. a raster grid) of values. Many scan statistics produce such continuous raster grids, as the moving window has been traditionally used on data that represents a continuous spatial field such as elevation or rainfall. Since our input data represent discrete locations of individuals, we use the node level to help avoid uncertainty associated with estimating values in places where no individual existed. Depending on future research questions, it may be prudent to estimate results for locations where no individuals lives, if a research is interested finding, for example, that a restaurant is a proximal meeting place for a local SSN.

Regarding visualization, we view results at the node level, instead of the edge level, in order to prevent a haystack visualization problem– a common challenge for non-planar network visualization in GISystems (Andris et al. 2018).

We test the EdgeScan and NDscan methods on data showing connections between members of U.S. Mafia families in the 1960s (from (DellaPosta 2017)). Mafia families are criminal organizations whose members engage in a variety of illegal (e.g. extortion, illegal gambling, drug trafficking) and sometimes legal (e.g. some members owned bars or restaurants) economic activities or “rackets.” While there are many varieties of organized crime, U.S. Mafia families specifically include groups that descended from similar groups in southern Italy and restricted full membership to ethnic Italians (though non-Italians could still be “associates” of the family and we include such individuals). As described in qualitative and historical accounts of the U.S. Mafia (Abadinsky 1983; Gambetta 1993), a member’s network of connections was perhaps their most important resource for carrying out criminal activities. For this reason, it is important to not just document clusters of co-located nodes but also the connections between them that facilitated collaboration in risky and dangerous criminal activities.

Our study area is the five boroughs of New York City and peripheral nearby nodes (all within New York State). We use only edges between members in this region for this case study, although members have alters outside of the study area. The data includes 298 nodes and 936 edges, a density of 0.0198 and average degree of 6.429. The average distance of an edge is 12.775 km, and the standard deviation is 10.525 (max = 55.3 km). There are four edges with 0 distance, as these individuals live at the same address (a home or apartment building). The local structure of these ties reflect particular geometries that represent a system of personal relationships between the households of individuals (Figure 2). Triads and isolates both emerge, as well as a few examples of ’cliques’. While we do not study the outcomes of the various structures, we seek to leverage GIS methods to capture general properties about their connectedness. It can be assumed that ties affect the stability of a sector of the city, and that this sector also has features that can host the ties.

An example is provided to show the difference in neighborhood definition for connected individuals of the Profaci family in Brooklyn (Figure 3). This concentration of individuals has relatively few local ties, and mixed levels of distant ties (not shown).

The average number of detected non-planar edges per node ranges from 0.67 to 31.17 and naturally grows with the size of the neighborhood (Table 4.1). Because EdgeScan simply detects number of edges, it is more likely to increase with increased area. The smallest values are found for 0.5 km of Manhattan distance, where nearly 75% of nodes have no edges within this radius. The largest values are found for KNN, and are larger with more neighbors. When at least 15 neighbors are considered, no nodes have zero edges in their neighborhood. When ten neighbors are considered, only two nodes have no local edges nearby.

We now examine the change in EdgeScan results across a continuous set of neighborhood definitions. Again, increases in the size of neighborhood, either by number of nearest neighbors, or radius, will have an effect on the outcome of the values. For EdgeScan, the KNN method has the smallest variance between all values as more nearest neighbors are added (Figure 4). Using Euclidean distance, with each increment of the radius after 3 km, there is an exponential increase in the average edge count across all of the nodes. This result is expected as the area of a circle increases exponentially with linear growth of the radius. This plot shows that while K is between 5-12 and either radius is less than 3 km (for both Euclidean and Manhattan distance), the results change little with neighborhood size. Afterwards, the results of EdgeScan vary more drastically, if Euclidean distance is chosen. After about 16 neighbors or 5 km, there is also a divergence in results depending on whether Manhattan distance or KNN is used.

Prior research has asserted that 1 km is a reasonable walking distance for meeting (Yang and Diez-Roux 2012). Given this measurement, and that the average degree for nodes is roughly 6.4, we visualize scan outcomes for neighborhood of 1 km Manhattan distance and ten nearest neighbors (KNN=10). The EdgeScan methods show tight concentrations of edges in the Little Italy section of lower Manhattan, and the Upper East Side (marked with dark blue in Figure 5). The KNN method reveals a more dispersed result, where nodes in Staten Island are counted as having high local edges, because the window joins these nodes to points in Brooklyn. As such, two different interpretations of the locations of high clusters of local relationships are given, but consensus locations do emerge.

The average NDScan results show that regardless of type of distance definition, the local density of networks exceeds the density of the entire network (0.0198) (Table 4.1). Only the Manhattan distance neighborhood of 0.5 km has a similar network density of 0.02. However, for this neighborhood definition, over 80% of the nodes in question have a density value of 0.The most connected networks (up to density of 0.16) occur for KNN, indicating that, regardless of distance, a lack of intervening opportunities between nodes may cause individuals to connect. In other words, ties were often made with the nearest people. This reflection holds true for 10 or 15 neighbors, but when 20 neighbors are reached, the density decreases, as these neighbors are potentially outside of the optimal range of more convenient opportunities. In fact the NDScan density of the network slightly decreases with added K neighbors, especially from about 13 - 19 neighbors (Figure 4). However, the variance in results reveals high heteroskedasticity of NDScan values calculated using a small numbers of neighbors. This variance decreases with more neighbors, until about 17 neighbors, in which the variance plateaus, and neighborhoods with greater than 17 neighbors give similar values between nodes.

Euclidean and Manhattan distance measures for NDScan yield results that also show a plateau effect, likely due to the geography of the study area (specifically, the island of Manhattan). Yet, these results are abrupt in that from radii of 0 - 2 km, the network density increases quickly, as does the variance of this value among the nodes. However, at about 1.75 km, there is little difference in the average neighborhood density with increased area. The neighborhood will have a steady density of 0.075 regardless of size or choice to use Euclidean or Manhattan distance (Figure 5).

Regarding the geographic results, the NDScan method reveals that the Manhattan distance neighborhood consistently yields more clustered results than the KNN results. This observation still holds, as Manhattan neighborhood distance largely depends on a fixed area radius (Figure 5). As such, using Manhattan distance results in more localized clusters than KNN. Using Manhattan distance, the NDScan clusters resemble those of EdgeScan with a few differences. There are a few smaller clusters that are detected (marked in red), while most areas have NDScan results of 0. This shows strong peaks and troughs of the density value. It is valuable because it finds places where people are associated, instead of simply proximal. The NDScan results using ten nearest neighbors results in a more even surface with only two nodes with a density of 0. This method finds a number of nodes with density up to 0.33. These highly connected nodes are located mostly in Brooklyn. A few such nodes are in Manhattan and near the Bronx, and even Staten Island. While there is a longstanding ferry that connects Staten Island with Brooklyn, a better measure of cost distance in the 1960s would be needed to assess whether this grouping is a meaningful geographic cluster. However, it is notable that agents between the two boroughs of New York connected in that location.

There are two nodes with have a value of 0 local edges and network density even when considering a neighborhood using 10 nearest neighbors (bottom maps in Figure 5). One such node is in the center of the point pattern, perhaps indicating that it may be between two separate groups, although this node does not have connection to either side (i.e. not playing a broker role). The second node with zero values for both EdgeScan and NDScan lies north of a dense network of Profaci Family members (one of the five family organizations based in New York City) who is clustered in the southern part of Brooklyn. The zero values for this node indicates that while the node is near other Mafia members, these members are not connected.

We now examine the overall variance in results as part of our sensitivity analysis. A single value of variation is computed for each node, by measuring the variance between the values of the results from the nine neighborhood distinctions shown in Table 4.1. The variance of values for EdgeScan and NDScan are shown in Figure 6. For both EdgeScan and NDScan, resultant node values tend to vary more on the periphery of the network, exhibiting a classic spatial computing problem of edge effects. Notably, for nodes with many zero values for both scan methods are likely to have a lower variance. However a number of nodes that are located in spatial clusters did not have low EdgeScan and NDScan values, and also have low variance. These maps can be used as a guide for assessing the reliability of scan method results, given a node’s location.

We also experimented with measuring local triads (triangles) present in the graph, and local transitivity index, defined as the ratio of $n$(triads) to number of possible triads (Newman and Park 2003), given the local structure in area $A$. The Mafia SSN has 549 triads and a global transitivity index of 0.0001. For three Euclidean distance neighborhood definitions, we calculated the mean local transitivity index and mean number of triads in that neighborhood. We find that at a 2 km distance radius, we are likely to find at least one (1.28) local triangle (Table 4.4).

We compare our values to results from a classic node density scan in each location and compare these statistics to our actual data. We first created a surface using Getis-Ord GI* statistic function to detect statistically-significant clusters of points (with no value associated with each) using a 1 km search radius. We conducted the same test for nodes marked by NDScan results using a 1 km-Euclidean distance neighborhood definition. Results show that areas where nodes form hot spots are not the same areas as the NDScan method detects hot spots (Figure 7). There are five total grid cells marked as hot spots using the traditional point cluster method (two cells are adjacent). In only one of these cells (which has only 90% confidence in southern Brooklyn) is there a statistically-significant NDScan cluster. There are five other adjacent clusters of nodes that are hot spots according to NDScan, and none of these intersect with the traditional results. This result suggests that there is an added benefit to detecting clusters of connected nodes, as they highlight locations where connections exist. Results for EdgeScan values (not shown) reveal (only) two major EdgeScan hot spots, each with many participating nodes. These hot spots matched the traditional hot spot areas in two concentrated locations (Upper East Side and Little Italy), and two other traditional locations did not have any EdgeScan hot spots.