{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T01:47:58Z","timestamp":1742953678665,"version":"3.40.3"},"publisher-location":"Cham","reference-count":45,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030314996"},{"type":"electronic","value":"9783030315009"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>\nDifferent types of data privacy techniques have been applied to graphs and social networks. They have been used under different assumptions on intruders\u2019 knowledge. i.e., different assumptions on what can lead to disclosure. The analysis of different methods is also led by how data protection techniques influence the analysis of the data. i.e., information loss or data utility.<\/jats:p>\n          <jats:p>One of the techniques proposed for graph is graph perturbation. Several algorithms have been proposed for this purpose. They proceed adding or removing edges, although some also consider adding and removing nodes.<\/jats:p>\n          <jats:p>In this paper we propose the study of these graph perturbation techniques from a different perspective. Following the model of standard database perturbation as noise addition, we propose to study graph perturbation as <jats:italic>noise graph addition<\/jats:italic>. We think that changing the perspective of graph sanitization in this direction will permit to study the properties of perturbed graphs in a more systematic\u00a0way.\n<\/jats:p>","DOI":"10.1007\/978-3-030-31500-9_8","type":"book-chapter","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T23:26:53Z","timestamp":1568935613000},"page":"121-137","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Graph Perturbation as Noise Graph Addition: A New Perspective for Graph Anonymization"],"prefix":"10.1007","author":[{"given":"Vicen\u00e7","family":"Torra","sequence":"first","affiliation":[]},{"given":"Juli\u00e1n","family":"Salas","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,9,20]]},"reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1080\/10586458.2001.10504428","volume":"10","author":"W Aiello","year":"2001","unstructured":"Aiello, W., Chung, F., Lu, L.: A random graph model for power law graphs. J. Exp. Math. 10, 53\u201366 (2001)","journal-title":"J. Exp. Math."},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1142\/S0218488512400284","volume":"20","author":"E Balsa","year":"2012","unstructured":"Balsa, E., Troncoso, C., D\u00edaz, C.: A metric to evaluate interaction obfuscation in online social networks. Int. J. Unc. Fuzz. Knowl.-Based Syst. 20, 877\u2013892 (2012)","journal-title":"Int. J. Unc. Fuzz. Knowl.-Based Syst."},{"key":"8_CR3","unstructured":"Bannink, T., van der Hofstad, R., Stegehuis, C.: Switch chain mixing times through triangle counts. arXiv:1711.06137 (2017)"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Bengoetxea, E.: Inexact graph matching using estimation of distribution algorithms, PhD Dissertation, Ecole Nationale Sup\u00e9rieure des T\u00e9l\u00e9communications, Paris (2002)","DOI":"10.1016\/S0031-3203(01)00232-1"},{"key":"8_CR5","volume-title":"Graphs and Hypergraphs","author":"C Berge","year":"1973","unstructured":"Berge, C.: Graphs and Hypergraphs. North-Holland, Netherlands (1973)"},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/j.ins.2014.02.035","volume":"275","author":"F Bonchi","year":"2014","unstructured":"Bonchi, F., Gionis, A., Tassa, T.: Identity obfuscation in graphs through the information theoretic lens. Inf. Sci. 275, 232\u2013256 (2014)","journal-title":"Inf. Sci."},{"key":"8_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/3-540-47804-3_8","volume-title":"Inference Control in Statistical Databases","author":"R Brand","year":"2002","unstructured":"Brand, R.: Microdata protection through noise addition. In: Domingo-Ferrer, J. (ed.) Inference Control in Statistical Databases. LNCS, vol. 2316, pp. 97\u2013116. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-47804-3_8"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-642-01718-6_4","volume-title":"Privacy, Security, and Trust in KDD","author":"Alina Campan","year":"2009","unstructured":"Campan, A., Truta, T.M.: Privacy, security, and trust in KDD, pp. 33\u201354 (2009)"},{"issue":"3","key":"8_CR9","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s10462-016-9484-8","volume":"47","author":"J Casas-Roma","year":"2017","unstructured":"Casas-Roma, J., Herrera-Joancomart\u00ed, J., Torra, V.: A survey of graph-modification techniques for privacy-preserving on networks. Artif. Intell. Rev. 47(3), 341\u2013366 (2017)","journal-title":"Artif. Intell. Rev."},{"key":"8_CR10","unstructured":"D\u2019Acquisto, G., Domingo-Ferrer, J., Kikiras, P., Torra, V., de Montjoye, Y.-A., Bourka, A.: Privacy by design in big data: an overview of privacy enhancing technologies in the era of big data analytics, ENISA Report (2015)"},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"027","DOI":"10.1103\/PhysRevE.72.027104","volume":"72","author":"J Duch","year":"2005","unstructured":"Duch, J., Arenas, A.: Community identification using extremal optimization. Phys. Rev. E 72, 027\u2013104 (2005)","journal-title":"Phys. Rev. E"},{"issue":"3","key":"8_CR12","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1214\/ss\/1177011681","volume":"6","author":"GT Duncan","year":"1991","unstructured":"Duncan, G.T., Pearson, R.W.: Enhancing access to microdata while protecting confidentiality: prospects for the future. Statist. Sci. 6(3), 219\u2013232 (1991)","journal-title":"Statist. Sci."},{"issue":"5","key":"8_CR13","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1016\/j.patrec.2008.12.014","volume":"30","author":"M Ferrer","year":"2009","unstructured":"Ferrer, M., Valveny, E., Serratosa, F.: Median graph: a new exact algorithm using a distance based on the maximum common subgraph. Pattern Recogn. Lett. 30(5), 579\u2013588 (2009)","journal-title":"Pattern Recogn. Lett."},{"issue":"3","key":"8_CR14","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1297332.1297338","volume":"1","author":"A Gionis","year":"2007","unstructured":"Gionis, A., Mannila, H., Mielik\u00e4inen, T., Tsaparas, P.: Assessing data mining results via swap randomization. ACM Trans. Knowl. Discov. Data 1(3), 14 (2007)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"issue":"12","key":"8_CR15","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Nat. Acad. Sci. US Am. 99(12), 7821\u20137826 (2002)","journal-title":"Proc. Nat. Acad. Sci. US Am."},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1142\/S0219525903001067","volume":"6","author":"P Gleiser","year":"2003","unstructured":"Gleiser, P., Danon, L.: Community structure in jazz. Adv. Complex Syst. 6, 565 (2003)","journal-title":"Adv. Complex Syst."},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"065103(R)","DOI":"10.1103\/PhysRevE.68.065103","volume":"68","author":"R Guimera","year":"2003","unstructured":"Guimera, R., Danon, L., Diaz-Guilera, A., Giralt, F., Arenas, A.: Self-similar community structure in a network of human interaction. Phys. Rev. E 68, 065103(R) (2003)","journal-title":"Phys. Rev. E"},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/0110037","volume":"10","author":"SL Hakimi","year":"1962","unstructured":"Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph I. J. Soc. Ind. Appl. Math. 10, 496\u2013506 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"8_CR19","doi-asserted-by":"crossref","first-page":"477","DOI":"10.21136\/CPM.1955.108220","volume":"80","author":"V Havel","year":"1955","unstructured":"Havel, V.: A remark on the existence of finite graphs. \u010casopis Pro P\u011bstov\u00e1n\u00ed Matematiky (in Czech) 80, 477\u2013480 (1955)","journal-title":"\u010casopis Pro P\u011bstov\u00e1n\u00ed Matematiky (in Czech)"},{"key":"8_CR20","unstructured":"Hay, M., Miklau, G., Jensen, D., Weis, P., Srivastava, S.: Anonymizing social networks, Technical report No. 07-19, Computer Science Department, University of Massachusetts Amherst, UMass Amherst (2007)"},{"issue":"1","key":"8_CR21","doi-asserted-by":"publisher","first-page":"102","DOI":"10.14778\/1453856.1453873","volume":"1","author":"M Hay","year":"2008","unstructured":"Hay, M., Miklau, G., Jensen, D., Towsley, D., Weis, P.: Resisting structural reidentification in anonymized social networks. Proc. VLDB Endow. 1(1), 102\u2013114 (2008)","journal-title":"Proc. VLDB Endow."},{"key":"8_CR22","first-page":"101","volume-title":"Random Graphs","author":"M Jerrum","year":"1992","unstructured":"Jerrum, M., McKay, B.D., Sinclair, A.: When is a graphical sequence stable? In: Frieze, A., Luczak, T. (eds.) Random Graphs, vol. 2, pp. 101\u2013115. Wiley-Interscience, Hoboken (1992)"},{"key":"8_CR23","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0304-3975(90)90164-D","volume":"73","author":"M Jerrum","year":"1990","unstructured":"Jerrum, M., Sinclair, A.: Fast uniform generation of regular graphs. Theoret. Comput. Sci. 73, 91\u2013100 (1990)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"8_CR24","doi-asserted-by":"publisher","first-page":"28:1","DOI":"10.1145\/2824443","volume":"10","author":"D Koutra","year":"2016","unstructured":"Koutra, D., Shah, N., Vogelstein, J.T., Gallagher, B., Faloutsos, C.: Deltacon: principled massive-graph similarity function with attribution. ACM Trans. Knowl. Discov. Data 10(3), 28:1\u201328:43 (2016)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"issue":"1","key":"8_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1217299.1217301","volume":"1","author":"J Leskovec","year":"2007","unstructured":"Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1(1), 1\u201340 (2007)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"issue":"1","key":"8_CR26","doi-asserted-by":"crossref","first-page":"16","DOI":"10.37236\/3028","volume":"20","author":"I Mikl\u00f3s","year":"2013","unstructured":"Mikl\u00f3s, I., Erd\u00f6s, P.L., Soukup, L.: Towards random uniform sampling of bipartite graphs with given degree sequence. Electr. J. Comb. 20(1), 16 (2013)","journal-title":"Electr. J. Comb."},{"key":"8_CR27","unstructured":"Milo, R., Kashtan, N., Itzkovitz, S., Newman, M.E.J., Alon, U.: On the uniform generation of random graphs with prescribed degree sequences. arXiv:cond-mat\/0312028v2 (2004)"},{"issue":"03","key":"8_CR28","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1142\/S0218488516500215","volume":"24","author":"DF Nettleton","year":"2016","unstructured":"Nettleton, D.F., Salas, J.: Approximate matching of neighborhood subgraphs - an ordered string graph levenshtein method. Int. J. Unc. Fuzz. Knowl.-Based Syst. 24(03), 411\u2013431 (2016)","journal-title":"Int. J. Unc. Fuzz. Knowl.-Based Syst."},{"key":"8_CR29","unstructured":"Nickel, C.L.M.: Random dot product graphs: a model for social networks, PhD. dissertation, Maryland (2006)"},{"issue":"03","key":"8_CR30","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1142\/S0218001404003277","volume":"18","author":"A Robles-Kelly","year":"2004","unstructured":"Robles-Kelly, A., Hancock, E.R.: String edit distance, random walks and graph matching. Int. J. Pattern Recogn. Artif. Intell. 18(03), 315\u2013327 (2004)","journal-title":"Int. J. Pattern Recogn. Artif. Intell."},{"issue":"2","key":"8_CR31","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s10207-018-0409-1","volume":"18","author":"M Ros-Mart\u00edn","year":"2019","unstructured":"Ros-Mart\u00edn, M., Salas, J., Casas-Roma, J.: Scalable non-deterministic clustering-based k-anonymization for rich networks. Int. J. Inf. Secur. 18(2), 219\u2013238 (2019)","journal-title":"Int. J. Inf. Secur."},{"key":"8_CR32","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.dam.2015.03.005","volume":"188","author":"J Salas","year":"2015","unstructured":"Salas, J., Torra, V.: Graphic sequences, distances and k-degree anonymity. Discrete Appl. Math. 188, 25\u201331 (2015)","journal-title":"Discrete Appl. Math."},{"key":"8_CR33","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.dam.2016.01.025","volume":"206","author":"J Salas","year":"2016","unstructured":"Salas, J., Torra, V.: Improving the characterization of p-stability for applications in network privacy. Discrete Appl. Math. 206, 109\u2013114 (2016)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"8_CR34","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1109\/TSMC.1983.6313167","volume":"SMC\u201313","author":"A Sanfeliu","year":"1983","unstructured":"Sanfeliu, A., Fu, K.: A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cybern. SMC\u201313(3), 353\u2013362 (1983)","journal-title":"IEEE Trans. Syst. Man Cybern."},{"issue":"10","key":"8_CR35","doi-asserted-by":"publisher","first-page":"1657","DOI":"10.1007\/s00500-012-0850-4","volume":"16","author":"K Stokes","year":"2012","unstructured":"Stokes, K., Torra, V.: Reidentification and k-anonymity: a model for disclosure risk in graphs. Soft Comput. 16(10), 1657\u20131670 (2012)","journal-title":"Soft Comput."},{"issue":"9","key":"8_CR36","doi-asserted-by":"publisher","first-page":"788","DOI":"10.14778\/2311906.2311907","volume":"5","author":"Z Sun","year":"2012","unstructured":"Sun, Z., Wang, H., Wang, H., Shao, B., Li, J.: Efficient subgraph matching on billion node graphs. Proc. VLDB Endow. 5(9), 788\u2013799 (2012)","journal-title":"Proc. VLDB Endow."},{"key":"8_CR37","doi-asserted-by":"crossref","unstructured":"Tian, Y., Patel, J.M.: Tale: a tool for approximate large graph matching. In: 2008 IEEE 24th International Conference on Data Engineering, pp. 963\u2013972, April (2008)","DOI":"10.1109\/ICDE.2008.4497505"},{"key":"8_CR38","series-title":"Studies in Big Data","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57358-8","volume-title":"Data Privacy: Foundations, New Developments and the Big Data Challenge","author":"V Torra","year":"2017","unstructured":"Torra, V.: Data Privacy: Foundations, New Developments and the Big Data Challenge. SBD, vol. 28. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57358-8"},{"issue":"12","key":"8_CR39","doi-asserted-by":"publisher","first-page":"2364","DOI":"10.1002\/int.22034","volume":"33","author":"V Torra","year":"2018","unstructured":"Torra, V., Jonsson, A., Navarro-Arribas, G., Salas, J.: Synthetic generation of spatial graphs. Int. J. Intell. Syst. 33(12), 2364\u20132378 (2018)","journal-title":"Int. J. Intell. Syst."},{"key":"8_CR40","series-title":"IFIP Advances in Information and Communication Technology","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-319-55783-0_2","volume-title":"Privacy and Identity Management. Facing up to Next Steps","author":"V Torra","year":"2016","unstructured":"Torra, V., Navarro-Arribas, G.: Big data privacy and anonymization. In: Lehmann, A., Whitehouse, D., Fischer-H\u00fcbner, S., Fritsch, L., Raab, C. (eds.) Privacy and Identity 2016. IAICT, vol. 498, pp. 15\u201326. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-55783-0_2"},{"issue":"2","key":"8_CR41","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/j.patcog.2014.01.002","volume":"48","author":"M Vento","year":"2015","unstructured":"Vento, M.: A long trip in the charming world of graphs for pattern recognition. Pattern Recogn. 48(2), 291\u2013301 (2015)","journal-title":"Pattern Recogn."},{"key":"8_CR42","unstructured":"Yan, X., Han, J.: gspan: graph-based substructure pattern mining. In: 2002 IEEE International Conference on Data Mining, 2002. Proceedings., pp. 721\u2013724, December (2002)"},{"key":"8_CR43","doi-asserted-by":"crossref","unstructured":"Ying, X., Pan, K., Wu, X., Guo, L.: Comparisons of randomization and k-degree anonymization schemes for privacy preserving social network publishing. In: Proceedings of the 3rd Workshop on Social Network Mining and Analysis, ser. SNA-KDD 2009, pp. 10:1\u201310:10. New York, NY, USA, ACM (2009)","DOI":"10.1145\/1731011.1731021"},{"key":"8_CR44","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1086\/jar.33.4.3629752","volume":"33","author":"WW Zachary","year":"1977","unstructured":"Zachary, W.W.: An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33, 452\u2013473 (1977)","journal-title":"J. Anthropol. Res."},{"key":"8_CR45","unstructured":"http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/pajek\/data\/gphs.htm"}],"container-title":["Lecture Notes in Computer Science","Data Privacy Management, Cryptocurrencies and Blockchain Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-31500-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T17:02:59Z","timestamp":1737133379000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-31500-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030314996","9783030315009"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-31500-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"20 September 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DPM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Data Privacy Management","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 September 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 September 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dpm2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/esorics2019.uni.lu\/workshops\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}