# A Personalizedα,β,l,k-Anonymity Model of Social Network for Protecting Privacy

Authors: Xiangmin Ren; Dexun Jiang
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

By mining the data published on social network, we can discover the hidden value of information including the privacy of individuals and organizations. Protecting privacy of individuals and organizations on social network has become the focus of more and more researchers. Based on the actual privacy protection need of edge sensitive attribute and vertexes sensitive attribute, we propose a new personalizedα,β,l,k-anonymity technology of privacy preserving to reduce distortion extent of the data in the privacy processing of data of social network. Experimental results of personalized α,β,l,k-anonymity algorithm show that d-neighborhood attack of graph, background knowledge attack, and homogeneity attack can be prevented effectively by using anonymous vertexes and edges, as well as the influence matrix based on background knowledge. The diversity of vertex sensitive attribute can be achieved. Personalized protecting privacy requirements can be met by using such parameter as α,β,l,k.


---

## Body

## 1. Introduction

Data publishing of social network is very important for scientific research, commercial purpose, countries, and so on, but social network data includes privacy information and sensitive relations, which can be leaked by publishing directly. How to protect individual privacy, and make the publishing data or graph useful at the same time, has become very important problem of social network data publishing. One of the most important principle is that individual can decide his own privacy whether be published or not, that is to say individual has different privacy protection needs.Anonymity techniques for data publishing have been used in the relational data for a long time, and make great progress in relational database area, includingk-anonymity, l-diversity, generalization, and so forth [1, 2]. Can we apply the same anonymous techniques that apply to relational data to social networks? Social network data contains more information than relational data because network data contains vertexes (nodes), edges, relationships between nodes, and various metric features of the graph. Some researchers want to use these technologies on data publishing of social network [3]. So the structure and evaluation of social network method were proposed in paper [4], and the categories of attack in social network can be found in paper [5]. Graph modification [6], graph partitioning [7], graph isomorphism [8], clustering [9], attribute generalization [10], and so on were applied to data publishing of social network, and then more and more anonymous technologies of social networks appear in many academic papers.Actually, a graph structure is necessary to represent the network vertexes relations rather than a two dimensional representation in relational database [11], degree denotes the relationship between two vertexes, high degrees mean the relationships are more closer among the vertexes, and there are only a small part of vertexes which degrees are high, degrees of most of vertexes are low in big social network. So a limited fraction of vertexes with high degrees bring a lot of data loss and computation cost when using unified anonymity methods and the same privacy protection level [12].Personalized privacy protection based on data table was proposed firstly by Xiao and Tao in 2006 [13]. They used individual guarding node to set level of self-sensitive attribute and did not set the same anonymity level for all individuals, but rather anonymity according to setting guarding node.Ever since then, more and more researcher paid more attention to personalized anonymity of data publishing and made modest progress. During the research process of social network privacy protection, because data of social network is more complex than traditional data table, most of social network research used unified anonymity methods and the same privacy protection level. For example, user can create their basic information, Web albums, Web logs, the lists of friends, and so on. But Facebook, Twitter, Wechat, and voov meeting, they were able to decide those information whether can be accessed and viewed by others according to their own privacy level, consequently achieved purpose of preserving privacy to some extent.The data in social network is more complex than two-dimensional data table in relational database. Privacy protection in social network can be summarized as vertex protection, edge protection, and sensitive attribute protection. Vertex protection is to prevent an attacker from identifying a vertex in an anonymous publishing graph with a high probability. Edge protection is to prevent an attacker from identifying an edge in an anonymous publishing graph with a high probability. Attribute protection is to prevent the attacker from getting vertexes or sensitive attributes of edges with a high probability. We cannot use anonymity methods and technologies, which used into traditional two dimensional data table, into social network directly, and users have personalized protecting privacy requirements (vertex protection, edge protection, and sensitive attribute protection) in the real social network such as the users of Facebook, Twitter, and Wechat, so it has the very high research value that personalized privacy protection methods are used into social network data publishing [14].


## 2. Problem Definition

### 2.1. Related Concepts

