التفاصيل البيبلوغرافية
| العنوان: |
Joint cluster analysis of attribute data and relationship data ; The connected k -center problem, algorithms and applications |
| المؤلفون: |
Ge, Rong, Ester, Martin, Gao, Byron J., Hu, Zengjian, Bhattacharya, Binay, Ben-Moshe, Boaz |
| المساهمون: |
Natural Sciences and Engineering Research Council of Canada |
| المصدر: |
ACM Transactions on Knowledge Discovery from Data ; volume 2, issue 2, page 1-35 ; ISSN 1556-4681 1556-472X |
| بيانات النشر: |
Association for Computing Machinery (ACM) |
| سنة النشر: |
2008 |
| الوصف: |
Attribute data and relationship data are two principal types of data, representing the intrinsic and extrinsic properties of entities. While attribute data have been the main source of data for cluster analysis, relationship data such as social networks or metabolic networks are becoming increasingly available. It is also common to observe both data types carry complementary information such as in market segmentation and community identification, which calls for a joint cluster analysis of both data types so as to achieve better results. In this article, we introduce the novel Connected k -Center ( CkC ) problem, a clustering model taking into account attribute data as well as relationship data. We analyze the complexity of the problem and prove its NP-hardness. Therefore, we analyze the approximability of the problem and also present a constant factor approximation algorithm. For the special case of the CkC problem where the relationship data form a tree structure, we propose a dynamic programming method giving an optimal solution in polynomial time. We further present NetScan, a heuristic algorithm that is efficient and effective for large real databases. Our extensive experimental evaluation on real datasets demonstrates the meaningfulness and accuracy of the NetScan results. |
| نوع الوثيقة: |
article in journal/newspaper |
| اللغة: |
English |
| DOI: |
10.1145/1376815.1376816 |
| الإتاحة: |
https://doi.org/10.1145/1376815.1376816Test |
| رقم الانضمام: |
edsbas.CF76D11 |
| قاعدة البيانات: |
BASE |
