PaperlayerView exact revision on arXiv

Source-linked AI summary

An overview and perspective on social network monitoring

William H. Woodall, Meng J. Zhao, Kamran Paynabar, Ross Sparks, James D. Wilson

arXiv:1603.09453v1stat.OTcs.SIphysics.soc-ph

TL;DR

Industrial statistical-process monitoring had not studied matrices of Poisson counts, a data structure relevant to network monitoring. The paper reviews social-network monitoring methods and relates them to industrial process monitoring and public-health surveillance. The authors conclude that social-network monitoring is an important research area with abundant opportunities.

  • Problem

    Industrial statistical-process monitoring had not studied matrices of Poisson counts, a data structure relevant to network monitoring.

    Source: 1.Introduction · pp. 3–4

  • Method

    The paper reviews social-network monitoring methods and relates them to industrial process monitoring and public-health surveillance.

    Source: 1.Introduction · p. 2

  • Results

    The authors conclude that social-network monitoring is an important research area with abundant opportunities.

    Source: §4 · p. 16

  • Takeaways & Limitations

    The authors recommend comparing social-network monitoring methods on simulated networks, where anomalies can be modeled and detection ability assessed.

    Source: §3.2 · p. 13

    For the described increment-based contact model, the interval division and estimation of π were unresolved, and multiple contacts within one increment would lose information.

    Source: §3.3 · p. 15

Abstract

from arXiv · show

In this expository paper we give an overview of some statistical methods for the monitoring of social networks. We discuss the advantages and limitations of various methods as well as some relevant issues. One of our primary contributions is to give the relationships between network monitoring methods and monitoring methods in engineering statistics and public health surveillance. We encourage researchers in the industrial process monitoring area to work on developing and comparing the performance of social network monitoring methods. We also discuss some of the issues in social network monitoring and give a number of research ideas.

1.Introduction

The introduction frames social-network monitoring as detecting sudden, large changes in network behavior and connects it to related monitoring fields. It defines the data structure and highlights how data representation affects monitoring.

1.Introduction

  • The paper extends Savage et al. (2014) by adding monitoring papers and relating their methods to industrial process monitoring and public health surveillance.The introduction notes applications including identifying influential participants, clandestine structures, and fraudulent or predatory activity.Source: 1.Introduction · p. 2
  • Social-network monitoring seeks sudden, large changes in part of a network, with increases often prioritized and global changes typically easiest to detect.Anomaly definitions depend on operational normal conditions; networks evolve, so detecting every small change is usually not the goal.Source: 1.Introduction · p. 2
  • Network observations are time-indexed communication levels between pairs of individuals, represented as sparse adjacency matrices with zero diagonals.Communication may be recorded as counts or indicators of contact; undirected data produce symmetric matrices.Source: 1.Introduction · pp. 2–3
  • Converting directed counts to undirected or binary data loses information, and greater aggregation is associated with poorer monitoring performance.Undirected data cannot show how contacts propagate through the network.Source: 1.Introduction · p. 3
  • Industrial statistical-process monitoring had studied single and multivariate Poisson data, but not matrices of Poisson counts.Public-health scan methods exploit the natural spatial ordering of regions, whereas network individuals usually have no natural ordering; social and computer network monitoring also differ in structure, objectives, data volume, frequency, and periodicity.Source: 1.Introduction · p. 4

2. Monitoring methods

This section reviews recent social-network monitoring methods and relates them to statistical process monitoring.

2. Monitoring methods

  • The review groups recent social-network monitoring methods into four broad categories, relating them to statistical process monitoring and prospective public-health surveillance.The authors assume familiarity with statistical process monitoring and direct readers to Montgomery (2013) for background.Source: §2 · p. 5

1.Control chart and hypothesis testing methods

The section relates control-chart and hypothesis-testing approaches to social-network monitoring, describing methods based on network metrics, regression, and modularity. It also identifies limitations in baseline estimation, anomaly sensitivity, and online monitoring assumptions.