Definition 1.k-Anonymity.
RTA1,⋯,An is a table and QIRT is quasi-identifier in RT. RT is said to satisfy k-anonymity if and only if each sequence of values in RTQIRT emerge k occurrences at least in RTQIRT [15].Table1 is said to satisfy k-anonymity, QIRT includes nation, birthday, gender, ZIP, the sensitive attribute is disease, k=2. As can be seen from Table 1, t1QI=t2QI, t3QI=t4QI, t5QI=t6QI=t7QI.Definition 2.k-Degree anonymity.
A social network graphGV;E is said to satisfy k-degree anonymity, if each vertex (node) has k−1 other vertexes at least, and these vertex’s degree are same in the social network graph. The variable V represents vertex amounts, and E represents edge amounts between vertexes [16, 17].Table 1
Example of 2-anonymity,QI=Nation,Birthday,Gender,ZIP.
No.NationBirthdayGenderZIPSalary1Yellow1995F26118∗90002Yellow1995F26118∗50003Yellow1994M26112∗270004Yellow1994M26112∗100005Brown1993F26113∗75006Brown1993F26113∗300007Brown1993F26113∗9500K-degree anonymity can prevent the inference attack by the adversary with background knowledge about vertex degree. In Figure 1, degree collection is d=4,3,2,4,3,3,2,3,2 in primal social network graph (a), so anonymity social network graph (b) satisfies 2-degree anonymity in Figure 1.Definition 3. Graph isomorphism.
For graphs:G1=V1,E1 and G2=V2,E2 where ∣V1∣=∣V2∣, if there is a bijection h between V1 and V2 satisfies ∀u,v∈E1, if and only if ∃hu,hv∈E2, G1, and G2 are graph isomorphism, represented as G1≅G2. Vi represents vertex (node) numbers, and Ei represents edge numbers between vertexes.Figure 1
2-Anonymity publishing in a social network.
(a)(b)(c)For example, when we delete the node information of (a) and (b) in Figure1, (a) and (b) are isomorphic [18].Definition 4.k-Isomorphism.
For a graphG=V,E, whose k sub-graphs are g1,g2,⋯,gk, if gil≤i≤k satisfies: (1) Ui=1kgi=G; (2) gi∩gj=Φ,i≠j (3) giandgji≠j are isomorphism, then, the graph G is k-isomorphism.Definition 5.k-Isomorphism vertex group.
Given ak-isomorphism publishing graph Gp=VP,EP=g1,g2,⋯gk,∀v1∈Gp,v1∈g1, then, there exist k−1 vertexes vi∈gii=2,⋯,k are isomorphic to v1, the vertex set consists the vertex vi and the k−1vi∈i=2,⋯,k is k-isomorphism vertexes group, which is denoted as VCS, VCS=k. Each VCS includes k vertexes and there are VP/kVCS in the k-isomorphism graph Gp.Definition 6.k-Isomorphism edge group.
Given ak-isomorphism publishing graph Gp=VP,EP=g1,g2,⋯,gk, ∀e1∈g1, then there exist k−1 edges ei∈gii=2,⋯,k is isomorphic to e1, the vertex set consists the vertex e1, and the k−1ei∈gii=2,⋯,k is k-isomorphism edges group, which is denoted as ECS, ECS=k. Each VCS includes k edges and there are EP/kECS in the k-isomorphism graph Gp.Definition 7. Social network graph.
Given a social network graph:G=V,E, wherein vertex set V denotes the social individuals, and the edge set E denotes the relationships among the social individuals. Each vertex and edge has its identify and attribute which includes
(a)
Identifier attribute (ID) of vertex asviviID(b)
Quasi-identifier attribute (QI) of vertexvi as QI=viN1,⋯,viNs,viC1,⋯,viCt(c)
Sensitive attribute (SA) of vertexvi as SA=viS1(d)
Quasi-identifier attribute (QI) of edgeei as QI=ejN1,⋯,ejNp,ejC1,⋯,ejCq(e)
Sensitive attribute (SA) of edgeei as SA=ejS1(f)
Other attributes (OA)Attribute (QI) of edge denotes by vector pair (viID,vjID), the total number of vertexes N=V, N denotes QI of numeric attribute, C denotes QI of character attribute, s, t, p, and q denote the amount of QI, respectively. For example, Figure 1 is an example of friendship social network, each vertex is a customer, and each edge denotes relationship between two vertexes. Table 2 is primal data of each vertex in Figure 1(a). Table 3 is edge table, Eid denotes the sequence number of edge, Vid1 and Vid2 denote the sequence number of vertex of Figure 1(b), and weighted relationship denotes the relationship between Vid1 and Vid2 of Figure 1(c). Table 4 is another relational data table of a vertex of Figure 1(a).Table 2
The vertex table.
VidNameAgeGenderZIPSalary1Kya25F26118690002John25M26118550003Mira26F261101270004Maci26F261131100005Cathy27F26113175006Kurt27M261124300007Sage27F26118695008Rain37M261185280009Toni35M26112422000Table 3
The edge table.
EidVid1Vid2Weighted relationship11212143323242415252635373728462956110591117811279313891Table 4
Table of primal personal health information.
NameAgeGenderZIPDiseaseKya25F261186ColdJohn25M261185HypertensionMira26F261101AIDSMaci26F261131ColdCathy27F261131CancerKurt27M261124ObesitySage27F261186PneumoniaRain37M261185DiabetesToni35M261124Short breath


### 2.2. Sensitive Degree of Friend Relationship (SA) of Vertex and Edge

#### 2.2.1. Sensitive Degree of Friend Relationship (SA) of Vertex

We use the influence matrix to represent the level of influence of vertex-sensitive attributes [19, 20]. We can use the influence matrix to meet the requirements of personalized privacy protection of users.tij: the influence degree of NO. j sensitive attribute generated by NO. i vertex.bi: the weightiness of sensitive attribute value of NO. i vertex.Influence matrixVertexm is with m rows, n+1 columns, m represents vertex amount, n represents QI attribute amount, so it can be described as
(1)Vertexm=tijbim×n+1QI1QI2QI3⋯QInt11t12t13⋯t1n⋯⋯⋯⋯⋯tm−11tm−12tm−13⋯tm−1ntm1tm2tm3⋯tmnSb1⋯bm−1bm.Thetij, bi values come from experts or experience value. For example, the weightiness of QI in Table 4 can be divided into 5 grades, 1, 0.8, 0.4, 0.1, and 0, and the weightiness of S in Table 4 can be divided into 5 grades too, 0.10, 0.60, 0.70, 0.80, and 0.90. The cold is general disease, and disease weightiness value can use 0.1. Common cold (influenza) may have the character of a regional outbreak, and we define the weight value of the ZIP as 0.8. Common cold may also have a little bit to do with gender, and we define the weight value of gender as 0.1. Then, we define the disease weight values of obesity, short breath, hypertension, diabetes, pneumonia, cancer, and AIDS as 0.12, 0.31, 0.5, 0.6, 0.7, 0.91, and 0.92, respectively. The influence matrix is as follows according to Table 4.
(2)Vertexm=tijbi9×5+1NationOccupationBirthdayGenderZIP0000.10.8⋯⋯⋯⋯⋯00.10.40000.1000Disease0.1⋯0.60.31.


#### 2.2.2. Sensitive Degree of Friend Relationship (SA) of Edge

We described relationships of simple friend, good friend, and sweetheart friend (boyfriend or girlfriend) among the vertexes in Figure1 of friend relationship graph. Graph (c) of Figure 1 is an example of friend relationship graph, “1” represents simple friend relationship between two vertexes, “2” represents good friend relationship between two vertexes, “3” represents sweetheart relationship between two vertexes, and “0” represents no relationship between two vertexes. Usually, if sweetheart friend includes gay or lesbian relationship, most of people do not want others to know that he is gay or she is lesbian, so different people have different sensitive degree about friend relationships, so we must meet the needs of personalized privacy protection according to the practical application.


### 2.3.αd,k-Anonymity Graph

