skip to main content
10.1145/1810617.1810637acmconferencesArticle/Chapter ViewAbstractPublication PageshtConference Proceedingsconference-collections
research-article

Analysis of graphs for digital preservation suitability

Published: 13 June 2010 Publication History

Abstract

We investigate the use of autonomically created small-world graphs as a framework for the long term storage of digital objects on the Web in a potentially hostile environment. We attack the classic Erdos --- Renyi random, Barabási and Albert power law, Watts --- Strogatz small world and our Unsupervise. Small World (USW) graphs using different attacker strategies and report their respective robustness. Using different attacker profiles, we construct a game where the attacker is allowed to use a strategy of his choice to remove a percentage of each graph's elements. The graph is then allowed to repair some portion of its self. We report on the number of alternating attack and repair turns until either the graph is disconnected, or the game exceeds the number of permitted turns. Based on our analysis, an attack strategy that focuses on removing the vertices with the highest betweenness value is most advantageous to the attacker. Power law graphs can become disconnected with the removal of a single edge; random graphs with the removal of as few as 1% of their vertices, small-world graphs with the removal of 14% vertices, and USW with the removal of 17% vertices. Watts --- Strogatz small-world graphs are more robust and resilient than random or power law graphs. USW graphs are more robust and resilient than small world graphs. A graph of USW connected WOs filled with date could outlive the individuals and institutions that created the data in an environment where WOs are lost due to random failures or directed attacks.

References

[1]
R. Albert, H. Jeong, and A.-L. Barabási. Error and Attack Tolerance of Complex Networks. Nature, 406(6794):378--382, July 2000.
[2]
A.-L. Barabási. The physics of the Web. Physics World, 14(7):33--38, 2001.
[3]
A.-L. Barabási and E. Bonabeau. Scale-Free Networks. Scientific American, 288(5):60--69, May 2003.
[4]
N. Baumann and S. Stiller. Network Models. Network Analysis, Lecture Notes in Computer Science, 3418:341--341, 2005.
[5]
B. Bollobás and O. Riordan. Robustness and Vulnerability of Scale-Free Random Graphs. Internet Mathematics, 1(1):1--35, 2004.
[6]
D. S. Callaway, M. Newman, S. H. Strogatz, and D. J. Watts. Network Robustness and Fragility: Percolation on Random Graphs. Physical Review Letters, 85(25):5468--5471, 2000.
[7]
C. L. Cartledge and M. L. Nelson. Connectivity Damage to a Graph by the Removal of an Edge or Vertex. Technical report, Old Dominion University, Computer Science Department.
[8]
C. L. Cartledge and M. L. Nelson. Self-Arranging Preservation Networks. In JCDL '08: Proceedings of the 8th ACM/IEEE-CS joint conference on Digital libraries, pages 445--445, 2008.
[9]
C. L. Cartledge and M. L. Nelson. Unsupervised creation of small world networks for the preservation of digital objects. JCDL '09: Proceedings of the 9th ACM/IEEE-CS Joint Conference on Digital Libraries, pages 349--352, 2009.
[10]
R. Criado, J. Flores, B. Hernández-Bermejo, J. Pello, and M. Romance. Effective measurement of network vulnerability under random and intentional attacks. Journal of Mathematical Modelling and Algorithms, 4(3):307--316, 2005.
[11]
G. Csárdi and T. Nepusz. The igraph software package for complex network research. InterJournal Complex Systems, 1695, 2006.
[12]
J. Farkas, C. Antal, G. Tóth, and L. Westberg. Distributed Resilient Architecture for Ethernet Networks. In Design of Reliable Communication Networks, 2005.(DRCN 2005). Proceedings. 5th International Workshop on, page 8, 2005.
[13]
J.-L. Guillaume, M. Latapy, and C. Magnien. Comparison of Failures and Attacks on Random and Scale-free Networks. Principles of Distributed Systems, Lecture Notes in Computer Science, 3544:186--196, 2005.
[14]
P. Holme, B. J. Kim, C. N. Yoon, and S. K. Han. Attack vulnerability of complex networks. Physical Review E, 65(5):56109, 2002.
[15]
I. Jacobs and N. Walsh. Architecture of the World Wide Web. World Wide Web Consortium, April 2004.
[16]
S. Janson, T. Łuczak, and A. Rucińnski. Random Graphs. Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, 2000.
[17]
R. Kahn and R. Wilensky. A Framework for Distributed Digital Object Services. International Journal on Digital Libraries, 6(2):115--123, 2006.
[18]
G. W. Klau and R. Weiskircher. Robustness and Resilience. Network Analysis: Methodological Foundations. Berlin, Heidelberg: Springer, pages 417--437, 2005.
[19]
C. Lagoze, H. Van de Sompel, P. Johnston, M. L. Nelson, R. Sanderson, and S. Warner. Object Re-Use & Exchange: A Resource-Centric Approach. Technical Report arXiv:0804.2273, 2008.
[20]
H. Lee, J. Kim, and W. L. Lee. Resiliency of Network Topologies under Path-Based Attacks. IEICE Transactions on Communications, 89(10):2878, 2006.
[21]
F. McCown, M. L. Nelson, and H. Van de Sompel. Everyone is a Curator: Human-Assisted Preservation for ORE Aggregations. Proceedings of the DigCCurr 2009, Jan 2009.
[22]
S. Milgram. The Small-World Problem. Psychology Today, 2(1):60--67, 1967.
[23]
Y. Moreno, R. Pastor-Satorras, A. Vazquez, and A. Vespignani. Critical Load and Congestion Instabilities in Scale-Free Networks. Europhysics Letters, 62(2):292--298, 2003.
[24]
A. E. Motter and Y.-C. Lai. Cascade-based attacks on complex networks. Physical Review E, 66(6):65102, 2002.
[25]
M. L. Nelson and K. Maly. Buckets: Smart Objects for Digital Libraries. Communications of the ACM, 44(5):60--62, 2001.
[26]
S. Netotea and S. Pongor. Evolution of robust and efficient system topologies. Cellular Immunology, 244(2):80--83, 2006.
[27]
M. Newman. The Structure and Function of Complex networks. Arxiv preprint cond-mat/0303516, 2003.
[28]
M. E. J. Newman. Models of the Small World: A Review. Journal of Statistical Physics, 101:819, 2000.
[29]
T. Opsahl and P. Panzarasa. Clustering in Weighted Networks. Social Networks, 31(2):155--163, 2009.
[30]
M. Randić and L. M. DeAlba. Dense Graphs and Sparse Matrices. J. Chem. Inf. Comput. Sci, 37(6):1078--1081, 1997.
[31]
T. Tanizawa, G. Paul, R. Cohen, S. Havlin, and H. Stanley. Optimization of network robustness to waves of targeted and random attacks. Physical Review E, 71(4):47101, 2005.
[32]
D. J. Watts and S. H. Strogatz. Collective dynamics of 'small world' networks. Nature, 393:440--442, June 1998.
[33]
E. Zio and G. Sansavini. Modeling failure cascades in network systems due to distributed random disturbances and targeted intentional attacks. Proceeding of the European Safety and Reliability Conference (ESREL 2008), 2008.

