More Web Proxy on the site http://driver.im/

short-paper

Community Detection in Social Network with Pairwisely Constrained Symmetric Non-Negative Matrix Factorization

Authors:

Shan HeAuthors Info & Claims

ASONAM '15: Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015

Pages 541 - 546

https://doi.org/10.1145/2808797.2809383

Published: 25 August 2015 Publication History

Abstract

Non-negative Matrix Factorization (NMF) aims to find two non-negative matrices whose product approximates the original matrix well, and is widely used in clustering condition with good physical interpretability and universal applicability. Detecting communities with NMF can keep non-negative network physical definition and effectively capture communities-based structure in the low dimensional data space. However some NMF methods in community detection did not concern with more network inner structures or existing ground-truth community information.

In this paper, we propose a novel pairwisely constrained nonnegative symmetric matrix factorization (PCSNMF) method, which not only consider symmetric community structures of undirected network, but also takes into consideration the pairwise constraints generated from some ground-truth group information to enhance the community detection. We compare our approaches with other NMF-based methods in three social networks, and experimental results for community detection show that our approaches are all feasible and achieve better community detection results.

References

[1]

F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, "Defining and identifying communities in networks," Proceedings of the National Academy of Sciences of the United States of America, vol. 101, no. 9, pp. 2658--2663, 2004.

[2]

M. E. J. Newman and M. Girvan, "Finding and evaluating community structure in networks," Phys. Rev. E, vol. 69, p. 026113, 2004.

[3]

R. Andersen, F. Chung, and K. Lang, "Local graph partitioning using pagerank vectors," in Foundations of Computer Science, 2006. FOCS' 06. 47th Annual IEEE Symposium on. IEEE, 2006, pp. 475--486.

Digital Library

[4]

E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, "Mixed membership stochastic blockmodels," Journal of Machine Learning Research, vol. 9, pp. 1981--2014, 2008.

Digital Library

[5]

X. Cao, X. Wang, D. Jin, Y. Cao, and D. He, "Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization," Scientific reports, vol. 3, 2013.

[6]

L. Yang, R. Jin, and R. Sukthankar, "Semi-supervised learning with weakly-related unlabeled data: Towards better text categorization," in Twenty-Second Annual Conference on Neural Information Processing Systems. Citeseer, 2008.

[7]

M. Leng, Y. Yao, J. Cheng, W. Lv, and X. Chen, "Active semisupervised community detection algorithm with label propagation," in Database Systems for Advanced Applications. Springer Berlin Heidelberg, 2013, vol. 7826, pp. 324--338.

[8]

J. Yang and J. Leskovec, "Defining and evaluating network communities based on ground-truth," in Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, 2012, pp. 3:1--3:8.

Digital Library

[9]

D. Lee, H. Seung et al., "Learning the parts of objects by non-negative matrix factorization," Nature, vol. 401, no. 6755, pp. 788--791, 1999.

[10]

D. LAI, X. WU, H. LU, and C. NARDINI, "Learning overlapping communities in complex networks via non-negative matrix factorization," International Journal of Modern Physics C, vol. 22, no. 10, pp. 1173-- 1190, 2011.

[11]

Z.-Y. Zhang, K.-D. Sun, and S.-Q. Wang, "Enhanced community structure detection in complex networks with partial background information," Sci. Rep, vol. 3, 2013.

[12]

X. Ma, L. Gao, X. Yong, and L. Fu, "Semi-supervised clustering algorithm for community structure detection in complex networks," Physica A: Statistical Mechanics and its Applications, vol. 389, no. 1, pp. 187 -- 197, 2010.

[13]

H. Liu, Z. Wu, X. Li, D. Cai, and T. S. Huang, "Constrained nonnegative matrix factorization for image representation," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 34, no. 7, pp. 1299--1311, 2012.

Digital Library

[14]

Y. Yang and B. Hu, "Pairwise constraints-guided non-negative matrix factorization for document clustering," in Web Intelligence, IEEE/WIC/ACM International Conference on. IEEE, 2007, pp. 250-- 256.

Digital Library

[15]