In order to make it impossible for an attacker to infer the real relationship between targeted individuals and corresponding vertexes with a probability,k-anonymity concept in data tables and the new concept of αd,k-anonymity are introduced.Definition 8.αd,k-Anonymity of the vertex.
Undirected graphG=V,E, the graph Gp=Vp,Ep is as its anonymous publishing graph, if a vertex v∈V, there are at least k−1 vertexes u1,u2,⋯,uk−1∈Vp in Gp, which makes Neighbordv≅Neighbordui and v≠ui, wherein, i=1,2,⋯k−1, thus, the vertex v is d,k-anonymity, and the vertex v is αd,k-anonymity according to α, α is the weight of relationships (edge weight) of d- neighborhood of vertex v.
For example, in Figures1, α=1,2,3 of vertex F (sage), and α=1,2,3 of vertex H (Maci), so vertex F and vertex H satisfy α1,2-anonymity.Definition 9.αd,k-Anonymity of the graph.
Undirected graphG=V,E, the graph Gp=Vp,Ep is as its anonymous publishing graph. If any vertex v∈V is d,k-anonymity, thus, the graph Gp is d,k-anonymity, if any vertex v∈V is αd,k-anonymity, thus, the graph Gp is αd,k-anonymity.Definition 10. Individual information leakage.
Suppose graphGp is the anonymity publishing graph of social network graph G, when the relative sensitive coefficient k and l satisfy one of the following four conditions, then, there exists individual information leakage. Otherwise, if the graph Gp can ensure that any of the following circumstances are not going to happen, the anonymity publishing graph Gp is regarded as secure. If the graph Gp can ensure the following circumstance (1) and (2) will not happen, then, the anonymity publishing graph Gp is k-secure [21].
(1)
Vertex Leakage. The probability of ascertaining the corresponding relationship between the vertex in the graph Gp and the target individual A in the primal graph G is greater than 1/k(2)
Edge Leakage. The probability of ascertaining the corresponding relationship between the edge in the graph Gp and the edge in the primal graph G is greater than 1/k(3)
Leakage of Vertex Sensitive Information. The probability of ascertaining the sensitive information of target individual A in the primal graph G is greater than 1/l(4)
Leakage of Edge Sensitive Information. The probability of ascertaining the sensitive information of the edge in the primal graph G is greater than 1/l


### 2.4. Personalizedα,β,l,k-Anonymity

#### 2.4.1. Personalizedα,β,l,k-Anonymity Model

Personalizedα,β,l,k-anonymity satisfies the following conditions:
(1)
Personalizedα,β,l,k-anonymity satisfies αd,k-anonymity(2)
∀bi<β in matrix Vertexm, all vertexes in k-isomorphism vertexes group be supposed to be published directly. Otherwise should be satisfied condition (3) and condition (4)(3)
L=∑j=1,⋯,k−Icountbi−bj>0,1≤i≤VCS,bi,bj are S column vectors of influence matrix Vertexm, i≠j, L is the numbers of different sensitive attribute value(4)
IfP=countMAXi=1⋯emtik=1>0 in influence matrix Vertexm, when tik is generated, under the precondition of anonymity, promote generalization hierarchies, or suppress directly [19]. P denotes sensitive degrees between QIk and S in influence matrixVertexm, if P=1, it means that tik will influence bi’s sensibilityHere, thresholdβ is important degree parameter of sensitive attribute in condition (2). If sensitive attribute values of an equivalent class (VCS) are less then β, that is to say sensitive attribute of these vertexes in k-isomorphism vertex group cannot affect their privacy, all vertexes can be published directly. Otherwise, must satisfy condition (3) and condition (4). If L>0, number of different sensitive attribute value is greater than or equal to 2, L makes sensitive attribute diversity.


#### 2.4.2. Personalizedα,β,l,k-Anonymity Example

There is an example which is shown to explain the definition and the process of personalizedα,β,l,k-anonymity according to Figure 2.Figure 2
Isomorphism social relationships network graph.
(a)
Subgraph G1(b)
Subgraph G2(c)
Subgraph G3Figure1(a) is the subgraph G of social relationships network, and the isomorphism subgraphs of G are found. The 3-isomorphism subgraphs are shown in Figure 2.In Figure2, (a) is the initial subgraph in Figure 1, and (b) and (c) are the isomorphism graphs corresponding to (a). From graph G, the amount of vertexes ∣Vp∣ is 27, and the amount of edges ∣Ep∣ is 39. Therefore, 9 3-isomorphism vertex groups and 13 3-isomorphosm edge groups are created and listed in Tables 5 and 6.Table 5
9 vertex groups of 3-isomorphism.
VCSG1G2G31A1A2A32B1B2B33C1C2C34D1D2D35E1E2E36F1F2F37G1G2G38H1H2H39I1I2I3Table 6
13 edges groups of 3-isomorphism.
ECSG1G2G31A1,B1A2,B2A3,B32A1,I1A2,I2A3,I33B1,C1B2,C2B3,C34B1,G1B2,G2B3,G35B1,I1B2,I2B3,I36C1,D1C2,D2C3,D37C1,G1C2,G2C3,G38D1,E1D2,E2D3,E39D1,F1D2,F2D3,F310E1,F1E2,F2E3,F311F1,G1F2,G2F3,G312G1,H1G2,H2G3,H313H1,I1H2,I2H3,I3Now, the 9 3-isomorphism vertex groups are generalized by their identifier attributes according to parameterβ. The isomorphism vertex groups VCS are changed into equivalence class vertexes groups QI. The item age, gender, and ZIP are identifier attributes, and disease item is the sensitive attribute. The inheritance hierarchy tree of ZIP is shown in Figure 3. The inheritance hierarchy tree of disease is shown in Figure 4 [21].Figure 3
Hierarchies tree of ZIP.Figure 4
Hierarchies tree of disease.TheA1, A2, and A3 attributes in the isomorphism groups VCS1 and VCS2 are listed in Table 7. After generalization, the identifier attributes value gen (VCS) are created and shown in Table 8 [15].Table 7
Example of isomorphism groups vertex’s attributes values.
VCSNumRaceOccupationAgeGenderZIPDisease1A1AsianSalesman25M150086FluA2AsianSalesman35F150084FluA3BlackTeacher35M150081Mammary cancer2B1WhiteTeacher45F150090Lung cancerB2WhiteDriver45M150041Lung cancerB3WhiteDriver50M150024Lung cancerTable 8
Example of isomorphism groups’ generalization identifier attributes values.
VCSNumRaceOccupationAgeGenderZIPDisease1A1AsianSalesman[25,35)∗15008∗FluA2AsianSalesman[25,35)∗FluA3BlackTeacher[25,35)∗Mammary cancer2B1WhiteTeacher[45,50)F1500∗∗∗B2WhiteDriver[45,50)M∗B3WhiteDriver[45,50)M∗


