Search

In networked communications nodes choose among available actions and benefit from exchanging information through edges, while continuous technological progress fosters system functionings that increasingly often rely on cooperation. Growing attention is being placed on coalition formation, where each node chooses what coalition to join, while the surplus generated by cooperation is an amount of TU (transferable utility) quantified by a real-valued function defined on partitions -or even embedded coalitions- of nodes. A TU-sharing rule is thus essential, as how players are rewarded determines their behavior. This work offers a new option for distributing partition function-based surpluses, dealing with cooperative game theory in terms of both global games and games in partition function form, namely lattice functions, while the sharing rule is a point-valued solution or value. The novelty is grounded on the combinatorial definition of such solutions as lattice functions whose M\"obius inversion lives only on atoms, i.e. on the first level of the lattice. While simply rephrasing the traditional solution concept for standard coalitional games, this leads to distribute the surplus generated by partitions across the edges of the network, as the atoms among partitions are unordered pairs of players. These shares of edges are further divided between nodes, but the corresponding Shapley value is very different from the traditional one and leads to two alternative forms, obtained by focusing either on marginal contributions along maximal chains, or else on the uniform division of Harsanyi dividends. The core is also addressed, and supermodularity is no longer sufficient for its non-emptiness., Comment: 10 pages. arXiv admin note: text overlap with arXiv:0905.4057 by other authors

When analyzing complex networks a key target is to uncover their modular structure, which means searching for a family of modules, namely node subsets spanning each a subnetwork more densely connected than the average. This work proposes a novel type of objective function for graph clustering, in the form of a multilinear polynomial whose coefficients are determined by network topology. It may be thought of as a potential function, to be maximized, taking its values on fuzzy clusterings or families of fuzzy subsets of nodes over which every node distributes a unit membership. When suitably parametrized, this potential is shown to attain its maximum when every node concentrates its all unit membership on some module. The output thus is a partition, while the original discrete optimization problem is turned into a continuous version allowing to conceive alternative search strategies. The instance of the problem being a pseudo-Boolean function assigning real-valued cluster scores to node subsets, modularity maximization is employed to exemplify a so-called quadratic form, in that the scores of singletons and pairs also fully determine the scores of larger clusters, while the resulting multilinear polynomial potential function has degree 2. After considering further quadratic instances, different from modularity and obtained by interpreting network topology in alternative manners, a greedy local-search strategy for the continuous framework is analytically compared with an existing greedy agglomerative procedure for the discrete case. Overlapping is finally discussed in terms of multiple runs, i.e. several local searches with different initializations., Comment: 10 pages

This work proposes an alternative approach to the so-called lattice of embedded subsets, which is included in the product of the subset and partition lattices of a finite set, and whose elements are pairs consisting of a subset and a partition where the former is a block of the latter. The lattice structure proposed in a recent contribution relies on ad-hoc definitions of both the join operator and the bottom element, while also including join-irreducible elements distinct from atoms. Conversely, here embedded subsets obtain through a closure operator defined over the product of the subset and partition lattices, where elements are generic pairs of a subset and a partition. Those such pairs that coincide with their closure are precisely embedded subsets, and since the Steinitz exchange axiom is also satisfied, what results is a geometric (hence atomic) lattice given by a simple matroid (or combinatorial geometry) included in the product of the subset and partition lattices (as the partition lattice itself is the polygon matroid defined on the edges of a complete graph). By focusing on its M\"obius function, this geometric lattice of embedded subsets of a n-set is shown to be isomorphic to the lattice of partitions of a n+1-set.

Given a family of feasible subsets of a ground set, the packing problem is to find a largest subfamily of pairwise disjoint family members. Non-approximability renders heuristics attractive viable options, while efficient methods with worst-case guarantee are a key concern in computational complexity. This work proposes a novel near-Boolean optimization method relying on a polynomial multilinear form with variables ranging each in a high-dimensional unit simplex, rather than in the unit interval as usual. The variables are the elements of the ground set, and distribute each a unit membership over those feasible subsets where they are included. The given problem is thus translated into a continuous version where the objective is to maximize a function taking values on collections of points in a unit hypercube. Maximizers are shown to always include collections of hypercube disjoint vertices, i.e. partitions of the ground set, which constitute feasible solutions for the original discrete version of the problem. A gradient-based local search in the expanded continuous domain is designed. Approximations with polynomial multilinear form of bounded degree and near-Boolean games are also finally discussed.

The input of most clustering algorithms is a symmetric matrix quantifying similarity within data pairs. Such a matrix is here turned into a quadratic set function measuring cluster score or similarity within data subsets larger than pairs. In general, any set function reasonably assigning a cluster score to data subsets gives rise to an objective function-based clustering problem. When considered in pseudo-Boolean form, cluster score enables to evaluate fuzzy clusters through multilinear extension MLE, while the global score of fuzzy clusterings simply is the sum over constituents fuzzy clusters of their MLE score. This is shown to be no greater than the global score of hard clusterings or partitions of the data set, thereby expanding a known result on extremizers of pseudo-Boolean functions. Yet, a multilinear objective function allows to search for optimality in the interior of the hypercube. The proposed method only requires a fuzzy clustering as initial candidate solution, for the appropriate number of clusters is implicitly extracted from the given data set., Comment: arXiv admin note: text overlap with arXiv:1509.07986

How to quantify the distance between any two partitions of a finite set is an important issue in statistical classification, whenever different clustering results need to be compared. Developing from the traditional Hamming distance between subsets or cardinality of their symmetric difference, this work considers alternative metric distances between partitions. With one exception, all of them obtain as minimum-weight paths in the undirected graph corresponding to the Hasse diagram of the partition lattice. Firstly, by focusing on the atoms of the lattice, one well-known partition distance is recognized to be in fact the analog of the Hamming distance between subsets, with weights on edges of the Hasse diagram determined through the number of atoms in the unique maximal join-decomposition of partitions. Secondly, another partition distance known as "variation of information" is seen to correspond to a minimum-weight path with edge weights determined by the entropy of partitions. These two distances are next compared in terms of their upper and lower bounds over all pairs of partitions that are complements of one another. What emerges is that the two distances share the same minimizers and maximizers, while a much rawer behavior is observed for the partition distance which does not correspond to a minimum-weight path. The idea of measuring the distance between partitions by means of minimum-weight paths in the Hasse diagram is further explored by considering alternative symmetric and order-preserving/inverting partition functions (such as the the rank, in the simplest case) for assigning weights to edges. What matters most, in such a general setting, turns out to be whether the weighting function is supermodular or else submodular, as this makes any minimum-weight path visit the meet or else the join of the two partitions, depending on order preserving/inverting.

Alternative novel measures of the distance between any two partitions of a n-set are proposed and compared, together with a main existing one, namely 'partition-distance' D(.,.). The comparison achieves by checking their restriction to modular elements of the partition lattice, as well as in terms of suitable classifiers. Two of the new measures obtain through the size, a function mapping every partition into the number of atoms finer than that partition. One of these size-based distances extends to geometric lattices the traditional Hamming distance between subsets, when these latter are regarded as hypercube vertexes or binary n-vectors. After carefully framing the environment, a main comparison finally results from the following bounding problem: for every value k, with 0