Facebook network
To evaluate effectiveness of our algorithms on large networks, we solve the
problem of growing a network of friendships. In such social networks, nodes
denote people and edges denote friendships. There is an edge between two
nodes if the two people are friends cite{mcales12}. The ego-Facebook network
is undirected and unweighted with 
nodes and 
edges; the data is
available at http://snap.stanford.edu/data/.
Our objective is to improve performance of this network by adding a small
number of extra edges. We consider a setup in which people can only form
friendships with friends of their friends. This restricts the number of
potential edges in the controller graph to 
. To avoid memory issues,
we have implemented our algorithms in C. For 
with 
and 
, the proximal
gradient algorithm computes the solution in about 
, 
, 
, and
hours, respectively. After identifying the topology of the controller
graph, we compute the optimal edge weights via polishing.
 |
The number of nonzero elements in the vector |
decreases as 
increases.
 |
The |
performance deteriorates as the number of nonzero elements
in 
, the
identified sparse controller has only 
nonzero elements (it uses only
of the potential edges). Relative to the optimal centralized
controller, this controller degrades performance by 
. The Facebook network consists of ego nodes, 
. All other nodes are friends to at least one
of these ego nodes cite{mcales12}. In all of our experiments, the added
links with the largest edge weights connect either the ego nodes to each
other or three non-ego nodes, 
, to the ego nodes. Thus,
our method identifies non-ego nodes that play an important role in improving
the network performance.
We compare performance of the identified controller to a heuristic strategy
that is described next. Controller graph contains 
potential edges
between ego nodes. If the number of edges identified by our method is smaller
than , we randomly select the desired number of edges between ego nodes.
Otherwise, we connect all ego nodes and select the remaining edges in the
controller graph randomly. We then use polishing to find the optimal edge
weights. The performance of resulting random controller graphs are averaged
over trials and the performance loss relative to the optimal centralized
controller is displayed in the second figure. We see that our algorithm
always performs better than the heuristic strategy. On the other hand, the
heuristic strategy outperforms the strategy that adds edges randomly (without
paying attention to ego nodes). Unlike our method, the heuristic strategy
does not necessarily improve the performance by increasing the number of
added edges. In fact, the performance deteriorates as the number of edges in
the controller graph increases from 
to 
.