## 2.1. Related Concepts

Definition 1.k-Anonymity.
RTA1,⋯,An is a table and QIRT is quasi-identifier in RT. RT is said to satisfy k-anonymity if and only if each sequence of values in RTQIRT emerge k occurrences at least in RTQIRT [15].Table1 is said to satisfy k-anonymity, QIRT includes nation, birthday, gender, ZIP, the sensitive attribute is disease, k=2. As can be seen from Table 1, t1QI=t2QI, t3QI=t4QI, t5QI=t6QI=t7QI.Definition 2.k-Degree anonymity.
A social network graphGV;E is said to satisfy k-degree anonymity, if each vertex (node) has k−1 other vertexes at least, and these vertex’s degree are same in the social network graph. The variable V represents vertex amounts, and E represents edge amounts between vertexes [16, 17].Table 1
Example of 2-anonymity,QI=Nation,Birthday,Gender,ZIP.
No.NationBirthdayGenderZIPSalary1Yellow1995F26118∗90002Yellow1995F26118∗50003Yellow1994M26112∗270004Yellow1994M26112∗100005Brown1993F26113∗75006Brown1993F26113∗300007Brown1993F26113∗9500K-degree anonymity can prevent the inference attack by the adversary with background knowledge about vertex degree. In Figure 1, degree collection is d=4,3,2,4,3,3,2,3,2 in primal social network graph (a), so anonymity social network graph (b) satisfies 2-degree anonymity in Figure 1.Definition 3. Graph isomorphism.
For graphs:G1=V1,E1 and G2=V2,E2 where ∣V1∣=∣V2∣, if there is a bijection h between V1 and V2 satisfies ∀u,v∈E1, if and only if ∃hu,hv∈E2, G1, and G2 are graph isomorphism, represented as G1≅G2. Vi represents vertex (node) numbers, and Ei represents edge numbers between vertexes.Figure 1
2-Anonymity publishing in a social network.
(a)(b)(c)For example, when we delete the node information of (a) and (b) in Figure1, (a) and (b) are isomorphic [18].Definition 4.k-Isomorphism.
For a graphG=V,E, whose k sub-graphs are g1,g2,⋯,gk, if gil≤i≤k satisfies: (1) Ui=1kgi=G; (2) gi∩gj=Φ,i≠j (3) giandgji≠j are isomorphism, then, the graph G is k-isomorphism.Definition 5.k-Isomorphism vertex group.
Given ak-isomorphism publishing graph Gp=VP,EP=g1,g2,⋯gk,∀v1∈Gp,v1∈g1, then, there exist k−1 vertexes vi∈gii=2,⋯,k are isomorphic to v1, the vertex set consists the vertex vi and the k−1vi∈i=2,⋯,k is k-isomorphism vertexes group, which is denoted as VCS, VCS=k. Each VCS includes k vertexes and there are VP/kVCS in the k-isomorphism graph Gp.Definition 6.k-Isomorphism edge group.
Given ak-isomorphism publishing graph Gp=VP,EP=g1,g2,⋯,gk, ∀e1∈g1, then there exist k−1 edges ei∈gii=2,⋯,k is isomorphic to e1, the vertex set consists the vertex e1, and the k−1ei∈gii=2,⋯,k is k-isomorphism edges group, which is denoted as ECS, ECS=k. Each VCS includes k edges and there are EP/kECS in the k-isomorphism graph Gp.Definition 7. Social network graph.
Given a social network graph:G=V,E, wherein vertex set V denotes the social individuals, and the edge set E denotes the relationships among the social individuals. Each vertex and edge has its identify and attribute which includes
(a)
Identifier attribute (ID) of vertex asviviID(b)
Quasi-identifier attribute (QI) of vertexvi as QI=viN1,⋯,viNs,viC1,⋯,viCt(c)
Sensitive attribute (SA) of vertexvi as SA=viS1(d)
Quasi-identifier attribute (QI) of edgeei as QI=ejN1,⋯,ejNp,ejC1,⋯,ejCq(e)
Sensitive attribute (SA) of edgeei as SA=ejS1(f)
Other attributes (OA)Attribute (QI) of edge denotes by vector pair (viID,vjID), the total number of vertexes N=V, N denotes QI of numeric attribute, C denotes QI of character attribute, s, t, p, and q denote the amount of QI, respectively. For example, Figure 1 is an example of friendship social network, each vertex is a customer, and each edge denotes relationship between two vertexes. Table 2 is primal data of each vertex in Figure 1(a). Table 3 is edge table, Eid denotes the sequence number of edge, Vid1 and Vid2 denote the sequence number of vertex of Figure 1(b), and weighted relationship denotes the relationship between Vid1 and Vid2 of Figure 1(c). Table 4 is another relational data table of a vertex of Figure 1(a).Table 2
The vertex table.
VidNameAgeGenderZIPSalary1Kya25F26118690002John25M26118550003Mira26F261101270004Maci26F261131100005Cathy27F26113175006Kurt27M261124300007Sage27F26118695008Rain37M261185280009Toni35M26112422000Table 3
The edge table.
EidVid1Vid2Weighted relationship11212143323242415252635373728462956110591117811279313891Table 4
Table of primal personal health information.
NameAgeGenderZIPDiseaseKya25F261186ColdJohn25M261185HypertensionMira26F261101AIDSMaci26F261131ColdCathy27F261131CancerKurt27M261124ObesitySage27F261186PneumoniaRain37M261185DiabetesToni35M261124Short breath


