Using Sampling Order in Network Inference

In this previous post, I had talked about how the order of values were sampled, but I gave a pretty esoteric argument involving compression and loss of information in a sample of 8 values.

For my current thesis project, I'm developing an inference methodology for snowball samples. Snowball samples, or more generally respondent driven samples, are used to sample hard-to-reach populations or to explore network structure. The sampling protocol I'm working with is

1. Select someone to interview from the population by simple random sampling.
2. In the interview, ask that person the number of connections they have (where the definition of a  'connection' is defined by the study; it could be business partners, sexual partners, close friends, or fellow injection drug users.)
3. For each connection the interviewed person has, give that person a recruitment coupon to invite that connected person to come in for an interview, often with an incentive.
• If no connected person responds, go to Step 1 and repeat.
• If one connected person responds, go to Step 2 and repeat.
• If multiple people respond, go to Step 2 and interview each of them.

In reality, people are interviewed in the order they come in for an interview. In my simulation, people are interviewed in a breadth first search system, in which I assume connections to the first interviewed person are followed before any connections to those connections are followed. This may make a difference (which I will explore later), because of two limitations of the sample this protocol is modeled after:

1. When the desired sample size has been attained, no more people are interviewed, even if additional people respond to the invitation. (Budget limitation)
2. Connections that lead back to people already in the sample are ignored. Even the information about there being a connection is missing. (Confidentiality limitation)

The budget limitation implies that the interviewing order impacts the subjects that are included in the sample, which in turn affects any statistics measured, even those for which sampling order is ancillary.

The limitation on reported connections implies that the observed network structure is dependent upon the sampling order, even when controlling for the actual members of a sample. For example, if someone receives invitation coupons from multiple connections, they will only show up as directly connected to the first person whose coupon they use. The other connections may not even be observed to be the same network component, even though they must be by definition.

Furthermore, every sampled network will be a forest. That is, a collection of one or more trees - networks that have no cycles, connections 'back into themselves'. Only being able to observe these tree sub-networks of the actual network limits what inferences can be made about the network as a whole. Observed link density isn't very useful for well-connected graphs because the observed link density is maximal just shy of one link/node, in cases where the observed network is one huge component.

Alternate measures of density, like component diversity, ( the Shannon species diversity index, applied to the components that nodes are in), run into this problem as well. In Figure 1 below, component diversity is useless at estimating the average (responding) degree of the network for networks with more than 1.5 links/node.

Figure 1, a network measure based only on observed network structure.

However, we can also estimate things like dPr(used)/dt, the rate of change in the proportion of a sample's connections that are also included in the sample over time. Barring variation due to response rate, we would consider such a measure to be non-positive. 

For networks that are sparse in large populations, the rate of change should be near zero, because very few connections will lead back into nodes that were already explored. What few recruitments there are will be just as successful up until near the end of the sample when a few may be turned away. 

However, for well-connected networks, sampling is done much more often by recruitment rather than by simple random sample. As more a component network is explored, the chance that each successive connection followed leading to someone already in the sample increases. Therefore, for well connected graphs, we would expect dPr(used)/dt to be distinctly negative. 

As Figure 2 shows below, we can use the rate of change in successes to differentiate between populations up to 2.5 links/node, even though most of the networks that we observe from 1.5-2.5 links/node all show up as single large components. Also note how poorly dPr(used)/dt differentiates between networks in the region where the structure-based diversity index excels.

Figure 2, a network measure based on sampling order.

Measures like these, in combination, can be used to make estimates of the features of the population as a whole, but that's for a poster I'm working in the coming weeks.

 

Temporary Blogging Slowdown, Future Plans

It was my original intention to publish four posts on this blog throughout each week. However, I am currently in the last few months of my PhD thesis in Statistics at Simon Fraser University.

Most of my writing effort is being funneled into that in the hopes of defending before the end of next semester. As such, any posts that appear here until the thesis is submitted will be less frequent and of lower effort, such as the laser tag ranking post instead of the goal difference average posts.

With luck, there will be a burst of high-quality material here in here in the late summer and fall to make up for the slack and bring the average back to 4+ good posts per month. I have a lot left to write about, including:

- Snowball sampling and the network analysis work I'm doing currently.

- Milaap, Kiva, Sunfunder, and lending for good and profit.

- Driving forces behind application specific integrated integrated circuits (ASICs), specifically Bitcoin and Super Nintendo.

- FPGAs , and a pipe dream to build an ASIC for large matrix operations.

- Dealing with scrap textiles, composting, crafting, and future industrial needs.

- Some arguments for landfills being the future of mining. Methane harvests, leachate harvests, necessary drilling advances, and the possible gamification of sorting trash.

- Mental health in academia, and mental health personally.

- Many more kudzu levels.

- Plans for a kudzu app, and a pipe dream of making it a carbon negative game through ad revenue and the European Carbon Exchange.

- An essay on how we all suffer from  diversity defecits in heavily gendered fields, as written by a white, Anglophone, heterosexual, cis, middle class man from a nuclear family in the suburbs. (Not a satire, despite the title)

- ongoing development of a senior undergrad course on data formatting and management,

- more R package spotlights, with priority on mice for multiple imputation, and on gologit for modelling ordinal data.

- ongoing development of the R packette for sums of variables.

- ongoing development of an R packette on "debinning", and the methodology surrounding the partial recovery of within-bin data from binned data and covariate information.

- A 'to do' list for humanity, and preparation for a world of automation.

- A commentary on the energy transistion, peak child, and how the tar sands, arctic drilling, and shale fields  cannot possibly be profitable in the long term.

Laser Tag Rating System

This is a rough outline of an idea that Phil Ophus and I had. We want a rating system for laser tag. We want it to be a cumulative reflection of a player's skill over multiple games. We want a means to compare the laser tag skill of players that have a substantial play record, but not necessarily against each other in the same match. In short, we want an Elo or Trueskill style metric that is a shorthand for "this player is X skilled at laser tag".

However, laser tag has less standardization than the sports and games that these metrics are usually applied to.

As it is now, the single game score cards don't give any context of a skill outside of the single match displayed. Scores in general are higher in matches with many players and longer 'ironman' matches. A score of 50000 can demonstrate just as much achievement as a score of 100000 against equally skilled opponents by these factors alone.

There are strategy factors that affect score that don't fairly reflect skill such as picking mostly weak targets, and aggressive running around play rather than base protection. Besides within-game luck, other random noise is added in from equipment effects; some guns are in better shape than others.

Scores are naturally different between free for all and team games, and some players do better in different formats. However, it's reasonable to assume a strong enough association between the skill levels of a given player across formats that one format can inform the other.

All of this variation, and this is only from a single location: Planet Lazer near Braid Station, New Westminster. At this location, the scoring system rewards hitting much more than it penalizes being hit. Also, every target on a vest is worth the same amount, although this isn't necessarily true at other locations.

We want a ratings method that can be used to compare players in different arenas that may be using different rules. Ideally something anyone could see how well they stack up on a regional up to a worldwide level. However even if we only use places that use comparable equipment, the arenas are substantially different, whereas in many other sports the arena effect is negligible. The rules and scoring systems even differ from place to place. 

Our intuition and short train ride's worth of literature searching suggest that no such system exists yet that can handle the non uniform, free for all situations of laser tag. I'm hoping that further developing the cricket similalulator to handle data of cricket players that are compete in multiple formats for multiple teams in a single year.        

On the sampling design and logistics side, there are issues with data collection. What if a location's equipment doesn't record a key variable? How long is data retained? Are there enough return players? It seems like the next step is to draw up a research proposal, and bring it to planet Lazer and see if they would let us record their player data like that.

For after the thesis, if at all.

R Packette - Weighted Binomial Sums

This R code file Weighted_BinSum.r is a... packette? Proto-package? Mini-package?

It's by no means a full R package because it doesn't have the proper documentation, but it's the start of what could be one.

Improving the Exam Experience - A Research Proposal

I've read through quite a few reports on improvements in university learning in the last year. A few ideas have made quite an impression. Ideas like the flipped classroom paradigm, in which the lecture time is spent working through homework problems with the guidance of the instructor and peers, and instruction and note-taking happens before the class with the use of online videos.

However, I've only seen a few pieces on improving the exam experience. Students spend a lot of time thinking about their exam performance, but besides writing good questions (which is a difficult art in itself), not much thought on the instructor side seems to have gone into it.

Kuzdu Update - Lock and Key

New Material:

First, there is a new dungeon available: Lock and Key, which features a pair of new spaces. Most of the map is sparse for treasure except for an optional room in the middle that become available about 2/3 through the map. I'm worried that on its own the treasure hoard is available too late to matter, but it could be just right for any meta-game rewards that are incorporated later.

(Module 03 - Lock and Key)

The rules have been made more explicit in some cases, and the relic deck has been increased from 16 to 20 cards. The card "Drill Relic" has been replaced - see patch notes for details.

(Kudzu Rules and Relic Cards 2015-03-06)

Other Links:

(Module 01 - The Cavern )

(Module 02 - The Halls of Lorsem )

Patch Notes:

I've made some changes to Kudzu's presentation intended to make it scale up more smoothly. 

- First, I've split off each dungeon into its own document. Each dungeon module includes the playable map for that level, a guiding layout, and an explanation of spaces found on that map. If there are any cards specifically for that map, they will be included.

- Generic Kudzu material such as rules and cards, however, are only found in a separate document. This way, updating the rules means changing one document instead of several. It also reduces legacy issues with players applying older rules to newer versions of the game.

- The card "Drill Relic" has been removed from the game for now. Having the ability to place tiles on walls is exciting, but has the potential to ruin any map where a major barrier is a single wall thick, as in Lock and Key. Cards with wall-breaking abilities will appear later, but attached to specific maps as starter cards.

Other thoughts and plans:

- The next module, Ulee's Pitfall, will not introduce new tiles, but will focus on more challenging uses for letter tiles. Players will start with a Pillar Relic, which allows them to turn letter tiles (and other tiles) into walls.

- Another possibility is 'portal' tiles that allow the player to start a crossword at one portal location and continue it at another. However, there may be memory issues with that. I want to experiment more with "Lock and Key" and tracking which keys have been collected before I try that.

- The logistics of a print-and-play game are more involved than I expected. Making things portable is taking more time than I expected, but hopefully the modularity changes will improve the development flow and allow more time for the creative aspects of the game.

- To my knowledge, nobody is testing the game at the moment, and neither am I. Most of my energy is going into thesis work at the moment, so playtesting and finding other playtesters is going to have to wait until the defense.

- I've been investigating the prospects of making Kudzu an Android game, again after the defense. I want to make the game a net good for the environment, and it seems like the best way to do that is by having a running advertisement bar on the bottom of the game, with a large portion of the revenue going towards either planting trees or buying up carbon permits and letting the permits expire unused. There are some other ideas involving in-game currency and 'cashing out', but the logistics of that are a distraction from game development at the moment.

New powerplay metrics applied to 2014-15 NHL teams

In this previous post I made a case for a new powerplay metric called GDA-PK (Goal-Difference Average -  Penalty Kill) that used the amount of time in a powerplay state rather than the number of powerplay instances as its basis. My argument was essentially that not every powerplay is the same: some are majors, some are interrupted by goals or additional penalties, and others are confounded by pulling the goalie and by shorthanded goals.

My aim was to present a new metric that would measure the effectiveness of special lineups in way that removed a lot of the noise and was easier to interpret in the context of the rest of the game.

GDA-PK represents the average goals gained or lost per hour when killing a penalty. In Table 1 below, for example, the Vancouver Canucks, have a GDA-PK this season of -3.87, so they fall behind by 3.87 goals for every 60 minutes in a 4-on-5 situation. This can also be written that the 'nucks lose a goal for every 60/3.87 = 15.5 minutes of penalty killing.

Likewise, GDA-PP represents the average goals gained or lost per hour of powerplay. Table 1 shows that the Detroit Red Wings manage to gain 8.00 goals for every 60 minutes of powerplay, or get ahead by 1 goal for every 7.5 minutes spent on the powerplay. This isn't the same as gaining 1 goal for every 7.5 minutes of penalty in favour of the Red Wings, because a lot of those penalties will be cut short by conversions.

Also note that it's 'Goal Difference', not goals scored/allowed. This way, both measures account for shorthanded goals by treating them as negative powerplay goals.

I wanted to see if there would be any major divergences between GDA measures and the traditional PP% and PK% (PowerPlay percent and Penalty Kill %) measures in terms of ranking the teams. Ideally, both measures would agree in rankings because they are intended to measure the same thing.

Results

Table 1: Powerplay and Penalty Kill Goal Differential per Hour (Goals against minus goals for) and related statistics for teams for the 901 of 1230 regular season games up to 2015-02-24, inclusive.