F. Wang, T. Li, X. Wang, S. Zhu, and C. Ding, "Community discovery using nonnegative matrix factorization," Data Min. Knowl. Discov., vol. 22, no. 3, pp. 493--521, 2011.

Digital Library

[16]

W. Xu and Y. Gong, "Document clustering by concept factorization," in Proceedings of the 27th annual international ACM SIGIR conference on Research and development in informaion retrieval, 2004, pp. 202--209.

Digital Library

[17]

W. Xu, X. Liu, and Y. Gong, "Document clustering based on nonnegative matrix factorization," in Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, 2003, pp. 267--273.

Digital Library

[18]

D. Kuang, H. Park, and C. H. Ding, "Symmetric nonnegative matrix factorization for graph clustering." in SDM, vol. 12. SIAM, 2012, pp. 106--117.

[19]

D. Wang, T. Li, S. Zhu, and C. Ding, "Multi-document summarization via sentence-level semantic analysis and symmetric matrix factorization," in Proceedings of the 31st annual international ACM SIGIR conference on Research and development in informaion retrieval. ACM, 2008, pp. 307--314.

Digital Library

[20]

Z.-Y. Zhang, "Community structure detection in complex networks with partial background information," EPL (Europhysics Letters), vol. 101, no. 4, p. 48005, 2013.

[21]

H. Liu, Z. Wu, D. Cai, and T. Huang, "Constrained non-negative matrix factorization for image representation," Pattern Analysis and Machine Intelligence, IEEE Transactions on, no. 99, pp. 1--1, 2011.

Digital Library

[22]

R. Guimera, L. Danon, A. Diaz-Guilera, F. Giralt, and A. Arenas, "Self-similar community structure in a network of human interactions," Physical review E, vol. 68, no. 6, p. 065103, 2003.

[23]

M. E. Newman, "Modularity and community structure in networks," Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577--8582, 2006.

[24]

S. Cafieri, P. Hansen, and L. Liberti, "Improving heuristics for network modularity maximization using an exact algorithm," Discrete Applied Mathematics, vol. 163, pp. 65--72, 2014.

Digital Library

[25]

V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, "Fast unfolding of communities in large networks," Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no. 10, p. P10008, 2008.

[26]

D. Cai, X. He, J. Han, and T. Huang, "Graph regularized nonnegative matrix factorization for data representation," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 33, no. 8, pp. 1548--1560, 2011.

Digital Library

[27]

L. Lovasz and M. Plummer, Matching theory. Elsevier Science Ltd, 1986, no. 121.

[28]

S. Fortunato and M. Barthelemy, "Resolution limit in community detection," Proceedings of the National Academy of Sciences, vol. 104, no. 1, pp. 36--41, 2007.

Cited By

Li SSong CLu LChen Z(2024)Hierarchical Object Part Learning Using Deep Lp Smooth Symmetric Non-Negative Matrix FactorizationSymmetry10.3390/sym1603031216:3(312)Online publication date: 6-Mar-2024
https://doi.org/10.3390/sym16030312
Ferdowsi ADehghan Chenary M(2024)Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex NetworksAlgorithms10.3390/a1706022617:6(226)Online publication date: 23-May-2024
https://doi.org/10.3390/a17060226
Wang ZYuan RFu JWong KPeng C(2024)Core–Periphery Detection Based on Masked Bayesian Nonnegative Matrix FactorizationIEEE Transactions on Computational Social Systems10.1109/TCSS.2023.334740611:3(4102-4113)Online publication date: Jun-2024
https://doi.org/10.1109/TCSS.2023.3347406
Show More Cited By

Community Detection in Social Network with Pairwisely Constrained Symmetric Non-Negative Matrix Factorization

Recommendations

Non-negative Matrix Factorization with Pairwise Constraints and Graph Laplacian

Non-negative matrix factorization (NMF) is a very effective method for high dimensional data analysis, which has been widely used in information retrieval, computer vision, and pattern recognition. NMF aims to find two non-negative matrices whose ...
New SVD based initialization strategy for non-negative matrix factorization

We give a new method to determine the rank of the factorization for NMF algorithms.We propose a novel method SVD-NMF to enhance initialization for NMF.The compute process is cheap.Numerical results show that SVD-NMF convergent faster than NNDSVD and ...
Inverse problems for symmetric matrices with a submatrix constraint

