Methods of Semantic Drift Reduction in Large Similarity Networks
Full item record
| dc.contributor.author | Bolikowski, Łukasz | |
|---|---|---|
| dc.contributor.organization | Interdyscyplinarne Centrum Modelowania Matematycznego i Komputerowego, Uniwersytet Warszawski | pl_PL |
| dc.date.accessioned | 2011-06-01T12:19:58Z | |
| dc.date.available | 2011-06-01T12:19:58Z | |
| dc.date.issued | 2011-06-01 | |
| dc.description.abstract | We have investigated the problem of clustering documents according to their semantics, given incomplete and incoherent hints reflecting the documents’ affinities. The problem has been rigorously defined using graph theory in set-theoretic notation. We have proved the problem to be NP-hard, and proposed five heuristic algorithms which deal with the problem using five quite different approaches: a greedy algorithm, an iterated finding of maximum cliques, energy minimization inspired by molecular mechanics, a genetic algorithm, and an adaptation of the Girvan-Newman algorithm. As a side effect of the fourth heuristic, an efficient and aesthetically appealing method of visualization of the large graphs in question has been developed. The approaches have been tested empirically on the network of links between articles from over 250 language editions of Wikipedia. A thorough analysis of the network has been performed, showing surprisingly large semantic drift patterns and an uncommon topology: a scale-free skeleton linking tight clusters. It has been demonstrated that, using a blend of the proposed approaches, it is possible to automatically detect, and to a large extent eliminate, the semantic drift in the network of links between the language editions of Wikipedia. Last but not least, an open-source implementation of the proposed algorithms has been documented. | en |
| dc.description.eperson | Łukasz Bolikowski | |
| dc.identifier.uri | https://open.icm.edu.pl/handle/123456789/66 | |
| dc.language.iso | en | en |
| dc.rights | Uznanie autorstwa 3.0 Polska | pl_PL |
| dc.rights.uri | http://creativecommons.org/licenses/by/3.0/pl/ | |
| dc.title | Methods of Semantic Drift Reduction in Large Similarity Networks | en |
| dc.type | doctoralDissertation | en |
Files for this record
Original bundle
1 - 1 of 1
| Name: | phd-thesis.pdf |
|---|---|
| Size: | 2.25 MB |
| Format: | Adobe Portable Document Format |
| Description: |
Download
License files
| Name: | license.txt |
|---|---|
| Size: | 597 B |
| Format: | Item-specific license agreed upon to submission |
| Description: |
Download