Partitioning Networks with Node Attributes by Compressing Information Flow. Smith, L. M., Zhu, L., Lerman, K., & Percus, A. G. ACM Trans. Knowl. Discov. Data, 11(2):15:1–15:26, ACM, New York, NY, USA, November, 2016.
Partitioning Networks with Node Attributes by Compressing Information Flow [link]Paper  doi  abstract   bibtex   1 download  
Real-world networks are often organized as modules or communities of similar nodes that serve as functional units. These networks are also rich in content, with nodes having distinguishing features or attributes. In order to discover a network's modular structure, it is necessary to take into account not only its links but also node attributes. We describe an information-theoretic method that identifies modules by compressing descriptions of information flow on a network. Our formulation introduces node content into the description of information flow, which we then minimize to discover groups of nodes with similar attributes that also tend to trap the flow of information. The method has several advantages: it is conceptually simple and does not require ad-hoc parameters to specify the number of modules or to control the relative contribution of links and node attributes to network structure. We apply the proposed method to partition real-world networks with known community structure. We demonstrate that adding node attributes helps recover the underlying community structure in content-rich networks more effectively than using links alone. In addition, we show that our method is faster and more accurate than alternative state-of-the-art algorithms.
@article{Smith2016tkdd,
 author = {Smith, Laura M. and Zhu, Linhong and Lerman, Kristina and Percus, Allon G.},
 title = {Partitioning Networks with Node Attributes by Compressing Information Flow},
 journal = {ACM Trans. Knowl. Discov. Data},
     abstract = {Real-world networks are often organized as modules or communities of similar
nodes that serve as functional units. These networks are also rich in content,
with nodes having distinguishing features or attributes. In order to discover a
network's modular structure, it is necessary to take into account not only its
links but also node attributes. We describe an information-theoretic method
that identifies modules by compressing descriptions of information flow on a
network. Our formulation introduces node content into the description of
information flow, which we then minimize to discover groups of nodes with
similar attributes that also tend to trap the flow of information. The method
has several advantages: it is conceptually simple and does not require ad-hoc
parameters to specify the number of modules or to control the relative
contribution of links and node attributes to network structure. We apply the
proposed method to partition real-world networks with known community
structure. We demonstrate that adding node attributes helps recover the
underlying community structure in content-rich networks more effectively than
using links alone. In addition, we show that our method is faster and more
accurate than alternative state-of-the-art algorithms.},
 issue_date = {November 2016},
 volume = {11},
 number = {2},
 month = nov,
 year = {2016},
 issn = {1556-4681},
 pages = {15:1--15:26},
 articleno = {15},
 numpages = {26},
    url = {http://arxiv.org/abs/1405.4332},
 doi = {10.1145/2968451},
 acmid = {2968451},
 publisher = {ACM},
 address = {New York, NY, USA},
     keywords = {social-networks},
}

Downloads: 1