TY - JOUR
T1 - Shortest paths anonymization on weighted graphs
AU - Wang, Shyue Liang
AU - Tsai, Yu Chuan
AU - Kao, Hung Yu
AU - Ting, I. Hsien
AU - Hong, Tzung Pei
N1 - Funding Information:
This work was supported in part by the National Science Council, Taiwan, under grant NSC-100-2221-E-390-030.
PY - 2013/2
Y1 - 2013/2
N2 - Due to the proliferation of online social networking, a large number of personal data are publicly available. As such, personal attacks, reputational, financial, or family losses might occur once this personal and sensitive information falls into the hands of malicious hackers. Research on Privacy-Preserving Network Publishing has attracted much attention in recent years. But most work focus on node de-identification and link protection. In academic social networks, business transaction networks, and transportation networks, etc, node identities and link structures are public knowledge but weights and shortest paths are sensitive. In this work, we study the problem of k-anonymous path privacy. A published network graph with k-anonymous path privacy has at least k indistinguishable shortest paths between the source and destination vertices [21]. In order to achieve such privacy, three different strategies of modification on edge weights of directed graphs are proposed. Numerical comparisons show that weight-proportional-based strategy is more efficient than PageRank-based and degree-based strategies. In addition, it is also more efficient and causes less information loss than running on un-directed graphs.
AB - Due to the proliferation of online social networking, a large number of personal data are publicly available. As such, personal attacks, reputational, financial, or family losses might occur once this personal and sensitive information falls into the hands of malicious hackers. Research on Privacy-Preserving Network Publishing has attracted much attention in recent years. But most work focus on node de-identification and link protection. In academic social networks, business transaction networks, and transportation networks, etc, node identities and link structures are public knowledge but weights and shortest paths are sensitive. In this work, we study the problem of k-anonymous path privacy. A published network graph with k-anonymous path privacy has at least k indistinguishable shortest paths between the source and destination vertices [21]. In order to achieve such privacy, three different strategies of modification on edge weights of directed graphs are proposed. Numerical comparisons show that weight-proportional-based strategy is more efficient than PageRank-based and degree-based strategies. In addition, it is also more efficient and causes less information loss than running on un-directed graphs.
UR - http://www.scopus.com/inward/record.url?scp=84878455050&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84878455050&partnerID=8YFLogxK
U2 - 10.1142/S0218194013400056
DO - 10.1142/S0218194013400056
M3 - Article
AN - SCOPUS:84878455050
SN - 0218-1940
VL - 23
SP - 65
EP - 79
JO - International Journal of Software Engineering and Knowledge Engineering
JF - International Journal of Software Engineering and Knowledge Engineering
IS - 1
ER -