## 2.2. Sensitive Degree of Friend Relationship (SA) of Vertex and Edge

### 2.2.1. Sensitive Degree of Friend Relationship (SA) of Vertex

We use the influence matrix to represent the level of influence of vertex-sensitive attributes [19, 20]. We can use the influence matrix to meet the requirements of personalized privacy protection of users.tij: the influence degree of NO. j sensitive attribute generated by NO. i vertex.bi: the weightiness of sensitive attribute value of NO. i vertex.Influence matrixVertexm is with m rows, n+1 columns, m represents vertex amount, n represents QI attribute amount, so it can be described as
(1)Vertexm=tijbim×n+1QI1QI2QI3⋯QInt11t12t13⋯t1n⋯⋯⋯⋯⋯tm−11tm−12tm−13⋯tm−1ntm1tm2tm3⋯tmnSb1⋯bm−1bm.Thetij, bi values come from experts or experience value. For example, the weightiness of QI in Table 4 can be divided into 5 grades, 1, 0.8, 0.4, 0.1, and 0, and the weightiness of S in Table 4 can be divided into 5 grades too, 0.10, 0.60, 0.70, 0.80, and 0.90. The cold is general disease, and disease weightiness value can use 0.1. Common cold (influenza) may have the character of a regional outbreak, and we define the weight value of the ZIP as 0.8. Common cold may also have a little bit to do with gender, and we define the weight value of gender as 0.1. Then, we define the disease weight values of obesity, short breath, hypertension, diabetes, pneumonia, cancer, and AIDS as 0.12, 0.31, 0.5, 0.6, 0.7, 0.91, and 0.92, respectively. The influence matrix is as follows according to Table 4.
(2)Vertexm=tijbi9×5+1NationOccupationBirthdayGenderZIP0000.10.8⋯⋯⋯⋯⋯00.10.40000.1000Disease0.1⋯0.60.31.


### 2.2.2. Sensitive Degree of Friend Relationship (SA) of Edge

We described relationships of simple friend, good friend, and sweetheart friend (boyfriend or girlfriend) among the vertexes in Figure1 of friend relationship graph. Graph (c) of Figure 1 is an example of friend relationship graph, “1” represents simple friend relationship between two vertexes, “2” represents good friend relationship between two vertexes, “3” represents sweetheart relationship between two vertexes, and “0” represents no relationship between two vertexes. Usually, if sweetheart friend includes gay or lesbian relationship, most of people do not want others to know that he is gay or she is lesbian, so different people have different sensitive degree about friend relationships, so we must meet the needs of personalized privacy protection according to the practical application.


## 2.2.1. Sensitive Degree of Friend Relationship (SA) of Vertex

We use the influence matrix to represent the level of influence of vertex-sensitive attributes [19, 20]. We can use the influence matrix to meet the requirements of personalized privacy protection of users.tij: the influence degree of NO. j sensitive attribute generated by NO. i vertex.bi: the weightiness of sensitive attribute value of NO. i vertex.Influence matrixVertexm is with m rows, n+1 columns, m represents vertex amount, n represents QI attribute amount, so it can be described as
(1)Vertexm=tijbim×n+1QI1QI2QI3⋯QInt11t12t13⋯t1n⋯⋯⋯⋯⋯tm−11tm−12tm−13⋯tm−1ntm1tm2tm3⋯tmnSb1⋯bm−1bm.Thetij, bi values come from experts or experience value. For example, the weightiness of QI in Table 4 can be divided into 5 grades, 1, 0.8, 0.4, 0.1, and 0, and the weightiness of S in Table 4 can be divided into 5 grades too, 0.10, 0.60, 0.70, 0.80, and 0.90. The cold is general disease, and disease weightiness value can use 0.1. Common cold (influenza) may have the character of a regional outbreak, and we define the weight value of the ZIP as 0.8. Common cold may also have a little bit to do with gender, and we define the weight value of gender as 0.1. Then, we define the disease weight values of obesity, short breath, hypertension, diabetes, pneumonia, cancer, and AIDS as 0.12, 0.31, 0.5, 0.6, 0.7, 0.91, and 0.92, respectively. The influence matrix is as follows according to Table 4.
(2)Vertexm=tijbi9×5+1NationOccupationBirthdayGenderZIP0000.10.8⋯⋯⋯⋯⋯00.10.40000.1000Disease0.1⋯0.60.31.


## 2.2.2. Sensitive Degree of Friend Relationship (SA) of Edge

We described relationships of simple friend, good friend, and sweetheart friend (boyfriend or girlfriend) among the vertexes in Figure1 of friend relationship graph. Graph (c) of Figure 1 is an example of friend relationship graph, “1” represents simple friend relationship between two vertexes, “2” represents good friend relationship between two vertexes, “3” represents sweetheart relationship between two vertexes, and “0” represents no relationship between two vertexes. Usually, if sweetheart friend includes gay or lesbian relationship, most of people do not want others to know that he is gay or she is lesbian, so different people have different sensitive degree about friend relationships, so we must meet the needs of personalized privacy protection according to the practical application.


## 2.3.αd,k-Anonymity Graph

