Exploration of Link Structure and Community-Based Node Roles in Network Analysis.
In:
Data Mining, 2007. ICDM 2007. Seventh IEEE International Conference on, pages 649 -654.
2007.
J. Scripps, Pang-Ning Tan and A.-H. Esfahanian.
[abstract]
[BibTeX]
Communities are nodes in a network that are grouped together based on a common set of properties. While the communities and link structures are often thought to be in alignment, it may not be the case when the communities are defined using other external criterion. In this paper we provide a new way to measure the alignment. We also provide a new metric that can be used to estimate the number of communities to which a node is attached. This metric, along with degree, is used to assign a community-based role to nodes. We demonstrate the usefulness of the community-based node roles by applying them to the influence maximization problem.
Node roles and community structure in networks.
In:
Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis, series WebKDD/SNA-KDD '07, pages 26-35.
ACM, New York, NY, USA, 2007.
Jerry Scripps, Pang-Ning Tan and Abdol-Hossein Esfahanian.
[doi]
[abstract]
[BibTeX]
A node role is a subjective characterization of the part it plays in a network structure. Knowing the role of a node is important for many link mining applications. For example, in Web search, nodes that are deemed to be authorities on a given topic are often found to be most relevant to the user's queries. There are a number of metrics that can be used to assign roles to individual nodes in a network, including degree, closeness, and betweenness. None of these metrics, however, take into account the community structure that underlies the network. In this paper we define community-based roles that the nodes can assume (ambassadors, big fish, loners, and bridges) and show how existing link mining techniques can be improved by knowledge of such roles. A new community-based metric is introduced for estimating the number of communities linked to a node. Using this metric and a modification of degree, we show how to assign community-based roles to the nodes. We also illustrate the benefits of knowing the community-based node roles in the context of link-based classification and influence maximization.
Role Assignments.
In:
U. Brandes and T. Erlebach, editors,
Network Analysis, pages 216-252.
Springer, Berlin / Heidelberg, 2005.
Jürgen Lerner.
[doi]
[abstract]
[BibTeX]
9.0. 9.0.1. Preliminaries 9.0.2. Role Graph 9.1. Structural Equivalence 9.1.1. Lattice of Equivalence Relations 9.1.2. Lattice of Structural Equivalences 9.1.3. Computation of Structural Equivalences 9.2. Regular Equivalence 9.2.1. Elementary Properties 9.2.2. Lattice Structure and Regular Interior 9.2.3. Computation of Regular Interior 9.2.4. The Role Assignment Problem 9.2.5. Existence of k-Role Assignments 9.3. Other Equivalences 9.3.1. Exact Role Assignments 9.3.2. Automorphic and Orbit Equivalence 9.3.3. Perfect Equivalence 9.3.4. Relative Regular Equivalence 9.4. Graphs with Multiple Relations 9.5. The Semigroup of a Graph 9.5.1. Winship-Pattison Role Equivalence 9.6. Chapter Notes