Contents
Privacy and Social Network
Part 1. Introduction and History of Privacy and Social Network
Network theory is the study of graphs. Social network examines the structure of relationships between social entities like groups, websites or nation states. Since the 1970s, many of the mathematical and statistical tools used for studying networks. Social network analysis is the process of investigating social structures through network and graph theories. Since the 20th century, social scientists have used the concept of ‘social networks’ to imply the relationships of social systems from interpersonal to international. In the 1930s Jacob Moreno and Helen Jennings introduced basic analytical methods. In 1954, John Arundel Barnes started using the term systematically to denote patterns of ties. In fact, social network analysis has found applications in various academic disciplines. (Freeman, 2004) First of all, the network must be a subgraph of the original graph, in other words, its edges must come from the original graph. Second, it must span the original graph, which means it must include all the vertices of the original graph. Third, it need to be minimal, in other words, the total weight of the network should be as small as possible. A network is just another name for a connected graph. A network with no circuits is called a tree. A spanning tree of a network is a subgraph that connected all the vertices of the network and has no circuits. Among all spanning trees of a weight network, one with least total weight is called a minimum spanning tree of the network. In a tree, there is one and only one path joining any two vertices. Every edge is a bridge in a tree, and the tree has N vertices has N-1 edges. The reverse is also true.
Part.2 Minimum Spanning Tree (MST)
Definition
A minimum spanning tree (MST) is a spanning tree of an edge-weighted graph that the sum of the weights of its edges is no larger than the weight of any other spanning tree. It is the base of both privacy and social network which is helpful in finding the cheapest and fastest network.
Properties
1. The graph is connected with n-1 edges in an n-vertex graph and is acyclic.
2. Removing an edge breaks the tree into two separate parts.
3. Adding an edge that connects two vertices in a tree creates a unique cycle.
4. The MST need not be unique. However, if all the edge weights in G are distinct, then G has a unique MST.
5. If the weights are positive, then a minimum spanning tree is in fact a minimum-weight subgraph connecting all vertices
Example Graph G. Suppose T is the MST for G where a is in G but not in T.
Proposition 1
Let G = (V, E, W) be a weighted graph and T = (V,S) be an MST for G, and let a=xy be an edge of G not in T. Then
a)w(a) >= w(k) for any edge k on the path in T from x to y.
b)If w(a) = w(k), then we may obtain another MST T’ for G by replacing k by a in S.
Proof. Consider a spanning tree T of the graph G, and let a be an edge of G but not of T. Then we may substitute k for a to retain a spanning tree.
Hence, if we replace k by a in T, we obtain a spanning tree T’ of cost w(T’) = w(T) + w(a) - w(k) . If w(a) < w(k), then w(T’) < w(T). It is conflict to our assumption that T is a MST. If w(a) = w(k), then w(T’) = w(T). Therefore we know that T’ is also an MST.
Proposition 2
Let be a connected graph with distinct edge weights. Then there is a unique minimum spanning tree.
Proof. Suppose we have a minimum spanning tree T of the graph G and a different minimum spanning tree T’. W (e) is the weight of edge e and W (e’) is the weight of edge e’.
If W (e) > W (e’), then T is not a minimal spanning tree. If W (e) < W (e’), then T’ is not a minimal spanning tree. If we want both T and T’ to be the different minimal spanning tree, then we should have W (e) = W (e’). However, G is a connected graph with distinct edge weights, thus W (e) = W (e’) is impossible. As W (e) is not equal to W (e’), T and T’ should be the same.
Applications
1. Telecommunication networks. A business with several offices that need to lease phone lines to connect them up with each other, where the total costs should be minimized.
2. Transportation networks. To find the shortest path that visits each point at least once. It will be a Hamilton path if visits each point and edges only once. Note that we can always drop some edges to get a tree if visiting some points more than once, and thus in general the minimum spanning tree has a weight less than the original network.
3. Computer networks. The Internet is connected in a tree shape while we are using the searching engine. It is quite important to take advantage of the minimal spanning tree in order to find the information in the fastest and cheapest way.
4. Electrical Grid. An electrical grid is an interconnected network for delivering electricity from suppliers to consumers. The distribution of electricity and transmission is in tree shapes while the cheapest and simplest design is a question based on minimum spanning tree.
Part.3 Privacy
Definition Privacy can be translated into different meanings, depending on the context. From the political standpoint, Schement and Curtis (1995) describe privacy as security against intrusion by government. In general, privacy can be described as the ability of an individual or group to seclude themselves or information about themselves and thereby reveal themselves selectively (Yves Le Roux).
Issues With the development of technology and the existence of social media, it is getting harder and harder for people to keep their privacy. Any information that we uploaded into our social media can be accessed by hundreds of people through the network, even if we did not intend to do that. Not only information that we purposely uploaded to our social media, the information about the things that we browsed on our web browser on our free time is also being watched and collected, so that the ad makers can tailored the kinds of advertisements that shows on the web pages that we visited so that it relates to us in order to increase the chance of us clicking the link.
Other than our web browser history, our personal information are also in danger of exposure through social medias. An analysis of personal online journals revealed that personal informations such as name, address, birth date, location, and e-mail addresses are revealed to third parties online. The amount of informations revealed could result to cyberstalking and identity theft. Shortly, it is unavoidable to say that the amount of social media exposure creates danger to our privacy.
Privacy Paradox
Definition On May 2015, Benjamin Wittes and Jodie C. Liu wrote a paper titled “The Privacy Paradox: The privacy benefits of privacy threats”. The main idea is that “most technologies often enhance and diminish privacy, depending on how it is used, who is using it, and what sorts of privacy that person values. Individual concern with privacy often will not involve privacy in the abstract, but rather vis a vis specific audiences - that is to say that the question of privacy from who matters. At least some modern technologies that we commonly think of as privacy-eroding may in fact enhance privacy from the people in our immediate surrounding.”
One hand, we are sharing our thoughts and information about us online, and on the other hand, government agencies and marketers are collecting personal data about us. Katz and Rice (2002) describe the Internet as a panopticon, which is a “constant view of individuals through para societal mechanisms that influence behavior simply because of the possibility of being observed.”
