Vertex selection via a multi-graph analysis

Research output: Contribution to journalArticlepeer-review


We study vertex selection in the presence of multiple graphs associated with a vertex set V representing an online community. First, we formulate a collection of Markov chains on the graph ensemble and describe the characteristics of the associated mean hitting times on V. Then, we design a branch and bound optimisation technique for computing the subset of vertices A that exhibits the smallest hitting time cost across the multi-graph, given a constraint on the volume of A. The complexity of the branch and bound technique limits its application to medium-size graphs. Thus, we formulate a greedy optimisation method for computing a close approximation to the optimal subset at lower complexity, which can be implemented in a decentralised way, for further complexity reduction. We prove that the objective function under consideration is supermodular and monotonic, which guarantees near-optimal solutions for the greedy method. This is verified in our numerical experiments that compare its performance to that of the branch and bound technique, on smaller size graphs. The experiments also examine the hitting-time trade-off across the multi-graph that our optimisation exhibits, governed by the sampling cost factors λj associated with each graph layer Gj. Relative to conventional community graph centrality methods for vertex selection, we demonstrate a substantially lower sampling (network) cost and higher data dissemination rate, on actual Facebook and Internet topology data. The generality of our framework allows for its application to information retrieval, from a collection of items represented by a multi-graph. Here, we demonstrate higher semantic consistency over state-of-the-art single-graph methods, on the popular DBLP data set.

Original languageEnglish (US)
Pages (from-to)139-150
Number of pages12
JournalSignal Processing
StatePublished - Sep 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering


  • Branch and bound optimisation
  • Generalised Lagrange Multiplier method
  • Greedy approximation
  • Information retrieval
  • Mean hitting time
  • Multi-graph vertex selection
  • Supermodularity and monotonicity
  • Viral marketing


Dive into the research topics of 'Vertex selection via a multi-graph analysis'. Together they form a unique fingerprint.

Cite this