@inproceedings{mitzlaff2010visit, abstract = {The ongoing spread of online social networking and sharing sites has reshaped the way how people interact with each other. Analyzing the relatedness of different users within the resulting large populations of these systems plays an important role for tasks like user recommendation or community detection. Algorithms in these fields typically face the problem that explicit user relationships (like friend lists) are often very sparse. Surprisingly, implicit evidences (like click logs) of user relations have hardly been considered to this end. Based on our long-time experience with running BibSonomy [4], we identify in this paper different evidence networks of user relationships in our system. We broadly classify each network based on whether the links are explicitly established by the users (e.g., friendship or group membership) or accrue implicitly in the running system (e.g., when user u copies an entry of user v). We systematically analyze structural properties of these networks and whether topological closeness (in terms of the length of shortest paths) coincides with semantic similarity between users.}, address = {New York, NY, USA}, author = {Mitzlaff, Folke and Benz, Dominik and Stumme, Gerd and Hotho, Andreas}, booktitle = {HT '10: Proceedings of the 21st ACM Conference on Hypertext and Hypermedia}, doi = {10.1145/1810617.1810664}, interhash = {5584c4c57fcd8eb4663df8b114bcf09c}, intrahash = {6628bf43e3834ba147a22992f2f534e9}, isbn = {978-1-4503-0041-4}, location = {Toronto, Ontario, Canada}, pages = {265--270}, publisher = {ACM}, title = {Visit me, click me, be my friend: an analysis of evidence networks of user relationships in BibSonomy}, url = {http://portal.acm.org/citation.cfm?id=1810617.1810664}, year = 2010 } @article{barber2007mac, abstract = {The modularity of a network quantifies the extent, relative to a null model network, to which vertices cluster into community groups. We define a null model appropriate for bipartite networks, and use it to define a bipartite modularity. The bipartite modularity is presented in terms of a modularity matrix B; some key properties of the eigenspectrum of B are identified and used to describe an algorithm for identifying modules in bipartite networks. The algorithm is based on the idea that the modules in the two parts of the network are dependent, with each part mutually being used to induce the vertices for the other part into the modules. We apply the algorithm to real-world network data, showing that the algorithm successfully identifies the modular structure of bipartite networks.}, author = {Barber, M. J.}, doi = {10.1103/PhysRevE.76.066102}, interhash = {e1d9f528c49b34ff4a05b2b0060bd653}, intrahash = {61f9d5839845d5d8fa1883a46a2f7744}, journal = {Physical Review E}, number = 6, title = {Modularity and community detection in bipartite networks}, url = {http://arxiv.org/abs/arXiv:0707.1616}, volume = 76, year = 2007 } @article{guimera2007mib, abstract = {Modularity is one of the most prominent properties of real-world complex networks. Here, we address the issue of module identification in two important classes of networks: bipartite networks and directed unipartite networks. Nodes in bipartite networks are divided into two non-overlapping sets, and the links must have one end node from each set. Directed unipartite networks only have one type of nodes, but links have an origin and an end. We show that directed unipartite networks can be conviniently represented as bipartite networks for module identification purposes. We report a novel approach especially suited for module detection in bipartite networks, and define a set of random networks that enable us to validate the new approach.}, author = {Guimer{\`a}, R. and Sales-Pardo, M. and Amaral, L.A.N.}, doi = {10.1103/PhysRevE.76.036102}, interhash = {a87821c7c8e7d5ca89cb369e6215a0f3}, intrahash = {6145a42fe04aee556fa7a68c7cea7db3}, journal = {Physical review. E, Statistical, nonlinear, and soft matter physics}, number = {3 Pt 2}, pages = 036102, publisher = {NIH Public Access}, title = {Module identification in bipartite and directed networks}, url = {http://arxiv.org/abs/physics/0701151}, volume = 76, year = 2007 } @article{duch-2005-72, abstract = {We propose a novel method to find the community structure in complex networks based on an extremal optimization of the value of modularity. The method outperforms the optimal modularity found by the existing algorithms in the literature. We present the results of the algorithm for computer simulated and real networks and compare them with other approaches. The efficiency and accuracy of the method make it feasible to be used for the accurate identification of community structure in large complex networks.}, author = {Duch, J. and Arenas, A.}, interhash = {2e37e9b6a0f76e94125990a47cd287f3}, intrahash = {36d905c5223e5516db9d08eb3e0bc9fc}, journal = {Physical Review E}, pages = 027104, title = {Community detection in complex networks using Extremal Optimization}, url = {http://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/0501368}, volume = 72, year = 2005 } @phdthesis{trier05visualization, author = {Trier, Matthias}, interhash = {f36769dd1fffe61d9239e4b4b7dc40e9}, intrahash = {66eb70a04e6946077182446170dd6dcf}, title = {IT-supported Visualization and Evaluation of Virtual Knowledge Communities. Applying Social Network Intelligence Software in Knowledge Management to enable knowledge oriented People Network Management}, url = {http://nbn-resolving.de/urn/resolver.pl?urn=urn:nbn:de:kobv:83-opus-10720}, year = 2005 } @misc{almeida03design, author = {Almeida, R.B. and Almeida, V.A.F.}, booktitle = {Proceedings of the 4th International Conference on Internet Computing}, interhash = {c882373d278260ba31ae4142e4f6e664}, intrahash = {41d2e7ad7417153fa5cb257486468919}, pages = {17--23}, title = {Design and evaluation of a user-based community discovery technique}, url = {citeseer.ist.psu.edu/almeida03design.html}, year = 2003 } @inproceedings{988728, abstract = { Current search technologies work in a "one size fits all" fashion. Therefore, the answer to a query is independent of specific user information need. In this paper we describe a novel ranking technique for personalized search servicesthat combines content-based and community-based evidences. The community-based information is used in order to provide context for queries andis influenced by the current interaction of the user with the service. Ouralgorithm is evaluated using data derived from an actual service available on the Web an online bookstore. We show that the quality of content-based ranking strategies can be improved by the use of communityinformation as another evidential source of relevance. In our experiments the improvements reach up to 48% in terms of average precision.}, address = {New York, NY, USA}, author = {Almeida, Rodrigo B. and Almeida, Virgilio A. F.}, booktitle = {Proceedings of the 13th international conference on World Wide Web}, interhash = {6688127f8ee06240c03f506622947f46}, intrahash = {33b448de19ddef891f2a4284b1cc42f1}, isbn = {1-58113-844-X}, pages = {413--421}, publisher = {ACM Press}, title = {A community-aware search engine}, url = {http://doi.acm.org/10.1145/988672.988728}, year = 2004 } @inproceedings{conf/www/BorodinRRT01, address = {New York, NY, USA}, author = {Borodin, Allan and Roberts, Gareth O. and Rosenthal, Jeffrey S. and Tsaparas, Panayiotis}, booktitle = {Proceedings of the 10th international conference on World Wide Web}, interhash = {08872cf4fd099592e76a10afcbb141be}, intrahash = {e8e14fc145cca87570da3f1209711183}, pages = {415--429}, publisher = {ACM Press}, title = {Finding authorities and hubs from link structures on the World Wide Web}, url = {http://doi.acm.org/10.1145/371920.372096}, year = 2001 } @inproceedings{kubica-stochastic, author = {Kubica, Jeremy and Moore, Andrew and Schneider, Jeff and Yang, Yiming}, booktitle = {Proceedings of the Eighteenth National Conference on Artificial Intelligence}, howpublished = {Conference Proceedings}, interhash = {7a471a32a59e73c43dc0dd64d55176d2}, intrahash = {1086034a16434bc39ad42264980df581}, month = {July}, pages = {798--804}, publisher = {AAAI Press/MIT Press}, title = {Stochastic Link and Group Detection}, year = 2002 } @techreport{Kubica_2003_4489, abstract = {Discovering underlying structure from co-occurrence data is an important task in many fields, including: insurance, intelligence, criminal investigation, epidemiology, human resources, and marketing. For example a store may wish to identify underlying sets of items purchased together or a human resources department may wish to identify groups of employees that collaborate with each other. Previously Kubica et. al. presented the group detection algorithm (GDA) - an algorithm for finding underlying groupings of entities from co-occurrence data. This algorithm is based on a probabilistic generative model and produces coherent groups that are consistent with prior knowledge. Unfortunately, the optimization used in GDA is slow, making it potentially infeasible for many real world data sets. To this end, we present k-groups - an algorithm that uses an approach similar to that of k-means (hard clustering and localized updates) to significantly accelerate the discovery of the underlying groups while retaining GDA's probabilistic model. In addition, we show that k-groups is guaranteed to converge to a local minimum. We also compare the performance of GDA and k-groups on several real world and artificial data sets, showing that k-groups' sacrifice in solution quality is significantly offset by its increase in speed. This trade-off makes group detection tractable on significantly larger data sets.}, address = {Pittsburgh, PA}, author = {Kubica, Jeremy Martin and Moore, Andrew and Schneider, Jeff}, institution = {Robotics Institute, Carnegie Mellon University}, interhash = {cecbc69533ab6d63fd478c7a9c7651a1}, intrahash = {3a4df0e814c3a1b125e3d403abe48733}, month = {September}, number = {CMU-RI-TR-03-32}, title = {K-groups: Tractable Group Detection on Large Link Data Sets}, url = {http://www.ri.cmu.edu/pubs/pub_4489.html}, year = 2003 } @inproceedings{kubicaKgroups, author = {Kubica, Jeremy and Moore, Andrew and Schneider, Jeff}, booktitle = {The Third IEEE International Conference on Data Mining}, editor = {Wu, Xindong and Tuzhilin, Alex and Shavlik, Jude}, interhash = {0d7be00e85fa41a082bab454c0665126}, intrahash = {a2602433bd2f144216fdddd3704d487f}, month = {November}, pages = {573-576}, publisher = {IEEE Computer Society}, title = {Tractable Group Detection on Large Link Data Sets}, year = 2003 } @misc{rcclp04defining, abstract = {The investigation of community structures in networks is an important issue in many domains and disciplines. This problem is relevant for social tasks (objective analysis of relationships on the web), biological inquiries (functional studies in metabolic, cellular or protein networks) or technological problems (optimization of large infrastructures). Several types of algorithm exist for revealing the community structure in networks, but a general and quantitative definition of community is still lacking, leading to an intrinsic difficulty in the interpretation of the results of the algorithms without any additional non-topological information. In this paper we face this problem by introducing two quantitative definitions of community and by showing how they are implemented in practice in the existing algorithms. In this way the algorithms for the identification of the community structure become fully self-contained. Furthermore, we propose a new local algorithm to detect communities which outperforms the existing algorithms with respect to the computational cost, keeping the same level of reliability. The new algorithm is tested on artificial and real-world graphs. In particular we show the application of the new algorithm to a network of scientific collaborations, which, for its size, can not be attacked with the usual methods. This new class of local algorithms could open the way to applications to large-scale technological and biological applications.}, author = {Radicchi, Filippo and Castellano, Claudio and Cecconi, Federico and Loreto, Vittorio and Parisi, Domenico}, interhash = {6ec9b00862909de405c08db1c9b43d63}, intrahash = {8634d935e0bf4d74a870d5c805612665}, month = Feb, title = {Defining and identifying communities in networks}, url = {http://arxiv.org/abs/cond-mat/0309488}, year = 2004 } @article{clauset-2004-70, author = {Clauset, Aaron and Newman, M.E.J. and Moore, Cristopher}, interhash = {2c68e3c981a00380692a3b0b661d7cfd}, intrahash = {a35d69f1d41a6cdd0632c5e1cadb4d44}, journal = {Physical Review E}, pages = 066111, title = {Finding community structure in very large networks}, url = {http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0408187}, volume = 70, year = 2004 } @article{newman2004finding, abstract = {We propose and study a set of algorithms for discovering community structure in networks -- natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems. }, author = {Newman, M.E.J. and Girvan, M.}, doi = {10.1103/PhysRevE.69.026113}, interhash = {b9145040e35ccb4d2a0ce18105e64ff4}, intrahash = {5581d4204604967a209dcc712ac391af}, journal = {Physical Review E}, pages = 026113, title = {Finding and evaluating community structure in networks}, url = {http://arxiv.org/abs/cond-mat/0308217}, volume = 69, year = 2004 } @article{gn02community, abstract = {A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known---a collaboration network and a food web---and find that it detects significant and informative community divisions in both cases.}, author = {Girvan, Michelle and Newman, M.E.J.}, interhash = {ecd7a48a37f660ab421472140168c892}, intrahash = {8f80a8586927ea69ea915b6c32e87629}, journal = {Proceedings of the National Academy of Science}, number = 12, pages = {7821-7826}, title = {Community structure in social and biological networks}, volume = 99, year = 2002 }