Harmonic Modularity for Joint Community and Structural Hole Spanner Detection
This research delves into the detection of joint community and structural hole spanners in social networks using the Harmonic Modularity model. The study proposes a metric to evaluate the quality of identified structural hole spanners and showcases the effectiveness of the model in simultaneously detecting communities and structural holes. Key innovations, algorithm details, and insights into the interconnected concepts of community and structural hole spanners are explored.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Joint Community and Structural Hole Spanner Detection via Harmonic Modularity Lifang He College of Computer Science and Software Engineering Shenzhen University, China
Core Research in Social Network[1] Information Diffusion Application Prediction Search Advertise Macro Meso Micro Social Network Analysis Community ER model BA model Structural influence Social tie behavior Action Social Group hole Algorithmic Foundations Social Theories Theory BIG Social Data [1] T. Lou and J. Tang. Mining Structural Hole Spanners Through Information Diffusion in Social Networks. In WWW'13 Slide.
Intuitions Community & Structural hole spanner. Holes exists between communities that are otherwise disconnected[2]. Structural hole spanners control information diffusion between communities. Community 1 Community 2 Information diffusion Well, community & structural hole spanner are naturally tangled with each other Community 3 Structural Hole Spanner [2] R. S. Burt. Structural Holes: The Social Structure of Competition. Harvard University Press, 1992.
Today, let us start with the joint study of community & structural hole spanner Three parts
Overview Study an interesting problem : joint community & structural hole spanner detection. Propose a harmonic modularity model (HAM) to simultaneously detect community and structural hole spanner in social networks, and provide a metric (SHII) to evaluate the quality of discovered structural hole spanners. Results HAM performs well on both community detection and structural hole spanner detection. SHII is an effective measure for evaluating the structural hole spanners. We provide a unique insight into the joint notions of community and structural hole spanner.
Algorithm Harmonic Modularity INPUT : -- A social network, G = (V, E) Identifying m communities C = (C1, C2, , Cm) and top-k structural hole spanners Objective function: measure the harmonic level between the node and its neighbors. L21-norm: enforce row-wise sparsity of F to discriminate relevant top-k structural hole spanners. F: community & Top-k structural holes spanners indicator
Algorithm Harmonic Modularity NOTE: How to get m communities and top-k structural hole spanners from F.
Metric Structural Hole Influence Index Numerator: measure the number of influenced outsiders. measure a metric based on the flow of information through the mined spanner candidates for some commonly studied information diffusion models Denominator: measure the number of influenced nodes (insiders & outsiders). NOTE: It is important to consider both numerator & denominator in the SHII. SHII depends heavily on the applied information diffusion model.
Experiment # Node # Edge ## SH spanner # Community Karate Club 34 78 13 2 DBLP 1557.6 362.19 4915.6 451.95 189 49.44 15 4.24 YouTube 1310 133.67 2853.5 289.69 91.3 13.57 15.25 2.06 GOAL: Community detection & Structural hole spanner detection
Structural Hole Spanner Detection Information diffusion model 5 - 10 times better
Case study on the karate club network Visualization: Nodes with mark O represent structural hole spanners An example: finding top 3 structural holes HAM captures the most intermediate nodes between communities. Other methods tend to take the highest degree nodes as structural hole spanners.
Community Detection Clear Improvement Better
Efficiency Converge around only 20 iterations. Efficient!!
Future works Learning from overlapping social networks. Learning from heterogeneous social networks. Learning from dynamic social networks.
Thanks you Collaborators: Chun-Ta Lu (UIC) Jiaqi Ma (THU), Jianping Cao (NUDT), Linlin Shen (SZU), Philip S. Yu (UIC & THU) Download Paper & Slide: https://www2.cs.uic.edu/~clu
