@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 } @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{citeulike:391307, address = {Arlington, VA, USA}, author = {Rosen-Zvi, Michal and Griffiths, Thomas and Steyvers, Mark and Smyth, Padhraic}, booktitle = {Proceedings of the 20th conference on Uncertainty in artificial intelligence}, citeulike-article-id = {391307}, interhash = {79b4ff1335f13cdbe18a38086e9fab3b}, intrahash = {a4dd688efe5778fb99ff94de104211aa}, isbn = {0974903906}, pages = {487--494}, priority = {0}, publisher = {AUAI Press}, title = {The author-topic model for authors and documents}, url = {http://portal.acm.org/citation.cfm?id=1036843.1036902}, year = 2004 } @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 } @inproceedings{conf/kdd/BackstromHKL06, author = {Backstrom, Lars and Huttenlocher, Daniel P. and Kleinberg, Jon M. and Lan, Xiangyang}, booktitle = {KDD}, crossref = {conf/kdd/2006}, date = {2006-10-05}, editor = {Eliassi-Rad, Tina and Ungar, Lyle H. and Craven, Mark and Gunopulos, Dimitrios}, ee = {http://doi.acm.org/10.1145/1150402.1150412}, interhash = {a3cda51b88fd4ff49632bd6b393b5b6b}, intrahash = {d7f58740d7b63881ba4993d0a576be94}, isbn = {1-59593-339-5}, pages = {44-54}, publisher = {ACM}, title = {Group formation in large social networks: membership, growth, and evolution.}, url = {http://dblp.uni-trier.de/db/conf/kdd/kdd2006.html#BackstromHKL06}, year = 2006 } @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 } @misc{noack08modularity, abstract = { Two natural and widely used representations for the community structure of networks are clusterings, which partition the vertex set into disjoint subsets, and layouts, which assign the vertices to positions in a metric space. This paper unifies prominent characterizations of layout quality and clustering quality, by showing that energy models of pairwise attraction and repulsion subsume Newman and Girvan's modularity measure. Layouts with optimal energy are relaxations of, and are thus consistent with, clusterings with optimal modularity, which is of practical relevance because both representations are complementary and often used together.}, author = {Noack, Andreas}, interhash = {a2442ee608964a82be06224fd90d54d3}, intrahash = {0186031133dc122ffd6ff33ded32c911}, title = {Modularity clustering is force-directed layout}, url = {http://www.citebase.org/abstract?id=oai:arXiv.org:0807.4052}, year = 2008 } @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{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{blondel2008fuc, author = {Blondel, V.D. and Guillaume, J.L. and Lambiotte, R. and Mech, E.L.J.S.}, interhash = {e4065c1dcd8f12fac7996dc7b2fc9476}, intrahash = {66b99a8248d2934e843f5314532340fb}, journal = {J. Stat. Mech}, pages = {P10008}, title = {{Fast unfolding of communities in large networks}}, year = 2008 } @misc{Brandes2006, abstract = {Several algorithms have been proposed to compute partitions of networks into communities that score high on a graph clustering index called modularity. While publications on these algorithms typically contain experimental evaluations to emphasize the plausibility of results, none of these algorithms has been shown to actually compute optimal partitions. We here settle the unknown complexity status of modularity maximization by showing that the corresponding decision version is NP-complete in the strong sense. As a consequence, any efficient, i.e. polynomial-time, algorithm is only heuristic and yields suboptimal partitions on many instances.}, author = {Brandes, U. and Delling, D. and Gaertler, M. and Goerke, R. and Hoefer, M. and Nikoloski, Z. and Wagner, D.}, interhash = {3e2bf460cff3138de1e855a7cf5d659d}, intrahash = {b5185cbb85b90294fa15dd2e8ea53f5e}, note = {cite arxiv:physics/0608255 Comment: 10 pages, 1 figure}, title = {Maximizing Modularity is hard}, url = {http://arxiv.org/abs/physics/0608255}, year = 2006 } @article{GirNew02, author = {Girvan, M. and Newman, M. E. J.}, interhash = {ecd7a48a37f660ab421472140168c892}, intrahash = {ec20851eb4909dd27cefec2dc9883fa4}, journal = {PNAS}, month = {June}, number = 12, pages = {7821-7826}, title = {Community structure in social and biological networks}, volume = 99, year = 2002 } @misc{Nicosia2008, abstract = { Complex networks topologies present interesting and surprising properties, such as community structures, which can be exploited to optimize communication, to find new efficient and context-aware routing algorithms or simply to understand the dynamics and meaning of relationships among nodes. Complex networks are gaining more and more importance as a reference model and are a powerful interpretation tool for many different kinds of natural, biological and social networks, where directed relationships and contextual belonging of nodes to many different communities is a matter of fact. This paper starts from the definition of modularity function, given by M. Newman to evaluate the goodness of network community decompositions, and extends it to the more general case of directed graphs with overlapping community structures. Interesting properties of the proposed extension are discussed, a method for finding overlapping communities is proposed and results of its application to benchmark case-studies are reported. We also propose a new dataset which could be used as a reference benchmark for overlapping community structures identification. }, author = {Nicosia, V. and Mangioni, G. and Carchiolo, V. and Malgeri, M.}, interhash = {06d111f009747dda641e0b28e7777ce0}, intrahash = {7d8bb9ffc0402259940814addb6954c5}, note = {cite arxiv:0801.1647 Comment: 22 pages, 11 figures}, title = {Extending the definition of modularity to directed graphs with overlapping communities}, url = {http://arxiv.org/abs/0801.1647}, year = 2008 } @article{PhysRevLett.100.118703, author = {Leicht, E. A. and Newman, M. E. J.}, doi = {10.1103/PhysRevLett.100.118703}, interhash = {825411a28bde71cda1c9087fc329d963}, intrahash = {93726cc0540f75ee1cb515b2923d69e8}, journal = {Phys. Rev. Lett.}, month = mar, number = 11, numpages = {4}, pages = 118703, publisher = {American Physical Society}, title = {Community Structure in Directed Networks}, url = {http://prl.aps.org/abstract/PRL/v100/i11/e118703}, volume = 100, year = 2008 } @misc{Leskovec2010, abstract = { Detecting clusters or communities in large real-world graphs such as large social or information networks is a problem of considerable interest. In practice, one typically chooses an objective function that captures the intuition of a network cluster as set of nodes with better internal connectivity than external connectivity, and then one applies approximation algorithms or heuristics to extract sets of nodes that are related to the objective function and that "look like" good communities for the application of interest. In this paper, we explore a range of network community detection methods in order to compare them and to understand their relative performance and the systematic biases in the clusters they identify. We evaluate several common objective functions that are used to formalize the notion of a network community, and we examine several different classes of approximation algorithms that aim to optimize such objective functions. In addition, rather than simply fixing an objective and asking for an approximation to the best cluster of any size, we consider a size-resolved version of the optimization problem. Considering community quality as a function of its size provides a much finer lens with which to examine community detection algorithms, since objective functions and approximation algorithms often have non-obvious size-dependent behavior. }, author = {Leskovec, Jure and Lang, Kevin J. and Mahoney, Michael W.}, interhash = {0e58de655596b2198f4a7001facd0c32}, intrahash = {410a9cbea51ea5dd3c56aad26a0e11b2}, note = {cite arxiv:1004.3539 }, title = {Empirical Comparison of Algorithms for Network Community Detection}, url = {http://arxiv.org/abs/1004.3539}, year = 2010 } @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 } @inproceedings{scripps2007roles, abstract = {A node role is a subjective characterization of the part it plays in a network structure. Knowing the role of a node is important for many link mining applications. For example, in Web search, nodes that are deemed to be authorities on a given topic are often found to be most relevant to the user's queries. There are a number of metrics that can be used to assign roles to individual nodes in a network, including degree, closeness, and betweenness. None of these metrics, however, take into account the community structure that underlies the network. In this paper we define community-based roles that the nodes can assume (ambassadors, big fish, loners, and bridges) and show how existing link mining techniques can be improved by knowledge of such roles. A new community-based metric is introduced for estimating the number of communities linked to a node. Using this metric and a modification of degree, we show how to assign community-based roles to the nodes. We also illustrate the benefits of knowing the community-based node roles in the context of link-based classification and influence maximization.}, acmid = {1348553}, address = {New York, NY, USA}, author = {Scripps, Jerry and Tan, Pang-Ning and Esfahanian, Abdol-Hossein}, booktitle = {Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis}, doi = {http://doi.acm.org/10.1145/1348549.1348553}, interhash = {bc67321ee8dc1e7db1c3c234833a5519}, intrahash = {4435192c25bfc86b47f030011f4ce1ef}, isbn = {978-1-59593-848-0}, location = {San Jose, California}, numpages = {10}, pages = {26--35}, publisher = {ACM}, series = {WebKDD/SNA-KDD '07}, title = {Node roles and community structure in networks}, url = {http://doi.acm.org/10.1145/1348549.1348553}, year = 2007 } @article{newman2006modularity, abstract = {Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as “modularity” over the possible divisions of a network. Here I show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which I call the modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times. I illustrate the method with applications to several published network data sets.}, author = {Newman, M. E. J.}, doi = {10.1073/pnas.0601602103}, interhash = {e664336d414a1e21d89f30cc56f5e739}, intrahash = {5dd9d0c2155f242393e63547d8a2347f}, journal = {Proceedings of the National Academy of Sciences}, number = 23, pages = {8577--8582}, title = {Modularity and community structure in networks}, volume = 103, year = 2006 } @incollection{yu2000social, abstract = {Trust is important wherever agents must interact. We consider the important case of interactions in electronic communities, where the agents assist and represent principal entities, such as people and businesses. We propose a social mechanism of reputation management, which aims at avoiding interaction with undesirable participants. Social mechanisms complement hard security techniques (such as passwords and digital certificates), which only guarantee that a party is authenticated and authorized, but do not ensure that it exercises its authorization in a way that is desirable to others. Social mechanisms are even more important when trusted third parties are not available. Our specific approach to reputation management leads to a decentralized society in which agents help each other weed out undesirable players.}, address = {Berlin/Heidelberg}, affiliation = {Department of Computer Science, North Carolina State University, Raleigh, NC 27695-7534, USA}, author = {Yu, Bin and Singh, Munindar}, booktitle = {Cooperative Information Agents IV - The Future of Information Agents in Cyberspace}, doi = {10.1007/978-3-540-45012-2_15}, editor = {Klusch, Matthias and Kerschberg, Larry}, interhash = {1065a4963600ef4f9b4c034d3bbd9a50}, intrahash = {337afcb67138b927b27a9687199e8568}, isbn = {978-3-540-67703-1}, keyword = {Computer Science}, pages = {355--393}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {A Social Mechanism of Reputation Management in Electronic Communities}, url = {http://dx.doi.org/10.1007/978-3-540-45012-2_15}, volume = 1860, year = 2000 } @article{Atzmueller:12c, author = {Atzmueller, Martin}, interhash = {0b20c1d53d5df05326d594726273c2fb}, intrahash = {7b616e64994893a2aad95b5ad95db662}, journal = {WIREs: Data Mining and Knowledge Discovery}, title = {{Mining Social Media: Key Players, Sentiments, and Communities}}, volume = {In Press}, year = 2012 }