Degree-preserving randomization
Network science | ||||
---|---|---|---|---|
Network types | ||||
Graphs | ||||
|
||||
Models | ||||
|
||||
| ||||
Degree Preserving Randomization is a technique used in Network Science that aims to assess whether or not variations observed in a given graph could simply be an artifact of the graph's inherent structural properties rather than properties unique to the nodes, in an observed network.
Background
Cataloged as early as 1996,[1] the simplest implementation of degree preserving randomization relies on a Monte Carlo algorithm that rearranges, or "rewires" the network at random such that, with a sufficient number of rewires, the network's degree distribution is identical to the initial degree distribution of the network, though the topological structure of the network has become completely distinct from the original network.
Degree preserving randomization, while it has many different forms, typically takes on the form of a relatively simple approach: for any network consisting of
As is common with algorithms based on Markov chains, the number of iterations, or individual rewires, that must occur on a given graph such that the graph is sufficiently random and distinct from the original graph is unknown, though Espinoza[2] asserts that a safe minimum threshold is
Uses
There are several cases in which published research have explicitly employed degree preserving randomization in order to analyze network properties. Dekker[5] used rewiring in order to more accurately model observed social networks by adding a secondary variable,
Additionally, some work has been done in investigating how Degree Preserving Randomization may be used in addressing considerations of anonymity in networked data research, which has been shown to be a cause for concern in Social Network Analysis, as in the case of a study by Lewis et al.[8][9] Ultimately the work conducted by Ying and Wu, starting from a foundation of Degree Preserving Randomization, and then forwarding several modifications, has showed moderate advances in protecting anonymity without compromising the integrity of the underlying utility of the observed network.[10]
Additionally, the method is similar in nature to the broadly used Exponential random graph models popularized in social science,[11][12] and indeed the various forms of modeling networks against observed networks in order to identify and theorize about the differences expressed in real networks. Importantly, Degree Preserving Randomization provides a simple algorithmic design for those familiar with programming to apply a model to an available observed network.
Example
What follows is a small example showing how one may apply Degree Preserving Randomization to an observed network in an effort to understand the network against otherwise random variation while maintaining the degree distributional aspect of the network. The Association of Internet Researchers has a Listserv that constitutes the majority of discussion threads surrounding their work. On it, members post updates about their own research, upcoming conferences, calls for papers and also engage one another in substantive discussions in their field. These emails can in turn constitute a directed and temporal network graph, where nodes are individual e-mail accounts belonging to the Listserv and edges are cases in which one e-mail address responds to another e-mail address on the Listserv.
In this observed network, the properties of the Listserv are relatively simple to calculate - for the network of 3,235 individual e-mail accounts and 9,824 exchanges in total, the observed reciprocity of the network is about 0.074, and the [Average path length|average path length] is about 4.46. Could these values be arrived at simply through the nature of the network's inherent structure?
Applying the
References
- ↑ Rao, A Ramachandra; Jana, Rabindranath; Bandyopadhyay, Suraj (1996). "A Markov chain Monte Carlo method for generating random (0, 1)-matrices with given marginals". Indian Journal of Statistics Series A. http://sankhya.isical.ac.in/search/58a2/58a2021.pdf. Retrieved November 5, 2014.
- ↑ Espinoza, Max. On Network Randomization Methods: A Negative Control Study. http://biogrid.engr.uconn.edu/REU/Reports_12/Final_Reports/Max.pdf. Retrieved 2014-11-06.
- ↑ Re: [igraph Degree-preserving rewiring of a large graph], http://lists.gnu.org/archive/html/igraph-help/2014-04/msg00003.html
- ↑ Pinar, Ali; Ray, Jaideep; Seshadri, S. (2012), Are we there yet? When to stop a Markov chain while generating random graphs, Bibcode: 2012arXiv1202.3473R, http://www.graphanalysis.org/SIAM-CSE13/05_Pinar.pdf
- ↑ Dekker, A.H. (2007), "Realistic Social Networks for Simulation using Network Rewiring", Proceedings MODSIM 2007, http://www.mssanz.org.au/MODSIM07/papers/13_s20/RealisticSocial_s20_Dekker_.pdf
- ↑ Liu, Y-Y.; Slotine, J-J; Barabási, A-L (2012), "Control Centrality and Hierarchical Structure in Complex Networks", PLOS ONE 7 (9): e44459, doi:10.1371/journal.pone.0044459, PMID 23028542, Bibcode: 2012PLoSO...744459L
- ↑ Liu, Yang-Yu; Slotine, Jean-Jacques; Barabási, Albert-Laszlo (2013), "Effect of correlations on network controllability", Sci. Rep. 3: 1067, doi:10.1038/srep01067, PMID 23323210, Bibcode: 2013NatSR...3E1067P
- ↑ Parry, Marc (July 10, 2011), "Harvard Researchers Accused of Breaching Students' Privacy", The Chronicle of Higher Education, http://chronicle.com/article/Harvards-Privacy-Meltdown/128166/, retrieved November 5, 2014
- ↑ Lewis, Kevin; Kaufman, Jason; Gonzalez, Marco; Wimmer, Andreas; Christakis, Nicholas (2008), "Tastes, ties, and time: A new social network dataset using Facebook.com", Social Networks 30 (4): 330–342, doi:10.1016/j.socnet.2008.07.002, http://media.withtank.com/3379594a17/tastes_ties_and_time-_a_new_social_network_dataset_using_facebook.com.pdf
- ↑ Ying, Xiaowei; Wu, Xintao (2008), "Randomizing Social Networks: a Spectrum Preserving Approach", SDM: 739–750, doi:10.1137/1.9781611972788.67, ISBN 978-0-89871-654-2
- ↑ Snijders, Tom AB. (2002), "Markov chain Monte Carlo estimation of exponential random graph models", Journal of Social Structure 3 (2): 1–40, https://www.researchgate.net/publication/2544726
- ↑ Robins, Garry; Patterson, Pip; Kalish, Yuval; Lusher, Dean (2007), "An introduction to exponential random graph models for social networks", Social Networks 29 (2): 173–191, doi:10.1016/j.socnet.2006.08.002
External links
![]() | Original source: https://en.wikipedia.org/wiki/Degree-preserving randomization.
Read more |