作者：gufe_hfding
文章目录
论文概况
今天要分享的是来自伊朗的论文，标题为：A graph modification approach for k‑anonymity in social networks using the genetic algorithm，主要对图进行基于演化算法的k-度匿名。
Sara Rajabzadeh, Pedram Shahsafi, Mostafa Khoramnejadi:
A graph modification approach for k-anonymity in social networks using the genetic algorithm. Soc. Netw. Anal. Min. 10(1): 38 (2020)
当然，伊朗是个大国，但在美国经济*的状况下仍然有大量的人员在做科研，也是挺不容易的。这篇论文的作者来自伊朗最富盛名，也是建立最早的两个大学，K. N. Toosi University of Technology 和Amirkabir University of Technology，都是理工类学校，据*的信息这两个学校都招收考分最高的学生，也比得上我们的清华北大了。
不过这篇论文是这个研究团队的第一篇关于图隐私的论文，应当是值得鼓励的，也比较钦佩在困难环境下仍然做科研的那些研究人员。
论文主要创新点
这篇论文最大的优势在于考虑了k-度匿名与图结构间的关系，在匿名算法加边的时候不是随便去加，而是先通过社团检测算法把图划分为若干个社团，在社团内部添加用来达到k-度的匿名边。加边的时候，优化算法不是用确定性算法，而是通过演化算法多次迭代，找到比较优的加边位置。用演化算法等一些非确定性算法可以大大提高效率，这是一个普遍的做法，这篇论文把不同的社团当做一个族群，每个顶点需要加边的数量当做基因，通过变异和遗传迭代，最终找出相对最优解。最终，实现了k-度匿名，对图的结构改变也不大，多个图的性质指标测试证实了这点。
论文启示
怎么说的，没有看到特别吸引人的创新点和结果优势。只能说做了一个有意义的工作，但工作借鉴意义没有那么大，还需要努力咯。