Relações entre particionamento e centralidade de árvores em função do vetor de Fiedler
DOI:
https://doi.org/10.5902/2179460X64895Keywords:
Partitioning, Centrality, Fiedler VectorAbstract
The purpose of this work is to present the concepts of partitioning and centrality of edges for trees using the Fiedler vector. From this, we describe two spectral heuristics. Finally, from the classification of type I and type II trees, we show in which situations these heuristics return the same partition.
Downloads
References
BAPAT, R. B. (2010). Graphs and matrices, vol. 27. Springer.
CHAN, P. K.; SCHLAG, M. D.; ZIEN, J. Y. (1994). Spectral k-way ratio-cu tpartitioning and clustering. IEEE Transactions on computer-aided design of integrated circuits and systems,13(9),1088–1096.
CHEN, P.Y., HERO, A. O. (2014). Local fiedler vector centrality for detection of deep and over lapping communities in networks. Em: 2014 IEEE International Conferenceon Acoustics, Speech and Signal Processing (ICASSP), IEEE, pp.1120–1124.
FIEDLER, M. (1975). A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal, 25(4), 619–633.
FORTUNATO, S. (2010). Community detection in graphs. Physicsreports, 486 (3-5), 75–174.
GOULD, S. H. (2012). Variational methods foreigen value problems: an introduction to the methods of Rayleigh, Ritz, Weinstein, and Aronszajn. Courier Corporation.
GUATTERY, S.; MILLER, G. L. (1998). On the quality of spectra separators. SIAM Journal on Matrix Analysis and Applications, 19(3), 701–719.
KANNAN, R.; VEMPALA, S.; VETTA, A. (2004). On clusterings: Good, bad and spectral. Journal of the ACM (JACM), 51(3), 497–515.
NG, A. Y.; JORDAN, M. I.; WEISS, Y., et al. (2002). On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 2, 849–856.
POTHEN, A., SIMON, H. D., LIOU, K. P. (1990). Partitioning sparse matrices with eigenvectors of graphs. SIAM journal on matrix analysis and applications, 11(3), 430–452.
SHI, J., MALIK, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8), 888–905.
VON LUXBURG, U. (2007). A tutorial on spectral clustering. Statistics and computing, 17(4), 395–416.
WEI, Y. C., CHENG, C. K. (1989). Towards efficient hierarchical designs by ratio cut partitioning. Em: 1989 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers, IEEE, pp. 298–301.
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Ciência e Natura
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
To access the DECLARATION AND TRANSFER OF COPYRIGHT AUTHOR’S DECLARATION AND COPYRIGHT LICENSE click here.
Ethical Guidelines for Journal Publication
The Ciência e Natura journal is committed to ensuring ethics in publication and quality of articles.
Conformance to standards of ethical behavior is therefore expected of all parties involved: Authors, Editors, Reviewers, and the Publisher.
In particular,
Authors: Authors should present an objective discussion of the significance of research work as well as sufficient detail and references to permit others to replicate the experiments. Fraudulent or knowingly inaccurate statements constitute unethical behavior and are unacceptable. Review Articles should also be objective, comprehensive, and accurate accounts of the state of the art. The Authors should ensure that their work is entirely original works, and if the work and/or words of others have been used, this has been appropriately acknowledged. Plagiarism in all its forms constitutes unethical publishing behavior and is unacceptable. Submitting the same manuscript to more than one journal concurrently constitutes unethical publishing behavior and is unacceptable. Authors should not submit articles describing essentially the same research to more than one journal. The corresponding Author should ensure that there is a full consensus of all Co-authors in approving the final version of the paper and its submission for publication.
Editors: Editors should evaluate manuscripts exclusively on the basis of their academic merit. An Editor must not use unpublished information in the editor's own research without the express written consent of the Author. Editors should take reasonable responsive measures when ethical complaints have been presented concerning a submitted manuscript or published paper.
Reviewers: Any manuscripts received for review must be treated as confidential documents. Privileged information or ideas obtained through peer review must be kept confidential and not used for personal advantage. Reviewers should be conducted objectively, and observations should be formulated clearly with supporting arguments, so that Authors can use them for improving the paper. Any selected Reviewer who feels unqualified to review the research reported in a manuscript or knows that its prompt review will be impossible should notify the Editor and excuse himself from the review process. Reviewers should not consider manuscripts in which they have conflicts of interest resulting from competitive, collaborative, or other relationships or connections with any of the authors, companies, or institutions connected to the papers.