Team GDA-PK Pkill Pct GDA-PP Pplay Pct ANA -3.44 0.814 4.35 0.177 ARI -7.77 0.779 5.97 0.212 BOS -5.62 0.824 5.00 0.174 BUF -6.88 0.754 1.59 0.118 CAR -3.26 0.880 5.66 0.185 CBJ -5.44 0.808 6.32 0.207 CGY -4.64 0.803 5.96 0.175 CHI -3.96 0.862 6.14 0.187 COL -4.49 0.832 3.56 0.133 DAL -6.18 0.793 5.43 0.180 DET -5.33 0.832 8.00 0.252 EDM -5.67 0.780 4.41 0.152 FLA -6.66 0.790 4.04 0.148 L.A -5.35 0.798 5.17 0.186 MIN -3.63 0.860 3.44 0.159 MTL -3.88 0.856 4.90 0.170 N.J -6.35 0.798 5.20 0.195 NSH -5.24 0.820 5.80 0.173 NYI -6.69 0.746 5.88 0.185 NYR -3.33 0.830 4.89 0.182 OTT -4.31 0.825 4.65 0.172 PHI -8.49 0.760 6.76 0.233 PIT -3.56 0.856 4.81 0.205 S.J -5.26 0.804 5.90 0.205 STL -6.67 0.804 6.67 0.233 T.B -4.83 0.833 4.11 0.171 TOR -4.52 0.821 4.52 0.186 VAN -3.76 0.859 4.83 0.184 WPG -4.75 0.807 5.05 0.188 WSH -6.17 0.808 7.76 0.237

League-wide GDA-PK: -5.163

League-wide GDA-PP: +5.163

Correlations between proposed and classic measures:

PP Pearson r = 0.892, Spearman's rho = 0.810

PK Pearson r = 0.833, Spearman's rho = 0.841

The league-wide GDA-PP and the GDA-PK balance out by definition.

Notable performances are highlighted in Table 1. The Carolina Hurricanes seem to get a lot more mileage out of their powerplays than their opponents (5.66 goals/hr gained vs. 3.26 goals/hr lost). Philadelphia and Washington are very exciting to watch during penalties in both directions.

After 60 games, each team has had 5-6 hours of powerplay time, and 5-6 hours of penalty kill time. As such, there's still a lot of uncertainty in the GDA-PK and PP of individual teams. Each team value should be considered to have a 'plus-or-minus 2 goals/hr' next to it. For example, Boston's GDA-PP of 5.00 could really mean they've been gaining 3 goals/hr on the powerplay and getting some lucky bounces, or that they should be gaining 7 goals/hr, but can't catch a break this season.

Further inference from these values is possible. We could make reasonable GDA-PK and PP estimates of specific matchups. For example, Pittsburgh's excellent penalty killing and Washington's excellent powerplay skills should cancel each other out. We would expect the Washington Capitals to gain (WSH PP + (- PIT PK) - LeagueAvg) =  (7.76 + 3.56 - 5.163) = 6.16 goals/hr on the Penguins with a 1-man advantage.

We could also find the average length of a minor or major penalty, so we can use this to estimate how many goals a given penalty is worth, either league wide or for a given team. We can also find the success rate of penalty shots, assuming we can use the shootout to increase our sample size, so we could also find out how many penalty minutes a penalty shot is worth.

The correlation measures Pearson's r and Spearman's rho are positive and far from zero (they are on a scale from -1 to 1). These correlations indicate a strong agreement between the GDA measures and the traditional measures; a team that puts up good PP% / PK% numbers will put up comparably good GDA-PP/PK numbers.

Furthermore, we can use a similar metric to isolate even-strength situations and see how well a team fares when there are no penalties involved. In Table 2, GDA-EV (Goal Difference Average - EVen Strength) refers to the number of goals a team gains or loses on average per 60 minutes of even strength play. A positive number represents a team that outscores their opponents when there are no active penalties (or only offsetting ones), and a negative number represents a team that falls behind at even strength.

Table 2: Even-Strength Goal differential per hour (Goals against minus goals for) and related statistics for teams for the 901 of 1230 regular season games up to 2015-02-24, inclusive.