In order to make it impossible for an attacker to infer the real relationship between targeted individuals and corresponding vertexes with a probability,k-anonymity concept in data tables and the new concept of αd,k-anonymity are introduced.Definition 8.αd,k-Anonymity of the vertex.
Undirected graphG=V,E, the graph Gp=Vp,Ep is as its anonymous publishing graph, if a vertex v∈V, there are at least k−1 vertexes u1,u2,⋯,uk−1∈Vp in Gp, which makes Neighbordv≅Neighbordui and v≠ui, wherein, i=1,2,⋯k−1, thus, the vertex v is d,k-anonymity, and the vertex v is αd,k-anonymity according to α, α is the weight of relationships (edge weight) of d- neighborhood of vertex v.
For example, in Figures1, α=1,2,3 of vertex F (sage), and α=1,2,3 of vertex H (Maci), so vertex F and vertex H satisfy α1,2-anonymity.Definition 9.αd,k-Anonymity of the graph.
Undirected graphG=V,E, the graph Gp=Vp,Ep is as its anonymous publishing graph. If any vertex v∈V is d,k-anonymity, thus, the graph Gp is d,k-anonymity, if any vertex v∈V is αd,k-anonymity, thus, the graph Gp is αd,k-anonymity.Definition 10. Individual information leakage.
Suppose graphGp is the anonymity publishing graph of social network graph G, when the relative sensitive coefficient k and l satisfy one of the following four conditions, then, there exists individual information leakage. Otherwise, if the graph Gp can ensure that any of the following circumstances are not going to happen, the anonymity publishing graph Gp is regarded as secure. If the graph Gp can ensure the following circumstance (1) and (2) will not happen, then, the anonymity publishing graph Gp is k-secure [21].
(1)
Vertex Leakage. The probability of ascertaining the corresponding relationship between the vertex in the graph Gp and the target individual A in the primal graph G is greater than 1/k(2)
Edge Leakage. The probability of ascertaining the corresponding relationship between the edge in the graph Gp and the edge in the primal graph G is greater than 1/k(3)
Leakage of Vertex Sensitive Information. The probability of ascertaining the sensitive information of target individual A in the primal graph G is greater than 1/l(4)
Leakage of Edge Sensitive Information. The probability of ascertaining the sensitive information of the edge in the primal graph G is greater than 1/l


## 2.4. Personalizedα,β,l,k-Anonymity

### 2.4.1. Personalizedα,β,l,k-Anonymity Model

Personalizedα,β,l,k-anonymity satisfies the following conditions:
(1)
Personalizedα,β,l,k-anonymity satisfies αd,k-anonymity(2)
∀bi<β in matrix Vertexm, all vertexes in k-isomorphism vertexes group be supposed to be published directly. Otherwise should be satisfied condition (3) and condition (4)(3)
L=∑j=1,⋯,k−Icountbi−bj>0,1≤i≤VCS,bi,bj are S column vectors of influence matrix Vertexm, i≠j, L is the numbers of different sensitive attribute value(4)
IfP=countMAXi=1⋯emtik=1>0 in influence matrix Vertexm, when tik is generated, under the precondition of anonymity, promote generalization hierarchies, or suppress directly [19]. P denotes sensitive degrees between QIk and S in influence matrixVertexm, if P=1, it means that tik will influence bi’s sensibilityHere, thresholdβ is important degree parameter of sensitive attribute in condition (2). If sensitive attribute values of an equivalent class (VCS) are less then β, that is to say sensitive attribute of these vertexes in k-isomorphism vertex group cannot affect their privacy, all vertexes can be published directly. Otherwise, must satisfy condition (3) and condition (4). If L>0, number of different sensitive attribute value is greater than or equal to 2, L makes sensitive attribute diversity.


### 2.4.2. Personalizedα,β,l,k-Anonymity Example

There is an example which is shown to explain the definition and the process of personalizedα,β,l,k-anonymity according to Figure 2.Figure 2
Isomorphism social relationships network graph.
(a)
Subgraph G1(b)
Subgraph G2(c)
Subgraph G3Figure1(a) is the subgraph G of social relationships network, and the isomorphism subgraphs of G are found. The 3-isomorphism subgraphs are shown in Figure 2.In Figure2, (a) is the initial subgraph in Figure 1, and (b) and (c) are the isomorphism graphs corresponding to (a). From graph G, the amount of vertexes ∣Vp∣ is 27, and the amount of edges ∣Ep∣ is 39. Therefore, 9 3-isomorphism vertex groups and 13 3-isomorphosm edge groups are created and listed in Tables 5 and 6.Table 5
9 vertex groups of 3-isomorphism.
VCSG1G2G31A1A2A32B1B2B33C1C2C34D1D2D35E1E2E36F1F2F37G1G2G38H1H2H39I1I2I3Table 6
13 edges groups of 3-isomorphism.
ECSG1G2G31A1,B1A2,B2A3,B32A1,I1A2,I2A3,I33B1,C1B2,C2B3,C34B1,G1B2,G2B3,G35B1,I1B2,I2B3,I36C1,D1C2,D2C3,D37C1,G1C2,G2C3,G38D1,E1D2,E2D3,E39D1,F1D2,F2D3,F310E1,F1E2,F2E3,F311F1,G1F2,G2F3,G312G1,H1G2,H2G3,H313H1,I1H2,I2H3,I3Now, the 9 3-isomorphism vertex groups are generalized by their identifier attributes according to parameterβ. The isomorphism vertex groups VCS are changed into equivalence class vertexes groups QI. The item age, gender, and ZIP are identifier attributes, and disease item is the sensitive attribute. The inheritance hierarchy tree of ZIP is shown in Figure 3. The inheritance hierarchy tree of disease is shown in Figure 4 [21].Figure 3
Hierarchies tree of ZIP.Figure 4
Hierarchies tree of disease.TheA1, A2, and A3 attributes in the isomorphism groups VCS1 and VCS2 are listed in Table 7. After generalization, the identifier attributes value gen (VCS) are created and shown in Table 8 [15].Table 7
Example of isomorphism groups vertex’s attributes values.
VCSNumRaceOccupationAgeGenderZIPDisease1A1AsianSalesman25M150086FluA2AsianSalesman35F150084FluA3BlackTeacher35M150081Mammary cancer2B1WhiteTeacher45F150090Lung cancerB2WhiteDriver45M150041Lung cancerB3WhiteDriver50M150024Lung cancerTable 8
Example of isomorphism groups’ generalization identifier attributes values.
VCSNumRaceOccupationAgeGenderZIPDisease1A1AsianSalesman[25,35)∗15008∗FluA2AsianSalesman[25,35)∗FluA3BlackTeacher[25,35)∗Mammary cancer2B1WhiteTeacher[45,50)F1500∗∗∗B2WhiteDriver[45,50)M∗B3WhiteDriver[45,50)M∗


