소셜 네트워크를 통해 수집된 수많은 데이터들은 여러 분야에 중요한 자료로 활용되고 있으며, 소셜 네트워크상의 데이터들이 이용되면서 개인정보가 노출되는 프라이버시 문제가 발생하고 있다. 프라이버시 문제를 해결하기 위한 실용적인 방안으로 k-익명성, l -다양성 등의 개념과 이를 토대로 한 데이터 익명화 방법이 제안되어 있다. 데이터의 익명화에서는 원본데이터의 왜곡을 최소화하면서 프라이버시 보호를 극대화하는 것이 목적이다. 이러한 목적을 달성하기 위해 익명화 비용을 측정하기 위한 합리적인 방법이 필요하다. 본 논문에서는 소셜 네트워크 그래프의 익명화 알고리즘 수행을 위해 필수적 요소인 익명화 비용을 합리적이고 실용적으로 측정하는 방법을 제안한다.