  The ubiquitous proliferation of online social networks has led to the
widescale emergence of relational graphs expressing unique patterns in link
formation and descriptive user node features. Matrix Factorization and
Completion have become popular methods for Link Prediction due to the low rank
nature of mutual node friendship information, and the availability of parallel
computer architectures for rapid matrix processing. Current Link Prediction
literature has demonstrated vast performance improvement through the
utilization of sparsity in addition to the low rank matrix assumption. However,
the majority of research has introduced sparsity through the limited L1 or
Frobenius norms, instead of considering the more detailed distributions which
led to the graph formation and relationship evolution. In particular, social
networks have been found to express either Pareto, or more recently discovered,
Log Normal distributions. Employing the convexity-inducing Lovasz Extension, we
demonstrate how incorporating specific degree distribution information can lead
to large scale improvements in Matrix Completion based Link prediction. We
introduce Log-Normal Matrix Completion (LNMC), and solve the complex
optimization problem by employing Alternating Direction Method of Multipliers.
Using data from three popular social networks, our experiments yield up to 5%
AUC increase over top-performing non-structured sparsity based methods.