1.Control chart and hypothesis testing methods

  • The paper argues that process-monitoring concepts, including distinguishing retrospective Phase I baseline analysis from prospective Phase II monitoring, could benefit social-network monitoring.The authors discuss this distinction as an issue for network monitoring.Source: 1.Control chart and hypothesis testing… · p. 5
  • McCulloh and Carley used CUSUM and EWMA charts on global network metrics, but reliable chart performance may require many more than five baseline graphs.Node or sub-network metrics could also serve as inputs.Source: 1.Control chart and hypothesis testing… · p. 5
  • Azarnoush et al. (2016) modeled pairwise contact probabilities with logistic regression using sub-network membership and individual covariates, then tested for changes in model fit.Their three references were fixed-baseline, all-previous-graphs dynamic, and sliding-window dynamic approaches; the authors favor the moving window as networks evolve.Source: 1.Control chart and hypothesis testing… · p. 6
  • Some anomalies are invisible to Azarnoush et al.’s (2016) logistic-regression method when within-group contacts are redistributed without changing model coefficients or the likelihood-ratio test.The paper identifies this as profile monitoring.Source: 1.Control chart and hypothesis testing… · p. 6
  • Azarnoush et al. (2016) compared their methods with McCulloh and Carley’s (2011) global-metric methods, but a fairer comparison would use metrics for activity within each assumed individual category.The latter methods did not incorporate available covariate information.Source: 1.Control chart and hypothesis testing… · p. 6
  • Miller et al. (2011, 2013) projected modularity-matrix residuals onto two eigenvectors and tested whether projected values clustered by quadrant.A large contingency-test statistic was treated as evidence of change; Miller et al. (2013) used a log-linear connection model whose reduced computation permits larger networks.Source: 1.Control chart and hypothesis testing… · pp. 6–7
  • Miller et al. (2011, 2013) used a matched-filter approach assuming a known anomaly signal model, but its timing is unknown and the studies evaluated immediate anomalies rather than continuous Phase II monitoring.Their simulations used fixed anomalous-subgraph density with changing edges, or linearly increasing density over 32 samples; large windows can build inertia and slow detection of delayed changes.Source: 1.Control chart and hypothesis testing… · p. 7

2.Bayesian methods

The reviewed Bayesian and scan-based approaches identify unusual contacts or network activity using predictive distributions, neighborhood metrics, or ranked sub-networks. Their usefulness depends on baseline choices, anomaly structure, and what the monitored statistic can detect.

2.Bayesian methods

  • Heard et al. (2010) used Bayesian predictive control limits to flag unusual pairwise contact counts, then analyzed the resulting smaller sub-network for anomalous behavior.Their Poisson or hurdle-Poisson models allow for counts and elevated probabilities of no contact; a 0.05 p-value threshold can falsely flag many pairs in large networks.Source: 2.Bayesian methods · p. 8
  • Heard et al. (2010) updated parameter estimates with prior data, unlike methods based only on fixed Phase I data; Heard et al. (2011) recommended shorter moving windows for longer-term monitoring.The review relates updating with all prior data to self-starting methods and notes its similarity to Azarnoush’s dynamic reference approach.Source: 2.Bayesian methods · pp. 8–9

2.3 Scan methods

  • Priebe et al. (2005) standardized each individual’s 0th-, 1st-, and 2nd-order neighborhood sizes, then signaled when the largest metric exceeded its moving-window mean by five standard deviations.The method was applied retrospectively to an Enron email network and was stated to be usable prospectively.Source: §2.3 · p. 9
  • The review distinguishes network scans, which maximize standardized node-metric deviations over moving windows, from traditional scans over temporal or spatiotemporal window counts.The Priebe et al. (2005) method is not a traditional scan in the sense of Kulldorff (2001) or Joner et al. (2008).Source: §2.3 · pp. 9–10
  • Moving-window baselines can accommodate gradual network evolution, but undetected changes enter the baseline and sustained anomalies will not continue to signal.Compared with the moving-window approach, Heard et al. (2010) incorporated all prior data into estimates of process level.Source: §2.3 · p. 10
  • Sparks (2015, 2016) ranked individuals before spatiotemporal scanning to reduce computation, but that ordering may miss communities or anomalies outside the represented sub-networks.The alternative of scanning all subsets of a given size was described as infeasible.Source: §2.3 · p. 10
  • Cheng and Dickinson (2013) combined Priebe et al.’s (2005) scans with moving-window metric cross-correlations, which may miss current activity and obscure pairwise relationships when averaged.The review also notes that their method does not appear to account for a time series’ correlation with itself being one.Source: §2.3 · p. 11

4.Time series models

Time-series models can monitor network metrics for unusually large residuals, connecting social-network monitoring with established process-monitoring applications in public health and industry.

4.Time series models

  • Time-series models can be fitted to network metrics, with unusually large residuals indicating network changes.The approach is described as applicable to time series of any network metric.Source: 4.Time series models · p. 11
  • Network-metric time-series monitoring has also been widely used in public health surveillance and industrial and quality-related process monitoring.Woodall and Montgomery (2014) and Unkel et al. (2011) reviewed these application areas.Source: 4.Time series models · p. 11
  • Pincombe (2005) is cited as an example of a network-monitoring method based on time-series models.Source: 4.Time series models · p. 11

5. Other approaches

The section surveys several network-analysis approaches for detecting structural changes, unusual events, compromised accounts, and emerging topics.

5. Other approaches

  • Cazabet et al. (2010) update potentially overlapping communities as data arrive and identify new communities.Source: §5 · p. 11
  • Chae et al. (2012) detect abnormal events using spatiotemporal social-media data, seasonal decomposition, and moving-window control charts for unusual topic-series peaks and outliers.Altshuler et al. (2013) instead use event timing and network traffic without message-content knowledge to detect extraordinary events.Source: §5 · p. 12
  • Egele et al. (2013) identify compromised accounts by finding groups with similar short-term behavioral changes, while Takahashi et al. (2011) detect emerging topics from users’ mentioning behavior.The compromised-account method was illustrated with Twitter and Facebook data.Source: §5 · p. 12

