日益成長的雲端技術使得雲端應用愈趨成熟，圖形是目前許多資訊處理與應用極為重要並倚賴的資料結構，因此使用者與企業在運用雲端之同時極有可能須將圖形的結構資料寄存至雲端，除善用其儲存系統儲存大量圖形資料，並借重其計算能力做有效率的處理，但圖形內含有許多重要且敏感的資訊，因此在上傳圖形結構前必須轉換成能夠隱藏資訊的外儲圖(outsource graph)以確保使用者的隱私。本論文提出方法將圖形轉換成k-isomorphism圖，該演算法酌量加入虛擬假節點(dummy vertex)與虛擬假邊(dummy edge)以及多個不同面向的策略挑選出k個互相同構的子圖，藉以將原始圖轉換成外儲圖；外儲圖即為寄存至雲端的實際圖形；雲端供應商雖可在此外儲圖上協助使用者進行各項運算與應用，但卻與第三者一樣無法了解或還原使用者的原始圖，達到保護圖形隱私之目的，本論文方法滿足k-security安全性，亦可以有效抵擋neighborhood attack、node identifier attack、structural attack與reconstruction attack。

The growing popularity of cloud technology makes the application of cloud become maturer. When data structure of graph becomes more important for processing data and application, user and companies always store structure of graph in cloud. They use data structure of graph by cloud’s large storage and efficient computation in cloud. But graphs have many important and sensitive information, those must transform to outsource graph for anonymity and ensure user’s privacy. This thesis designs an algorithm to add dummy vertices and dummy edges in the right time, and use some different strategies to select k subgraphs which are isomorphic to each other. The proposed algorithm transforms origin graphs to k-isomorphism graphs which are outsource graphs. Users store those outsource graphs in cloud. The suppliers of cloud provide some service to the user based on those outsource graphs, but the suppliers can’t know the connection of any two nodes in users’ original graphs.  The graphs’ privacy is protected. The proposed algorithm satisfy k-security, and also resist neighborhood attack, node identifier attack, structural attack and reconstruction attack.

目錄
第一章 前言	1
第二章 相關研究	4
2.1 相關技術與安全性定義	4
2.2 Cheng等學者方法簡介	6
2.2.1 Frequency Based Graph Synthesis演算法	9
2.2.2 Anonymize-PAG 演算法	10
2.2.3 i-Graph Formation 演算法	11
2.3 分析與討論Cheng等學者之方法	13
第三章 論文方法	15
3.1 本論文概要	16
3.2 演算法D：圖形的分析與匿名	19
3.3 演算法E：轉換處理子圖	23
3.4 演算法F：i-graph的構成	26
3.5 演算法G：i-graph的構成	28
第四章 討論與分析	30
4.1 Neighborhood Attack	30
4.2 Node Identifier Attack	31
4.3 Structural Attack	31
4.4 Reconstruction Attack	31
4.5 功能比較	32
第五章 結論與未來研究方向	33
參考文獻	34
Appendix	35

圖目錄
圖2-1(a)：給定之原始圖G	6
圖2-1(b)：由圖2-1(a)轉換後的Gk	6
圖2-2(a)：原始圖G	8
圖2-2(b)：特定之子圖g	8
圖2-2(c)：圖G存在的Embedding	8
圖2-2(d)：圖形G只存在的VDEmbed	8
圖3-1：EM表格對應之範例原始圖	17
圖3-2：EM表格對應之PGraph	17
圖3-3：本論文方法演算法之主體架構圖	18
圖4-1：neighborhood attack範例圖	30

表目錄
表2-1：符號定義	4
表2-2：VM表格範例	8
表3-1：EM表格範例	17
表3-2：CNT表格範例	17

[1]	J. Gao, J. Yu, R. Jin, J. Zhou, T. Wang, and D. Yang, Neighborhood privacy protected shortest distance computing in cloud, in Proc. of ACM COMAD, 2011.
[2]	B. Zhou and J. Pei. Preserving privacy in social networks against neighborhood attacks. In ICDE, pp. 506–515, 2008.
[3]	K. Liu and E. Terzi. Towards identity anonymization on graphs. In SIGMOD, 2008.
[4]	L. Zou, L. Chen, and M. T. Ozsu. K-automorphism: A general framework for privacy preserving network publication. In VLDB, 2009.
[5]	J. Cheng, A. W.-C. Fu, and J. Liu. K-isomorphism: privacy preserving network publication against structural attacks. In SIGMOD, pp. 459–470, 2010.
[6]	M. Hay, G. Miklau, D. Jensen, D. F. Towsley and P. Weis. Resisting structural re-identification in anonymized social networks. PVLDB 1(1), pp.102–114, 2008.
[7]	M. Hay, G. Miklau, D. Jensen, P. Weis, and S. Srivastava. Anonymizing social networks. Technical report No. 07-19, Computer Science Department, University of Massachusetts Amherst, 2007.
[8]	A. Campan and T. M. Truta. A clustering approach for data and structural anonymity in social networks. In PinKDD, 2008.
[9]	E. Zheleva and L. Getoor. Preserving the privacy of sensitive relationships in graph data. In PinKDD, pp. 153–171, 2007.
[10]	X. Ying and X. Wu. Randomizing social networks: a spectrum preserving approach. In SDM, pp. 739–750, 2008.
[11]	J. Gao, J. X. Yu, R. Jin, J. Zhou, T. Wang, D. Yang. Outsourcing shortest distance computing with privacy protection. In VLDB Journal, 2013.
[12]	P. Samarati. Protecting respondents’ identities in microdata release. IEEE Transactions on Knowledge and Data Engineering (TKDE) 13(6), pp. 1010–1027, 2001.
[13]	P. Samarati. Protecting respondents’ identities in microdata release. IEEE Transactions on Knowledge and Data Engineering (TKDE) 13(6), 1010–1027, 2001.
[14]	L. Sweeney. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 10(5), pp. 557–570, 2002.