Dynamic communities in evolving network graphs

• Main Authors: Macker, J. P., Claypool, D. J.
• Format: Conference Proceeding
• Language: English
• Subjects: Communities; Eigenvalues and eigenfunctions; Laplace equations; Measurement; Mobile communication; Mobile computing; Partitioning algorithms
• ISSN: 2155-7578; 2155-7586
• DOI: 10.1109/MILCOM.2012.6415614

This work presents applied research using spectral graph partitioning to examine potential community structures in evolving graphs. In our early experiments, evolving graphs represent time varying models of mobile wireless communication networks but they could also represent more abstract architectural representations such as middleware topologies or social network dynamics. While in its technical infancy, mobile network community analysis is an important capability in network planning, management, and adaptation strategies. We first present some discussion and technical background required to describe the analytical components and dynamic network modeling techniques. A set of mobile network scenarios are then described and applied to demonstrate the use of the dynamic spectral partitioning methods. We also develop and present a potential aid to dynamically establish partition set size and introduce a heuristic metric for partitioning quality. Our dynamic network experiments are represented by a series of evolving weighted graphs with dynamic attribute data that we plan to use in future work to represent network neighbor quality effects or other metrics as deemed appropriate to the scenario. We conclude by reviewing results and discussing future work.