## 2.4.1. Personalizedα,β,l,k-Anonymity Model

Personalizedα,β,l,k-anonymity satisfies the following conditions:
(1)
Personalizedα,β,l,k-anonymity satisfies αd,k-anonymity(2)
∀bi<β in matrix Vertexm, all vertexes in k-isomorphism vertexes group be supposed to be published directly. Otherwise should be satisfied condition (3) and condition (4)(3)
L=∑j=1,⋯,k−Icountbi−bj>0,1≤i≤VCS,bi,bj are S column vectors of influence matrix Vertexm, i≠j, L is the numbers of different sensitive attribute value(4)
IfP=countMAXi=1⋯emtik=1>0 in influence matrix Vertexm, when tik is generated, under the precondition of anonymity, promote generalization hierarchies, or suppress directly [19]. P denotes sensitive degrees between QIk and S in influence matrixVertexm, if P=1, it means that tik will influence bi’s sensibilityHere, thresholdβ is important degree parameter of sensitive attribute in condition (2). If sensitive attribute values of an equivalent class (VCS) are less then β, that is to say sensitive attribute of these vertexes in k-isomorphism vertex group cannot affect their privacy, all vertexes can be published directly. Otherwise, must satisfy condition (3) and condition (4). If L>0, number of different sensitive attribute value is greater than or equal to 2, L makes sensitive attribute diversity.


## 2.4.2. Personalizedα,β,l,k-Anonymity Example

There is an example which is shown to explain the definition and the process of personalizedα,β,l,k-anonymity according to Figure 2.Figure 2
Isomorphism social relationships network graph.
(a)
Subgraph G1(b)
Subgraph G2(c)
Subgraph G3Figure1(a) is the subgraph G of social relationships network, and the isomorphism subgraphs of G are found. The 3-isomorphism subgraphs are shown in Figure 2.In Figure2, (a) is the initial subgraph in Figure 1, and (b) and (c) are the isomorphism graphs corresponding to (a). From graph G, the amount of vertexes ∣Vp∣ is 27, and the amount of edges ∣Ep∣ is 39. Therefore, 9 3-isomorphism vertex groups and 13 3-isomorphosm edge groups are created and listed in Tables 5 and 6.Table 5
9 vertex groups of 3-isomorphism.
VCSG1G2G31A1A2A32B1B2B33C1C2C34D1D2D35E1E2E36F1F2F37G1G2G38H1H2H39I1I2I3Table 6
13 edges groups of 3-isomorphism.
ECSG1G2G31A1,B1A2,B2A3,B32A1,I1A2,I2A3,I33B1,C1B2,C2B3,C34B1,G1B2,G2B3,G35B1,I1B2,I2B3,I36C1,D1C2,D2C3,D37C1,G1C2,G2C3,G38D1,E1D2,E2D3,E39D1,F1D2,F2D3,F310E1,F1E2,F2E3,F311F1,G1F2,G2F3,G312G1,H1G2,H2G3,H313H1,I1H2,I2H3,I3Now, the 9 3-isomorphism vertex groups are generalized by their identifier attributes according to parameterβ. The isomorphism vertex groups VCS are changed into equivalence class vertexes groups QI. The item age, gender, and ZIP are identifier attributes, and disease item is the sensitive attribute. The inheritance hierarchy tree of ZIP is shown in Figure 3. The inheritance hierarchy tree of disease is shown in Figure 4 [21].Figure 3
Hierarchies tree of ZIP.Figure 4
Hierarchies tree of disease.TheA1, A2, and A3 attributes in the isomorphism groups VCS1 and VCS2 are listed in Table 7. After generalization, the identifier attributes value gen (VCS) are created and shown in Table 8 [15].Table 7
Example of isomorphism groups vertex’s attributes values.
VCSNumRaceOccupationAgeGenderZIPDisease1A1AsianSalesman25M150086FluA2AsianSalesman35F150084FluA3BlackTeacher35M150081Mammary cancer2B1WhiteTeacher45F150090Lung cancerB2WhiteDriver45M150041Lung cancerB3WhiteDriver50M150024Lung cancerTable 8
Example of isomorphism groups’ generalization identifier attributes values.
VCSNumRaceOccupationAgeGenderZIPDisease1A1AsianSalesman[25,35)∗15008∗FluA2AsianSalesman[25,35)∗FluA3BlackTeacher[25,35)∗Mammary cancer2B1WhiteTeacher[45,50)F1500∗∗∗B2WhiteDriver[45,50)M∗B3WhiteDriver[45,50)M∗


## 3. Personalizedα,β,l,k-Anonymity Algorithm

