Social Networks (SN) can be used to pinpoint advertising campaigns and marketing intelligence efforts by leveraging similarities in interests among groups of friends. Let G= (V,E) be a social network where V is a set of nodes that represent profiles, and E is a set of undirected links that represent friendship relationships. Let H⊆V be a set of hidden target nodes whose privacy settings do not allow listing their friends. We assume that such hidden nodes also do not appear in the friend lists of their friends. This means that all links connecting hidden nodes are hidden as well. Let G'= (V-H,E') denote the visible network where E'={(u,v)E | u,v ∉ H} denotes a set of visible links.
We model a marketing campaign, targeted at some hidden profiles (H), as a susceptible infective (SI) epidemic diffusion process. Since we only know some information about the hidden profiles (i.e., they are students in some Israeli university), we expose (infect) at some time point t a set of visible profiles It⊆V which seem most related to the target hidden profiles. Each neighbor of these profiles is exposed to the campaign at time t+1 with a predefined probability . The prevalence of the campaign at time point t is the number of infected nodes |It|. We assume that all information stored in a node is revealed including its friend list once the node is infected. We denote the number of hidden nodes that were exposed to the campaign (a.k.a. revealed) by Rt=H∩It. and the quality of the diffusion depends on the growth rate of Rt. We define Focus (Ft=|Rt|/|It|) as a measure of diffusion effectiveness. Normalized Focus (NF=(Rt/H)/(It/V)) is the fraction of revealed target nodes (out of all targets) divided by the fraction of infected nodes (out of all nodes in the network).
Given the visible network (G'={V-H, E'}), the goal is to find a small set of seeds (initially infected nodes) I0∈V-H that result in the most focused diffusion for a given social network (G). We hypothesize that the seeds should be as close as possible to all hidden nodes but at the same time far from most of the known nodes. Our results indicate that while Closeness Centrality (defined as the sum of reciprocal distances to nodes in the visible network) reveals hidden nodes faster than any other strategy, it also has the lowest focus. We propose a strategy that combines spectral analysis for identifying missing nodes and a special weighted version of Group Closeness which has not been evaluated in earlier work. This strategy results in highly-focused diffusion, especially during the first stages of the propagation.
