Motiverade av nyligen upptäckta integritetsattacker på sociala nätverk studerar vi problemet med anonymisering av den underliggande grafen av interaktioner i ett socialt nätverk. Vi kallar en graf (k, l)-anonym om för varje nod i grafen det finns minst k andra noder som delar minst l av sina grannar. Vi betraktar två kombinatoriska problem som uppstår till följd av denna uppfattning om anonymitet i grafer. Mer specifikt, med tanke på en ingång graf vi ber om det minsta antalet kanter som ska läggas till så att grafen blir (k, l)-anonym. Vi definierar två varianter av detta minimeringsproblem och studerar deras egenskaper. Vi visar att för vissa värden av k och l problemen är polynom-tid solvable, medan för andra de blir NP-hård. Tillnärmningsalgoritmer för de senare fallen ges också.
Feder m.fl. REF kallas en graf (k, l)-anonym om, för varje vertex i grafen, det finns minst k andra hörn som delar minst l av sina grannar.
Anonymizing Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}