The basic algorithm principle is thatk-isomorphism graph Gp=g1,⋯,ge is caught; k-isomorphism graph vertex group VCS is generalized about identifier attributes and sensitive attributes; edge group ECS is generalized about identifier attributes and sensitive attributes. In the process, the generalization is not executed definitely, especially when the type differences do not affect l-diversity [22]. The input parameter α=0,1,2,3 indicates the generalizing type: when the value is 0, it should be static generalization, and when the value is greater than 0, it means the generalizing would be on the base of graph isomorphism. The input parameter α indicates the sensitive degree between nodes. When α≠0, we achieve αd,k-anonymity graph, d-neighborhood attack of graph and structure attack of graph can be prevented [23, 24], when α=0, the input parameter β is the generalization threshold [19, 22], background knowledge attack and homogeneity attack can be prevented by using anonymous data of vertexes in social network effectively, and diversity of sensitive attribute can be solved. The following is personalized α,β,l,k-anonymity algorithm (α=0), and personalized α,β,l,k-anonymity algorithm (α≠0) has been given in another paper published by the author [23].Algorithm 1: Personalized α,β,l,k-anonymity algorithm.
Inputs:Initial anonymous graphG = (V, E),Sensitivity parameters:k’(k’ ≥2); l(2 ≤ l ≤ k’); m(l ≤ m ≤ |V|);Node attributes table:AS = {viS,viN(1),…,viN(s),viC(1),…,viC(t)};Edge attributes table:AS = {vjS,vjN(1),…,vjN(s),vjC(1),…,vjC(t)};All the classified attribute inheritance treeHCInput parametersα =0 and βOutputs:Anonymous graphGp = {g1, g2, …, ge};The whole VCS, ECS and their attribute information;Steps:1 anonymous graphGp, groups VCS and ECS are caught;2 readα to judge the generalizing type;3 got the group number:NVCS = |NVP|/k, NECS = |NEP|/k;4fori =1 to NVCSdo//QI attributes generalization5forj =1 to sdo//numeric type attributes generalization6gen(VCSi)[Nj] = [min{v1N(j), …,vkN(j)},max{v1N(j), …,vkN(j)}]7end for8forj =1 to tdo//t type QI attributes generalization9gen(VCSi)[Cj] = {v1C(j),…,vkC(j)}10end for11whileSAVCSi<l&&SAVCSi/SAVP>βdo12if(sensitive attributes are classified) then13forj =0 to kdo14vjC is replaced by its parents node in classified inheritance tree of sensitive attribute15ifSAVCSi≥lthen jump while loop16end for17Else18forj =1 to kdo19     the interval ofvjN is changed to its neighborhood;20ifSAVCSi≥lthen jump while loop21end for22end if23end while24end for25fori =1 to NECSdo26forj =1 to pdo27gen(ECSi)[Nj] = [min{v1N(j),…,vkN(j)},max{v1N(j), …,vkN(j)}]28end for29forj =1 to qdo30gen(ECSi)[Cj] = {e1C(j),…,ekC(j)}31end for32whileSAVCSi<l&&SAVCSi/∣SAVP∣>βdo33if(sensitive attributes are classified) then34forj =1 to kdo35vjC is replaced by its parents node in classified inheritance tree of sensitive attribute36ifSAVCSi≥lthen jump while loop37end for38Else39forj =1 to kdo40     the interval ofnjN is changed to its neighborhood;41ifSAVCSi≥lthen jump while loop42end for43end if44end while45end for46 anonymous graphGp is published; all the VCS nodes, ECS edges and their attribute information are published


## 4. Experiments and Results

The experiments were completed in the PC with Intel(R) Core(TM) i5-4590 CPU @ 3.30 GHz, 8 GB memory, and the OS is Microsoft Windows 7. The programs were coded and compiled in VS 2019 IDE.The vertex (nodes) data set in these experiments are from adults census data set of the UC Irvine Machine Learning Repository [25, 26]. There are two experiments examples, and the vertex numbers of each are 300 and 1000. In these vertexes, 6 attributes are considered in the experiments, which are age, occupation, race, gender, zip, and disease. In these attributes, age is numeric, and the others are category. The attribute disease is sensitive attribute. The edge set in these experiments is created by Pajek software randomly, and the numbers of nodes are, respectively, 5000, 10000, 15000, 20000, and 25000.Information loss was compared between the algorithm in this paper that we proposed and paper [15]. We use the information loss method from paper [15]. The algorithm in this paper was named as ACIM (anonymous composite improved model) algorithm, and the algorithm in paper [15] was named as ACM (anonymous composite model) algorithm. In personalized α,β,l,k-anonymity algorithm (α=0), we make the data usability and original according to parameter β. When β is less than the given threshold, all vertex (data) will be published directly, which reduce the degree of data distortion [19].Whenα≠0, a number of nodes and edges should be added in initial graphs. When the structure is more different, the number of adding is higher. Meanwhile, the information loss is larger.Figure5 shows that some nodes are added to construct the isomorphic graphs, the percentage of adding nodes in all the nodes of the graph is shown in Figure 5, and the situation of edges is shown in Figure 6. With the k=5, k=10, and k=15, the increasing speed of nodes and edges slows down. These are additional redundant data.Figure 5
Nodes increasing percentage.Figure 6
Edges increasing percentage.In Figures7–9, the loss of information is shown with k=5, k=10, and k=15. The information loss degrees are increasing with the increasing of nodes, k and d. The reason is that the candidate set will be larger with the increasing of data scale, and finding similar neighborhood will be easier [19].Figure 7
Information loss degree whenk=5, d=1, and d=2.Figure 8
Information loss degree whenk=10, d=1, and d=2.Figure 9
Information loss degree whenk=15, d=1, and d=2.Whenα=0, the information loss results of attributes generalization are compared when k value is 5, 10, 15, 20, and 25. Figures 10 and 11 show the comparison results.Figure 10
Comparison of generalization information loss with 300 nodes.Figure 11
Comparison of generalization information loss with 1000 nodes.From Figure10, when k value increase, the demand of privacy protection becomes higher, which lead to obviously increasing of information loss. Besides, the loss of ACIM is lower after comparison. The reason is that not all the situations in same types are generalized but adding threshold judgments in ACIM. In Figure 11, the number of nodes is larger, and the generalization information loss is lower and make the node information availability for users.Figures12 and 13 show the comparison of generalization information loss with different β value. With higher β value, the vertex’s attributes should be changed less, so the information loss rate should be lower. That is to say, parameter β can make the vertex information availability and meet personalized needs.Figure 12
Comparison of generalization information loss with differentβ value with 300 nodes.Figure 13
Comparison of generalization information loss with differentβ value with 1000 nodes.


## 5. Conclusion

The authors studyk-anonymity technologies and introduce k-anonymity application in relational database and social network. We proposed personalized α,β,l,k-anonymity model of social network. A lot of personalized α,β,l,k-anonymity algorithm experiments were done by the authors. Experimental results show that d-neighborhood attack of graph, background knowledge attack, and homogeneity attack can be prevented effectively by using anonymous vertexes and edges, as well as the influence matrix based on background knowledge. The diversity of vertex-sensitive attribute can be achieved. Personalized protecting privacy requirements can be met by using such parameter as α,β,l,k.



---

*Source: 7187528-2022-04-20.xml*