Cited By

View all
  • (2021)Analysis of Nature-Inspired Algorithms for Long-Term Digital PreservationMathematics10.3390/math91822799:18(2279)Online publication date: 16-Sep-2021
  • (2015)When should I make preservation copies of myself?International Journal on Digital Libraries10.1007/s00799-015-0155-116:3-4(183-205)Online publication date: 21-Jun-2015
  • (2014)When should I make preservation copies of myself?Proceedings of the 14th ACM/IEEE-CS Joint Conference on Digital Libraries10.5555/2740769.2740771(1-10)Online publication date: 8-Sep-2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
HT '10: Proceedings of the 21st ACM conference on Hypertext and hypermedia
June 2010
328 pages
ISBN:9781450300414
DOI:10.1145/1810617
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2010

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. resilience
  2. robustness
  3. small world

Qualifiers

  • Research-article

Conference

HT '10
Sponsor:
HT '10: 21st ACM Conference on Hypertext and Hypermedia
June 13 - 16, 2010
Ontario, Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 378 of 1,158 submissions, 33%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)Analysis of Nature-Inspired Algorithms for Long-Term Digital PreservationMathematics10.3390/math91822799:18(2279)Online publication date: 16-Sep-2021
  • (2015)When should I make preservation copies of myself?International Journal on Digital Libraries10.1007/s00799-015-0155-116:3-4(183-205)Online publication date: 21-Jun-2015
  • (2014)When should I make preservation copies of myself?Proceedings of the 14th ACM/IEEE-CS Joint Conference on Digital Libraries10.5555/2740769.2740771(1-10)Online publication date: 8-Sep-2014
  • (2014)When should i make preservation copies of myself?IEEE/ACM Joint Conference on Digital Libraries10.1109/JCDL.2014.6970143(1-10)Online publication date: Sep-2014

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media