The proliferation of mobile devices, such as smartphones and tablets, and the popularity of online social networks that link humans, mobile devices and Internet together, increasingly emphasize the role of human behaviors on network designs. Due to the involvement of human behaviors, social structure provides crucial information of network structure and node organization, and thus can be exploited for network designs, e.g., in online social networks and mobile social networks. Social structure that represents the relations between individuals or the organization of individuals can be seen as a summary of human behaviors. Social structure has been seen as a salient property that is common to many networks in recently studies in sociology, biology, physics and etc. Moreover, social structure is long-term stable, and hence we can also predict future node behaviors based on the given social structure. This research focuses on uncovering social structure from networks and applying social structure to network designs.
Uncovering Communities from Big Network Data
First, we consider community. Although community has been widely used in network designs, community detection is still an issue. The existing community detection algorithms focus on binary networks, while most networks are weighted. However, simplifying weighted networked as binary networks will cost the lost of important information. Therefore, we consider the community detection on weighted networks. We has designed a detection algorithm based conductance with very low computational complexity (tailored for big network data). The algorithm starts with a community formed by the two nodes connected by the highest weight edge and iteratively expands the community by adding a neighboring node that can maximally increase the conductance of the community. The algorithm has been evaluated on a large Facebook data set, and its performance is much better than existing algorithms based on the metrics (e.g., modularity) that quantify the quality of the detected community structure.
Information Diffusion in Online Social Networks
Online social networks has played a important role as a medium for information diffusion and it has been utilized as a platform for viral marketing through the power of “word-of-mouth”. As the essence of viral marketing applications is the information diffusion from a small number of individuals to the network by “word-of-mouth”, we address the problem of identifying a small number of individuals through whom the information can be diffused to the network quickly, referred as diffusion minimization problem. Unfortunately, the diffusion minimization problem under the probabilistic diffusion model can be formulated as an asymmetric k-center problem which is NP-hard and $\log^*n$-hard to approximate. To deal with this, we design a community based algorithm with better performance and less complexity. Unlike existing approximation algorithms, the community based algorithm, from the social point of view, leverages the community structure to solve the diffusion minimization problem, by deliberately selecting seed nodes from communities based their sociability.
Network Skeleton
Community structure is a complex representation of a social network, where a community may largely overlap with other communities, and hence it is hard to determine whether these communities should be seen as individual communities or a single community. To provide a more simple and clear representation, we propose network skeleton, a tree structure specially designed for organizing network nodes, as the underlying structure in mobile social networks. Network skeleton is simple and easy to be uncovered, and we have proposed a lightweight algorithm that constructs skeleton based on best friendship and also adopts to dynamic networks. With skeleton, nodes can be easily connected or separated from other nodes, which better facilitates network designs. We have exploited network skeleton for designing a data forwarding algorithm and a worm containment strategy in mobile social networks.