Team GP Goal Diff GD/G GDA-EV ANA 61 8 0.13 0.06 ARI 61 -71 -1.16 -1.19 BOS 60 4 0.07 0.08 BUF 61 -94 -1.54 -1.09 CAR 59 -24 -0.41 -0.67 CBJ 59 -31 -0.53 -0.66 CGY 60 12 0.20 -0.08 CHI 61 29 0.48 0.28 COL 61 -17 -0.28 -0.08 DAL 59 -11 -0.19 0.00 DET 61 25 0.41 0.17 EDM 59 -65 -1.10 -1.05 FLA 62 -21 -0.34 0.00 L.A 60 16 0.27 0.48 MIN 59 11 0.19 0.16 MTL 60 25 0.42 0.47 N.J 60 -20 -0.33 -0.04 NSH 60 42 0.70 0.86 NYI 61 22 0.36 0.37 NYR 62 43 0.69 0.58 OTT 59 4 0.07 -0.11 PHI 61 -12 -0.20 -0.10 PIT 60 25 0.42 0.37 S.J 61 0 0.00 -0.22 STL 60 32 0.53 0.54 T.B 62 38 0.61 0.61 TOR 60 -16 -0.27 -0.39 VAN 60 13 0.22 0.10 WPG 62 3 0.05 0.23 WSH 61 30 0.49 0.34

League-wide GDA-EV 0.000

Correlation between goal difference per game, and GDA-EV:

Pearson's r = 0.941 , Spearman's rho = 0.916

The league-wide GDA-EV is exactly 0, as expected. There is a very strong linear relationship between GDA-EV and simple goal differential, which may indicate that powerplay performance isn't as important as it's made out to be. Looking at all goals, the Buffalo Sabres seem to be uniquely awful, but when you remove the effect of penalties, they're merely as bad as Edmonton and Arizona.

Another note is that even though Montreal is currently the top of the Eastern Conference standings, they're only putting up half a goal more than their opponents on the 5-on-5 or the 4-on-4. They're on par with the L.A. Kings, who are currently on the playoff bubble.

Since teams spend the large majority of their time at even-strength, GDA-EV has a lot of data to draw from. You should consider them to be (plus-or-minus 0.5 goals/hr).

This is still very much a work in progress, and these measurements should be taken as preliminary only. There are likely still some bugs to work out that have gone unseen. 

In this previous post, I gave a short demo of the nhlscrapr package, which allows anybody to download a play-by-play table of every hit, shot, faceoff, line change, penalty, and goal recorded. The data used to make Tables 1 and 2 come from nhlscrapr. Select details are found in the methodology below.

Methodology

I've written an R script, to count the time spent in each powerplay state and the number of events (in this case, events are goals) that occur in each state and for/against each team. A cautionary note to those trying to do similar things: the numbers in the home.skates and away.skaters variables are unreliable and you're better off tracking it yourself if it's critical. The other variables appeared to be pretty reliable, such as home and away goalie ID which made identifying empty-net times possible.

I apologize, but I won't be sharing the script to get this data, until I've considered (and possibly taken advantage of) the academic publication potential of the results in the tables below. Also, the script is a modification of one used for a research paper Dr. Paramjit Gill and I currently have in the submission stage, and I don't want to complicate that process.

Overtime and two-man advantage situations was ignored. Neither the goals nor the time spent are included here. However, the league-wide goal differential seems to be in the 12-16 goals-per-hour range. There is nowhere near enough data to say anything about individual teams in these situations.

The league-wide measures are not the raw average of the values from each of the 30 teams because some teams spend more time short handed or on the power play. Instead, they are computed by treating the whole league as a single team playing against itself. If a team draws more penalties and spends more time on the powerplay, that team's performance will count for more towards the league-wide average than other teams. However, in reality, every team is contributing between 3.0% and 3.6% towards each league measure.

Any goals scored when the goalie was on the bench for an extra skater (e.g. during a delayed penalty call or when a team is losing at the very end of the game) were ignored. This includes goals on empty nets, goals by teams with empty nets, and that time the Flames did both.  The time where one (or both?) goalies were off the ice was deducted from the appropriate situation. There was a mean average of about 50 seconds of empty net per game, with a lot of games with no empty net time.

Finally, only regulation play (the first 60 minutes of each game) is considered. This is to filter out any confounding issues such as teams scoring less often in overtime than they do in regulation.