This paper is concerned with the following problems: Problem I(a). Given a full column rank matrix X@?R^n^x^p and symmetric matrices B@?R^p^x^p and A"0@?R^r^x^r, find an nxn symmetric matrix A such thatX^TAX=B,A([1,r])=A"0, where A([1,r]) is the rxr ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASONAM '15: Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015

August 2015

835 pages

ISBN:9781450338547

DOI:10.1145/2808797

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 August 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper
Research
Refereed limited

Funding Sources

National Natural Science Foundation of China
the Science and Technology Commission of Shanghai Municipality
the Arts and Science Cross Special Fund of Shanghai Jiao Tong University

Conference

ASONAM '15

Sponsor:

SIGKDD

ASONAM '15: Advances in Social Networks Analysis and Mining 2015

August 25 - 28, 2015

Paris, France

Acceptance Rates

Overall Acceptance Rate 116 of 549 submissions, 21%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
399
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li SSong CLu LChen Z(2024)Hierarchical Object Part Learning Using Deep Lp Smooth Symmetric Non-Negative Matrix FactorizationSymmetry10.3390/sym1603031216:3(312)Online publication date: 6-Mar-2024
https://doi.org/10.3390/sym16030312
Ferdowsi ADehghan Chenary M(2024)Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex NetworksAlgorithms10.3390/a1706022617:6(226)Online publication date: 23-May-2024
https://doi.org/10.3390/a17060226
Wang ZYuan RFu JWong KPeng C(2024)Core–Periphery Detection Based on Masked Bayesian Nonnegative Matrix FactorizationIEEE Transactions on Computational Social Systems10.1109/TCSS.2023.334740611:3(4102-4113)Online publication date: Jun-2024
https://doi.org/10.1109/TCSS.2023.3347406
Liu ZLuo XZhou M(2024)Symmetry and Graph Bi-Regularized Non-Negative Matrix Factorization for Precise Community DetectionIEEE Transactions on Automation Science and Engineering10.1109/TASE.2023.324033521:2(1406-1420)Online publication date: Apr-2024
https://doi.org/10.1109/TASE.2023.3240335
Xie WPeng SYang Z(2024)Robust Semi-Supervised Community Detection Based on Symmetric Nonnegative Matrix Factorization2024 5th International Conference on Computer Engineering and Intelligent Control (ICCEIC)10.1109/ICCEIC64099.2024.10775644(55-61)Online publication date: 11-Oct-2024
https://doi.org/10.1109/ICCEIC64099.2024.10775644
Chen ZXiao QLeng TZhang ZPan DLiu YLi X(2024)Multi-constraint non-negative matrix factorization for community detection: orthogonal regular sparse constraint non-negative matrix factorizationComplex & Intelligent Systems10.1007/s40747-024-01404-410:4(4697-4712)Online publication date: 1-Apr-2024
https://doi.org/10.1007/s40747-024-01404-4
Ghadirian MBigdeli N(2024)A New Adaptive Robust Modularized Semi-Supervised Community Detection Method Based on Non-negative Matrix FactorizationNeural Processing Letters10.1007/s11063-024-11588-y56:2Online publication date: 2-Apr-2024
https://doi.org/10.1007/s11063-024-11588-y
Yang SZhang WShang RXu SWang C(2024)Attribute community detection based on attribute edges weights fusion and graph embedding factorizationApplied Intelligence10.1007/s10489-024-05687-554:22(11342-11356)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s10489-024-05687-5
Liu ZYan HZhong YLi W(2024)A Relaxed Symmetric Non-negative Matrix Factorization Approach for Community DiscoveryPRICAI 2024: Trends in Artificial Intelligence10.1007/978-981-96-0116-5_10(119-133)Online publication date: 12-Nov-2024
https://doi.org/10.1007/978-981-96-0116-5_10
Tokala SEnduri MLakshmi TSharma H(2023)Community-Based Matrix Factorization (CBMF) Approach for Enhancing Quality of RecommendationsEntropy10.3390/e2509136025:9(1360)Online publication date: 20-Sep-2023
https://doi.org/10.3390/e25091360
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents