Låt G = (V, E) vara en enkel ansluten graf och S = {w 1, · ·, w t }  till V en beställd delmängd av hörn. Den metriska representationen av en vertex u  ska V med avseende på S är t-vektorn r(u-S) u, v) representerar längden av en kortaste u − v sökväg i G. Den uppsättning S kallas en upplösning uppsättning för G om r(u-S) = r(v-S) innebär u = v för varje u, v -V. Den minsta kardinaliteten i en upplösning uppsättning är den metriska dimensionen av G. I denna artikel föreslår vi, så vitt vi vet, ett nytt problem i diagramteori som liknar den ovan nämnda metriska dimensionen problem. Vi kallar S en k-antiresolving set om k är det största positiva heltal sådan att för varje vertex v  på V − S det finns andra k − 1 olika hörn v 1, · · · ·, v k-1 V − S med r(v-S) = r(v 1 -S) = · · · = r(v k-1 -S), dvs, v och v 1, · · ·, v k-1 har samma metriska representation med avseende på S. K-metrisk antidimension av G är den minsta kardinaliteten bland alla k-antiresolving uppsättningar för G. I denna artikel, introducerar vi en ny integritet åtgärd, namngiven (k, )-anonymitet och baserat på k-metrisk antidimensionsion problem, som syftar till att utvärdera motståndet av sociala grafer mot aktiva attacker. Vi föreslår därför en sannförståelig algoritm för beräkning av den k-metriska antidimensionen av slumpmässiga grafer. Framgångsfrekvensen för vår algoritm, enligt empiriska resultat, är över 80% och 90% när man letar efter en k-antiresolving bas respektive en k-antiresolving set. Vi undersöker också de teoretiska egenskaperna hos k-antiresolving-seten och den k-metriska antidimensionen av grafer. I synnerhet fokuserar vi på stigar, cykler, kompletta bipartite grafer och träd.
Såvitt vi vet har (k,)-anonymitet REF hittills varit den enda privata egendomen som är skräddarsydd för att mäta motståndet från sociala grafer mot aktiva attacker.
k-Metric Antidimension: a Privacy Measure for Social Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}