Na Li

Graduation Semester and Year




Document Type


Degree Name

Doctor of Philosophy in Computer Science


Computer Science and Engineering

First Advisor

Sajal Das


With the advent of Web 2.0 and advanced techniques of wireless devices (e.g., smart phones or iPhones), Online Social Networks (OSNs) and Mobile Social Networks (MSNs) are becoming integral part of our lives as two main digital social communities. Data collected from people's communication on OSNs and MSNs contains valuable information which makes human relationships more visible as compared to their existence in our physical world. For instance, the friend list on a user's profile page on Facebook clearly tells us the user's friendships with other users. Moreover, the short-range wireless communication techniques (e.g., Bluetooth) also enable us to “sense” human relations in MSNs composed of wireless devices carried by human. On the one hand, human relation networks can facilitate socially intelligent computing, for example, the friend recommendation service provided by most of the OSNs; on the other hand, we must ensure the security in using them to avoid users' concerns in OSNs and MSNs. This dissertation addresses four research problems in the effective and secure use of human relation networks in OSNs and MSNs: (1) How can OSN owners preserve users's relation privacy in sharing data with the third-parties? We model a more realistic attack against users' relation privacy in publishing OSN data, where part of the users may be identified from the published OSN data. We propose a privacy preservation model, called l-diversity, to protect users relation privacy. Furthermore, we propose three graph-manipulation based anonymization techniques to convert an arbitrary graph to a graph of l-diversity with less topology change as compared to the original graph. (2) How can a third-party analyst efficiently detect a minimum subgraph that connects a group of target users on OSNs with the minimum number of web accesses needed for online discovery? Based on the topological properties of human relation networks on OSNs, we propose two searching techniques which can quickly discover the subgraph connectivity on OSNs. Furthermore, we observe that users on OSNs are very well connected as we can find the connectivity of any group of target users by a small number of web accesses in searching on OSNs. (3) In MSNs, the approach to inferring a relation between two people is based on the encountering frequencies of their wireless devices. However, in a malicious wireless environment, one device can create redundant encountering records by tailgating another wireless device. The redundant records can be used by the former to launch a black hole attack to disturb data forwarding. We design a reputation-based framework guaranteeing the use of reliable relations in data forwarding in MSNs. (4) Highly active nodes which frequently meet with other nodes in an MSN, also called high-centrality nodes, are introduced in design of data forwarding protocols; however, overusing these nodes may cause serious network congestion. To deal with this issue, we build a framework which effectively spreads the congestion condition at high-centrality nodes to the entire network by social influence to notify data sources of the congestion situation so that they can adjust data generation rate to relieve network congestion.


Computer Sciences | Physical Sciences and Mathematics


Degree granted by The University of Texas at Arlington