1. Phase I vs. Phase II

The paper relates social-network monitoring to process-monitoring phases, simulation design, distributional assumptions, and performance metrics, highlighting choices that affect how methods are assessed.

1. Phase I vs. Phase II

  • In Phase I, historical data support retrospective model fitting; Phase II uses that baseline for prospective monitoring as new samples arrive.The authors argue that stable network baselines may be harder to obtain than industrial-process baselines, increasing the need for moving windows, which are unsuitable when industrial processes should not evolve.Source: §1 · pp. 12–13

3.2 Use of computer simulation

  • Simulation studies can compare methods on modeled anomalies, ideally using realistic networks, while simplified networks can still reveal relative performance.The paper identifies network size, subgrouping, covariates, and anomaly type as simulation-design choices; cited examples use labeled covariates or Poisson contact counts.Source: §3.2 · pp. 13–14

3.3 Distributional assumptions

  • Distributional choices include Poisson or hurdle-Poisson contact counts, negative-binomial models for overdispersion, and graph models suited to different degree patterns.The authors note that social-network counts can have heavier tails than Poisson counts; Erdős–Rényi, preferential-attachment, and degree-corrected stochastic block models are alternatives for network structure.Source: §3.3 · p. 14
  • The authors reject a proposed binomial approach because increment choice and π estimation are unresolved, and multiple contacts within an increment lose information.Vigliotti and Hankin’s approach divides each period into increments and treats whether a connection occurs in each as Bernoulli.Source: §3.3 · pp. 14–15
  • For parametric network simulations, the authors suggest beginning with independence of the network matrices over time.They reason that a method performing poorly under this assumption is unlikely to work well under a more general model.Source: §3.3 · p. 15

3.4 Performance metrics for monitoring schemes

  • Average run length suits sustained changes, whereas temporary changes call for the probability of detecting the change while it remains in effect.McCullough and Carley’s average detection length is equivalent to ARL.Source: §3.4 · p. 15
  • Steady-state metrics assess delayed changes, and the authors expect Miller et al.’s method to perform less well on delayed than immediate network changes.Other useful measures include individual misclassification or Dice similarity for identifying affected people, change-time estimation, and false discovery rate for large networks with repeated anomaly flags.Source: §3.4 · pp. 15–16
  • Simulation metrics enable comparisons, but practitioners should not expect limited baseline data to deliver a specified in-control ARL.The paper cites the difficulty of achieving this even in the simpler case of monitoring a normal variable’s mean.Source: §3.4 · p. 16

4. Research opportunities and conclusions

The authors see social-network monitoring as a promising research area and call for systematic method comparisons alongside work on unresolved modeling and monitoring choices.

4. Research opportunities and conclusions

  • Comparisons are needed because case studies rarely establish whether detections are false alarms, and case-specific methods may perform poorly elsewhere.The authors also call for scalable methods and guidance on selecting network metrics that fit monitoring objectives.Source: §4 · p. 17
  • CUSUM and EWMA methods based on network metrics are expected to detect changes better than Shewhart-type approaches, but comparisons are needed.Many existing approaches make decisions from each graph individually as it arrives.Source: §4 · p. 17
  • Research should test how temporal aggregation affects detection and how converting contact counts to Bernoulli data affects information and detection ability.The authors anticipate greater difficulty with increased aggregation, especially for Bernoulli data, and possible substantial information loss from reducing counts.Source: §4 · p. 17
  • The authors anticipate that direct subnetwork searches may outperform first identifying anomalous individuals because their resulting subnetwork need not itself be anomalous.Source: §4 · pp. 17–18
  • Further work should clarify which network changes are undetectable when monitoring a specified number of modularity-matrix eigenvalues.Source: §4 · p. 18
  • False-discovery-rate methods may suit simultaneous charting approaches, including p-value-based methods concerned with many false positives.The authors identify Heard et al. (2010) and Vigliotti and Hankin (2015) as examples.Source: §4 · p. 18
  • Methods using attributed data remain limited, despite the relevance of labels, message size, and contact timing.The paper identifies Miller et al. (2013) and Azarnoush et al. (2016) as the only proposed methods for attributed data thus far.Source: §4 · p. 18
  • Open questions also include smoothing versus moving windows, window length and lag, seasonal effects, evolving membership, and Bayesian versus self-starting charts.The authors note that it is unclear which smoothing approach is better; they also call for methods that avoid treating network entry or exit as changes of interest.Source: §4 · pp. 18–19

APPENDIX: SHORT TUTORIAL ON NETWORK TERMINOLOGY

The tutorial defines core graph components and terminology, then describes subgraphs, node relationships, and network metrics used to characterize social networks. Its Enron example illustrates how network structure and communication can change over time.

Loading 1603.09453v1…